Skip Lists are Fascinating
igoro.com
igoro.com
for (int R = _rand.Next(); (R & 1) == 1; R >>= 1)
Safer:
while (_rand.Next(2) == 0)
Another nice thing about skip lists is that they are relatively easy to make into cheap persistent structures (aka functional structures), that is, structures where operations return a new immutable copy of the structure, but share most of the substructure with the previous version.
Actually, his technique is way faster (1 random generation per element, vs. log(n) or log(u)), but you're absolutely right, you need to take the higher order bits first or your skiplist will be very far from correct.
(P.S. I'd love to have you reviewing my code ;-)
The expected height of an element is 2, and the maximum height is 32. So there is at most a constant-factor performance difference, and in practice we should find this constant to be small.
It's not clear whether any small performance gain is worth the loss of clarity in presentation of the algorithm and code.
The simplest purely functional balanced dictionary structures I am aware of are 2-3 trees, which are actually another way of viewing 1-2 skip lists, a deterministic variant of skip lists!
http://scholar.google.com/scholar?cluster=107462261140470234...
How? I thought about this for a while, but could not come up with a persistent version of skiplists.
[1] http://ocw.mit.edu/courses/electrical-engineering-and-comput...
Adv. knowledge of data-structures is definitely one of the hallmarks of a powerful developer.
What I do find very interesting about skip lists is that they support fingers - pointers to locations in the structure that allow fast modification nearby. As a very simple example, prepending an item to a skip list (this cons) is O(1) expected.
Getting this property for AVL or red-black trees is possible, but much more difficult, and requires fundamental changes to the structural invariants and representations.
For more on the uses of finger search, see:
The nice thing about skip lists, beyond being mostly simple, is that min() is O(1), which is far more useful than the middling value at the root of AVL trees.
That you can finger-append in O(u) is misleading, since ideally u≃log n and finger operations are amortized O(1) in AVL trees (I know it's been shown empirically, not sure if analytically).
Of course you can do this for AVL trees as well, but in order to do so there is to take additional information in the structure.
What's finger-append?
> finger operations are amortized O(1) in AVL trees (I know it's been shown empirically, not sure if analytically)
Do you have a citation for that? I thought delete was Theta(lg n) expected, even from a finger.
The O(1) wasn't amortized, it was expected. The citation is P. L. Karlton, S. H. Fuller, R. E. Scroggs and E. B. Kaehler, Performance of height-balanced trees. Comm. ACM 19, 1 (1976), 23-28.
i've had to implement both and replace many of the java collections interfaces with them as the backing store for various projects or coursework. i find the structure of the skiplists intricate and fascinating as a thought experiment, but i feel they difficult for certain things, like implementing an iterator over them. treaps, if i recall correctly, just use the normal BST traversals.
would be curious to hear comparisons on the two, being probably the most popular of the probabilistic data structures.
performance wise, i've found both to have their strengths and weaknesses under various load testing scenarios. i have some stats around here somewhere.
of course the downside with any probabilistic data structure is that you're counting on the amortized bounds, but could end up with the absolute worst case performance at times. there are so many well-documented and well-implemented libraries out there for red-black trees (the gold standard in my opinion) that it's hard to find compelling reasons besides curiosity to use them in practice.
the original papers for both of them are here (treaps):
http://faculty.washington.edu/aragon/pubs/rst89.pdf
and here (skiplists) :
ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf
Skip lists are augmented single-linked lists. You can traverse likewise.
See the python implementation[1] and its lua port[2].
it's been a few years since i've worked with skiplists and i remember some kind of complexity/hangup with them, but darned if i can find what that could have been looking at those clean python implementations.
TODO: go back and take a look at skiplists again.
PS: skiplists in haskell http://j.mp/ge5Voi
No. With typical probabilistic data structures you're counting on the average bounds. If you have good amortized bounds and that's what you care about, you don't need to bother with the randomization. Per-operation versus amortized and worst-case versus average-case are orthogonal distinctions.
On the other hand, skiplists are just sorted lists that can be maintained in O(log n) time, which is a conceptually very nice thing. The GSequence data structure in glib is such a sorted list, but implemented internally with a treap, so it's possible to get that type of API with treaps too.
It's essentially a 2 level skip list (but could be generalized where you get one extra level per bowling ball), and brings out some basic calculus to optimize lookup performance even further.