For C# on .NET, this may work fine, but in general, this is a bad way of extracting a 0/1 choice from a pseudo-random number generator (PRNG). Many PRNGs use linear congruential generators, which are just a multiply and an add, and have highly predictable low bits as a result (frequently just a repeating pattern with a short period, as short as 4 or 8).
Safer:
while (_rand.Next(2) == 0)
- or even simply reading the bits off the other end.
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.
> 1 random generation per element, vs. log(n) or log(u)
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.
Not only that, but if you were to write this in (say) Java, which uses a linear congruential random number generator, doing it this way would probably be even faster due to the higher quality random numbers. The least significant bits on a linear congruential generator aren't terribly random.
> 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.
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!
My take is to never trust the built-in random number generator of any standard library. Get a copy of Numerical Recipes and implement your own, it's only a few lines of code.
At least then you know which one it is, what properties it has, and how it is initialized. Too few random number libraries document this. But as that is the primary advantage my gut would be to still at least use a library. It's not hard to come up with a Mersenne Twister library, and if you need something cryptographically secure just about the only thing I'd even consider is going straight to the OpenSSL implementation.
You need to be able to re-create your inputs if a problem occurs. You need to be able to seed a random number generator and have it generate the same sequence for debugging.
> 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.
How? I thought about this for a while, but could not come up with a persistent version of skiplists.
They are indeed fascinating, and Erik Demaine's MIT OCW lecture on it is amazing [1]. The analogy between the NYC subway system (express and local trains) and skip lists is brilliant.
Terrific lecture. A bit leisurely for the first hour, probably could've cover that in half the time, but then progressively realizes he's short on time and accelerates through the probabilistic analysis of the runtime. Still pretty easy to follow at warp speed near the end, because he is extremely clear. For instance, you can tell when he makes a simple 1/x mistake in a couple places (he catches himself), since his explanation which goes along with the calculation is crystal clear. Nice job.
I don't find skip lists to be simpler than AVL trees, but it's my understanding I'm in the minority on this issue.
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.
I find AVL trees simpler as well, and probably a good deal more performant.
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).
Since MIN / MAX are O(1) operations there is a trivial optimization where you can add elements that are greater or smaller of any other element in O(1), and in many applications this is happens with a great probability.
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.
By finger-append I meant that skip lists are normally singly linked, and so you can append to a sublist but not prepend nor insert into the implied subtree.
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 should also note that it's not very surprising that AVL restructurings show up as expected O(1) empirically, since many AVL trees are BB-trees, and it's been shown for BB-trees under the assumption that the root approximates the median - which is certainly true in most experimental settings. So It's quite possible the expectation isn't O(1) for pathological distributions, not to mention sequences.
Yes. I have read that big skip lists have poor data locality because the skips jump at unpredictable (probabilistic) times to memory that is probably on a different page.
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):
> 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.
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.
> * 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].
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.
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.
Safer:
- or even simply reading the bits off the other end.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.