Sliding window data structure
David Hopwood
<>
Tue Aug 30 04:55:39 CEST 2005
Richard A. O'Keefe wrote:
> 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
> is O(log(N))
>
> 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.
I think it's possible to get O(log(N)) indexing and O(1) worst-case
shifting, by using the the skew binary random access list from Chapter 9
of Chris Okasaki's "Purely Functional Data Structures" [*]. This structure
supports O(log(N)) indexing and an O(1) worst case 'head', 'cons' and
'tail'. It is not quite a sliding window, but it can be made into one
(for the shift operation, use 'cons' and drop the final digit/tree whenever
the list grows too long; this doesn't affect the bounds). But that's quite
complicated, so yes, I'd be interested in a simple way of doing a purely
functional sliding window.
[*] or section 6.4.1 of <http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf>
--
David Hopwood <>
More information about the erlang-questions
mailing list