5 ms·

i've always preferred treaps to skiplists as far as probabilistic data structures are concerned. that could be partially due to the fact that i felt aragon and

i've always preferred treaps to skiplists as far as probabilistic data structures are concerned. that could be partially due to the fact that i felt aragon and seidel's paper on treaps to be fundamentally better that pugh's paper on skiplists, which i recall being kind of hand-wavy with respect to the analysis. 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 http://faculty.washington.edu/aragon/pubs/rst89.pdf and here (skiplists) : ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf

pygy_ 16y ago
> * 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.* Skip lists are augmented single-linked lists. You can traverse likewise. See the python implementation[1] and its lua port[2]. 1. http://code.activestate.com/recipes/576930/ http://code.activestate.com/recipes/576930/ 2. http://love2d.org/wiki/Skip_list http://love2d.org/wiki/Skip_list
- kamechan 16y ago
  hmm, yeah those iterators are nice and simple. 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 http://j.mp/ge5Voi
gjm11 16y ago
> of course the downside with any probabilistic data structure is that you're counting on the amortized bounds 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.
- kamechan 16y ago
  yes, sorry. that's what i meant. long day. wait, it's still not over.
ssp 16y ago
An advantage of treaps is that is that there is a natural way to add aggregates. That is, you can put data in a node that summarises the underlying tree. These are very useful in many applications and can be maintained in the same O(log n) bound that you get for insertion and deletion. I think it might be possible to get the same effect in skiplists, but it wouldn't be nearly as natural. 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.

pygy_ 16y ago

> * 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.* Skip lists are augmented single-linked lists. You can traverse likewise. See the python implementation[1] and its lua port[2]. 1. http://code.activestate.com/recipes/576930/ http://code.activestate.com/recipes/576930/ 2. http://love2d.org/wiki/Skip_list http://love2d.org/wiki/Skip_list

kamechan 16y ago
hmm, yeah those iterators are nice and simple. 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 http://j.mp/ge5Voi

gjm11 16y ago

> of course the downside with any probabilistic data structure is that you're counting on the amortized bounds 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.

kamechan 16y ago
yes, sorry. that's what i meant. long day. wait, it's still not over.

ssp 16y ago

An advantage of treaps is that is that there is a natural way to add aggregates. That is, you can put data in a node that summarises the underlying tree. These are very useful in many applications and can be maintained in the same O(log n) bound that you get for insertion and deletion. I think it might be possible to get the same effect in skiplists, but it wouldn't be nearly as natural. 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.