Fast running maximum-minimum filters in C++.

A running maximum-minimum filter computes the maximum and minimum for each window in a sequence. For example, given these values:

1,2,3,2,1

Then the running maximum filter with a window of size 3 is:

3,3,3

whereas the minimum filter is

1, 2, 1

A running maximum-minimum filter computes simultaneously the maximum and the minimum filters.

Sample:

  supermaxmin C(data,width);// width in an integer and data is some vector
  vector<double> runningmax = a.getmaxvalues(); // gets the max values, as a vector
  vector<double> runningmin = a.getminvalues(); // gets the min values, as a vector

This code implements the algorithms described in the following paper:

• Daniel Lemire, Streaming Maximum-Minimum Filter Using No More than Three Comparisons per Element. Nordic Journal of Computing, 13 (4), pages 328-339, 2006. http://arxiv.org/abs/cs.DS/0610046

One of the result of this paper is that it is possible to compute the maximum-minimum filter faster than it is possible to compute both the maximum filter and the minimum filtering separately.