Sliding window data structure

Richard A. O'Keefe ok@REDACTED
Tue Aug 30 07:13:48 CEST 2005


I wrote:
	> I've found a fairly simple data structure for sliding windows
David Hopwood <david.nospam.hopwood@REDACTED> provided a useful
link:
	http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

My data structure is basically a cross between what Okasaki calls
a Binary Random Access List (*not* skew binary) and the back-to-back
lists traditionally used for queues.

Basically, a sliding window is a triple {Size,Left,Right}
where Left and Right are lists of complete binary trees.
The Left list is a Binary Random Access List.
The Right list *isn't*.  When you shift a window that has
an empty Right list, you sete the Right list to be reverse(Left).
So in Left you have small elements to the left of big ones,
but after a switchover the new Right list goes from big to small.
Then when you start deleting from the Right list, the biggest
element breaks up.  So you get this sort of size pattern:

    Left (increasing size)			<
    Right <increasing size) (decreasing size)	< >

It's easy to show that length(Right) <= 2*logN, and for each
Tree in Left or Right, depth(Tree) <= logN.  (Leaving the occasional
ceiling and +constant out.)
Thw worst case of log(N) comes partly from reversing the Left list,
but mostly from tree building and dismantling.

The nice thing is that it really does work out to O(1) amortised cost
per slide.

I suspect that Skew Binary Random Access Lists could also be used back-
to-back this way, but I don't understand them well enough to tell what
weakening the invariant for the Right list would do.

I've just this minute discovered Hinze and Paterson's "2-3 Finger Trees",
which amongst other things give you O(1) amortised push and pop at each
end.  They can also support indexing.  I don't know why they call it a
"simple" data structure, though.

For what it's worth, the Erlang code seems to be about twice as slow as
SICStus Prolog, and that's with c(window, [verbose,hipe]) in a hipe-
enabled Erlang.



More information about the erlang-questions mailing list