scipy/scipy — pull request #3517 by jaimefrio (2014-04-02 04:04:29+00:00)
Title: ENH: speed-up ndimage.filters.min(max)imum_filter1d

The current implementation of `min(max)imum_filter1d` rescans the full filter
window at every step, leading to an `O(n*m)` complexity, `n` being the size of
the image, and `m` of the filter.

This PR changes the computation algorithm, keeping track of the min(max)imum
value, and its offset from the current position. This allows to compute the
min(max)imum by making a single compare of the next value in the image against
the min(max)imum, and checking that the min(max)imum is still within the filter
window. This leads to an expected `O(n)` average performance, although the worst
case is still `O(n*m)`.

The worst case happens for strictly inc(dec)reasing sequences of values. Despite
the extra overhead of keeping track of the min(max)imum offset, the new code
also runs faster for this case, probably due to replacing array indexing operations
with pointer arithmetic.