alt Hacker NewsCould someone provide intuitive understanding for why the "express lanes" in a skip list are created probabilistically?
My first instinctive idea would be that there is an optimal distance, maybe based on absolute distance or by function of list size or frequency of access or whatever. Leaving the promotion to randomness is counter intuitive to me.
Replies
Maybe for very high-level intuition, it's vaguely similar to other randomized algorithms that you want to minimize the worst-case on expectation and the easiest way to do so is to just introduce randomness (think quicksort, which is N^2 worst case with a badly chosen pivot). Your idea of there being an optimal distance is similar to the concept of "derandomization" maybe, e.g. in Quicksort there are deterministic pivot selection algorithms to avoid the worst case. But all of those require much more effort to compute and require an algorithm whose output is a function of the input data. Whereas randomly picking a pivot or randomly creating express lanes is simpler and avoids the data dependency (which is important since unlike sorting, the data isn't fixed ahead of time).
There likely is an optimal stride, as a function of the platform and the data you are storing. There is also a worst-case stride. You probably don't know what the good and bad strides are, and because they are data-dependent, they can change over time. Randomness gives you a very high probability of avoiding very bad case performance. And (to rephrase what another comment says) avoiding a constant stride avoids unlucky 'resonances' where the interval interacts with some other fixed property of your system or data.
If it has a constant stride then that stride can align with something upstream and result in horrible performance
The same reason naive BST tree (non self balancing one) doesn't work. You need to be able to add and remove elements without any knowledge of future operations and without malicious input being able to force a degenerate structure which is equivalent to a flat linked list. It's a bit similar how treap achieves somewhat balanced tree using randomness instead of deterministic rebalancing algorithms.
If you knew all the items ahead of time and didn't require adding/removing them incrementally you could build optimal skiplist without randomness. But in such situations you likely don't need a skip list or BST at all. Binary search on sorted list will do.