Open harendra-kumar opened 2 years ago
We can possibly combine the ring and the heap into a single data structure to efficiently find the min/max in a rolling window.
For smaller window sizes we could just use the ring buffer and perform a linear search in it to find the min/max. The total cost would be n * w
.
We can possibly use a heap instead of a
Deque
, hopefully giving better performance. Here is how it might work.Assuming the input is (a, Maybe a), where the first element of the tuple is the element being inserted in the window and the second element is the one being ejected from the window. Assuming a min heap to find the minimum:
(x, Nothing)
, insertx
into the heapx
into the heap, discard any of the existing heap elements that are greater thanx
.(x, Just y)
, since we know thaty
is the last element in the window, we know thaty
has to be minimum if it is present in the heap. So removey
from the top of the heap if it is the top element in the heap. Then insertx
as described in the previous steps. If there are multiple instances ofy
in the window then we should not remove it, we can keep a refcount for that and decrement the refcount until it becomes 0. Increment the refcount when inserting a duplicate.Note that we would need a custom heap implementation as we need to cut the top of the heap in one case and the bottom of the heap in another.
The cost would likely be
n * log w
wheren
is the number of elements in the stream andw
is the window size. The worst case forminimum
would be when the input stream is sorted ascending order. The best case would be when it is sorted in the descending order.Note that we can perform a partial sort of the stream by scanning it using the
min
or themax
fold.