# ANN: MaxMinFilters.jl - fast streaming maximum / minimum within moving window

**URL:** <https://discourse.julialang.org/t/ann-maxminfilters-jl-fast-streaming-maximum-minimum-within-moving-window/30151>\
**Category:** Package Announcements\
**Tags:** announcement\
**Created:** [October 22, 2019, 12:34am UTC](https://discourse.julialang.org/t/ann-maxminfilters-jl-fast-streaming-maximum-minimum-within-moving-window/30151 "2019-10-22T00:34:24Z")\
**Posts on this page:** 5\
**Page:** 2

<div class="post-metadata">

**Author:** ![sairus7](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sairus7/32/10816_2.png) [@sairus7](https://discourse.julialang.org/u/sairus7)\
**Post date:** [November 7, 2019, 4:11pm UTC](https://discourse.julialang.org/t/ann-maxminfilters-jl-fast-streaming-maximum-minimum-within-moving-window/30151/21 "2019-11-07T16:11:03Z")

</div>

I think, when writing some new functions, it is easier to start with 1-dimensional case for simplicity, then debug it, and then it can be rewritten to multi-dimensional case, if applicable. And if there are some notable performance differences OR extra code complexity, we can leave both implementations.

It’s nice to have one implementation for 2 and more dimensions. But combining 1 and many has some extra burden, e.g. in DataStructures we have 1-dimensional CircularDeque, and there is no need to rewrite it for multidimensional deque with pushes along selected dims. If we really need that, it can be just added in separate source file.

---

<div class="post-metadata">

**Author:** ![Jakub\_Wronowski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jakub_wronowski/32/204030_2.png) [@Jakub\_Wronowski](https://discourse.julialang.org/u/Jakub_Wronowski)\
**Post date:** [January 29, 2020, 9:05pm UTC](https://discourse.julialang.org/t/ann-maxminfilters-jl-fast-streaming-maximum-minimum-within-moving-window/30151/22 "2020-01-29T21:05:15Z")

</div>

Hi, recently there were thread started by @Kruxigt and I realised, that I need this functionality 🙂

> [@juliohm](#):
>
> Indeed, it would be nice to see a generalization of all these efforts into a single even more powerful package.

As I will need those moving max/min for a quantitative algorithms I am working now, I can spend some time on such consolidation or improving something in existing ones, cause I want to avoid creating one more package with this functionality.

> [@tkf](#):
>
> Just FYI, you may be interested in transducers instead of stateful functions, e.g., if you want to squeeze out performance

This is what I am going to do, using transducers will allow operations on infinite streams.

> [@tim.holy](#):
>
> The algorithm in MaxMinFilters is the same one implemented in ImageFiltering; it just turned out the one in ImageFiltering had been optimized for small window sizes. A [small tweak](https://github.com/JuliaImages/ImageFiltering.jl/pull/115) fixed the performance for large windows, so that now its performance is similar to MaxMinFilters.

@tim.holy, unfortunately my benchmarks are not reflecting that. Am I doing something wrong?

EDIT: now I see that it uses fast algorithm for extrema, but not minimum or maximum

```julia
julia> @btime ImageFiltering.mapwindow($maximum, $x, $1001);
  1.010 s (11021 allocations: 17.82 MiB)

julia> @btime movmax($x, $1001);
  9.996 ms (3 allocations: 7.64 MiB)

julia> length(x)
1000000

```

---

<div class="post-metadata">

**Author:** ![sairus7](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sairus7/32/10816_2.png) [@sairus7](https://discourse.julialang.org/u/sairus7)\
**Post date:** [January 30, 2020, 8:25am UTC](https://discourse.julialang.org/t/ann-maxminfilters-jl-fast-streaming-maximum-minimum-within-moving-window/30151/23 "2020-01-30T08:25:11Z")

</div>

What functionality are you talking about?  
There are different sets of possible functionality extensions:

1. Steteless functions (to process small data chunks at once) =\> stateful functions for (realtime or larger than memory) data streams, that can be stopped and resumed later, so function state can be saved and loaded. This is also related to delays and boundary conditions handling.

2. Special function types:

3. Functions for 1-dimensional signals =\> multi-diomensional signals, like video streams.

4. Composing chains of processing steps, like: “filter1 \> decimate \> sliding function \> detect events \> calc features \> …” and so on. It is related to using transducers to feed data, or making functions and data buffers compatible for possible use with transducers. You may be interested in this thread:  
[Using Transducers.jl instead of stateful functions for stream processing](https://discourse.julialang.org/t/using-transducers-jl-instead-of-stateful-functions-for-stream-processing/30553)  
Speaking of transducers, I just don’t fully understand, how to use them for complex processing chains, if you need branching and joining data streams, select to store some intermediate data, log intermediate data for debug purpose, and so on.

All that extensions are partly compatible with each other, but not all.

Also, I think we should start with as simple use cases as possible.

---

<div class="post-metadata">

**Author:** ![Jakub\_Wronowski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jakub_wronowski/32/204030_2.png) [@Jakub\_Wronowski](https://discourse.julialang.org/u/Jakub_Wronowski)\
**Post date:** [January 30, 2020, 8:22pm UTC](https://discourse.julialang.org/t/ann-maxminfilters-jl-fast-streaming-maximum-minimum-within-moving-window/30151/24 "2020-01-30T20:22:34Z")

</div>

Nice summary, I can see you were working a lot on this algorithm.

> [@sairus7](#):
>
> Steteless functions (to process small data chunks at once) =\> stateful functions for (realtime or larger than memory) data streams, that can be stopped and resumed later, so function state can be saved and loaded. This is also related to delays and boundary conditions handling.

This is the most interesting for me - processing of very large or infinite streams from databases or other “larger than memory” sources. I don’t think stopping and resuming is crucial but probably you have more insight in this concept than me, so maybe just I cannot imagine a use case. There are coroutines, tasks and threading (see [ThreadPools.jl](https://discourse.julialang.org/t/ann-threadpools-jl-improved-thread-management-for-background-and-nonuniform-tasks/33592)), so they can handle interrupts in the data delivery quite nice.

> [@sairus7](#):
>
> Special function types:

Those functionalities sounds complicated, I am not sure the O(N) algorithm will handle them.

> [@sairus7](#):
>
> Functions for 1-dimensional signals =\> multi-diomensional signals, like video streams.

I guess we neeed an array of Deques to handle that. Probably it would be useful somewhere but I have only 1D cases to handle.

> [@sairus7](#):
>
> Speaking of transducers, I just don’t fully understand, how to use them for complex processing chains, if you need branching and joining data streams, select to store some intermediate data, log intermediate data for debug purpose, and so on.

I don’t think they can handle that. Branching streams is not easy. If we have an iterator to database query stream it would be problematic to iterate it in 2 places with different cadence. The solution would be to open 2 independent connections and process them separately, eventually we can join those 2 processed streams later.

> [@sairus7](#):
>
> Also, I think we should start with as simple use cases as possible.

So for me simplest use case is to make this fast extrema algorithm work for any iterable things, not only AbstractArrays. I’ll try to prototype it soon, the discussion you linked is helpful. I did it long time ago in C# so this is feasible.

---

<div class="post-metadata">

**Author:** ![LostInMusic](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lostinmusic/32/7486_2.png) [@LostInMusic](https://discourse.julialang.org/u/LostInMusic)\
**Post date:** [September 20, 2020, 8:44pm UTC](https://discourse.julialang.org/t/ann-maxminfilters-jl-fast-streaming-maximum-minimum-within-moving-window/30151/25 "2020-09-20T20:44:31Z")

</div>

When I looked for an efficient moving/rolling/running median in Julia this was one of the first threads I found, but none of the mentioned packages could do a running median that was fast enough for my application.  
So I took matters into my own hands and created one:

[https://github.com/Firionus/FastRunningMedian.jl](https://github.com/Firionus/FastRunningMedian.jl)

For window sizes above roughly 10 it is faster than sairus7’s [https://github.com/sairus7/SortFilters.jl](https://github.com/sairus7/SortFilters.jl) which can do arbitrary probability levels though. See the README.md for Benchmarks.

[Previous page](https://discourse.julialang.org/t/ann-maxminfilters-jl-fast-streaming-maximum-minimum-within-moving-window/30151.md?page=1)