Sliding window data structure
Richard A. O'Keefe
Tue Aug 30 03:25:12 CEST 2005
Not so long ago we had a thread about tuple operations,
with the motivation being sliding windows.
I've found a fairly simple data structure for sliding windows
(indexed collections with the property that when you push a
new value on one end an old value drops off the other)
with the following properties:
make_window(N, Element) -> Window
list_to_window(List) -> Window
window_to_list(Window) -> List
are all O(N)
index_window(I, Window) -> Element
shift_window(New_Element, Window) -> New_Window
is O(log(N)) worst case,
BUT is O(1) amortised.
I've measured the performance for indexing and shifting,
and they are empirically O(log(N)) -- I haven't seen such a beautiful
straight line in an empirical plot in a *long* time -- and O(1) as
claimed over N = 1 to 1,000,000.
It's pretty easy to come up with a data structure which is O(1)
amortised cost for shift_window/2; the old back-to-back pair of
lists for queues will do it. But that doesn't give you O(log(N))
worst case, and it doesn't give you O(log(N)) indexing.
Is this of any interest? It does suggest to me that we don't need
fancy array operations for sliding windows.
More information about the erlang-questions