4
$\begingroup$

In Skip Lists: A Probabilistic Alternative to Balanced Trees by Pugh he suggests different strategies for choosing the level of an inserted node. One such strategy, called fix the dice, limits the level to our previous highest level plus one if a higher level was randomly chosen.
What are the practical implications of choosing this strategy, especially for large skip lists and those with p < 1/2?
I imagine it could lead to a higher than usual fanout, but without all too dramatic effects, especially if deletions are as common as insertions after some growth (since that would minimize the effect of lower than usual levels after that initial growth).
Any educated speculation or hints to already existing analyses are welcome.

$\endgroup$
  • $\begingroup$ I apologize for editing the answer after you accepted it, but I really wasn't satisfied with the arithmetic. I think the edit is clearer and more accurate, although the result works out to the same thing (since $\log n / n$ is asymptotically zero, fixing the dice has asymptotically no effect, and a negligible effect in practice, since the asymptote is reached rapidly.) I hope you concur with the edit. $\endgroup$ – rici May 22 '17 at 16:56
4
$\begingroup$

Contrary to what Pugh says in that paper, I don't believe the "fix the dice" strategy has any impact on the stochastic analysis of skip list performance.

The strategy demotes (reduces the level) of a newly-created item to one more than the current maximum level in the skip list, if the random level assignment would have produced a higher level. Let's call such an item a demoted item.

Observe that the skip list cannot contain two demoted items at the same level. One of them would have to have been created first, and that would prevent the other one from having been demoted to that level. (Items are never demoted after they are created, so even if deletions entirely empty some level, higher-level items continue to have the same level. One could imagine a strategy which also demoted existing items in such a case, but even then it would be impossible to have two demoted items at the same level.)

The level of an item is limited to $MaxLevel$ (using Pugh's terminology), which means that there are at most $MaxLevel$ demoted items in the skip list. Pugh suggests choosing $MaxLevel$ as $log_{p^{-1}}N$ where $N$ is the expected maximum number of elements in the skip list. In practice, we might use a fixed constant, or we might use $log_{p^{-1}}M$ where $M$ is the maximum size that the skip list has ever reached (assuming we use an implementation where $MaxLevel$ can be incremented). In any case, we expect that $MaxLevel$ is $O(\log n)$.

Now, let's say that $\mathscr{E}(l)$ is the expected number of items at level $l$ without die-fixing and $\mathscr{E}'(l)$ is the expected number in the die-fixed skip list. Die-fixing could cause at most $l-1$ items at level $l$ to be demoted to another level (because there are only $l-1$ lower levels, each of which can have at most one demoted item) and it could cause at most $1$ item at a higher level to be demoted to $l$. So:

$$\mathscr{E}'(l) \in [\mathscr{E}(l)-l-1, \mathscr{E}(l)+1]$$

Since $\mathscr{E}(l) = n\mathscr{P}(l)$, where $\mathscr{P}(l)$ is the probability for a random item to be at level l (analogue $\mathscr{P}'(l)$ for the die-fixed list), we can estimate

$$\mathscr{P}'(l) \in [\mathscr{P}(l)-{{l-1} \over n}, \mathscr{P}(l)+{1\over n}]$$

But as noted above, the maximum value of $l$ is $O(\log n)$, so both ends of that range are asymptotically $\mathscr{P}(l)$.

In other words, the "fix the dice" strategy does not significantly change the probability that a random node is at a given level. Therefore, it does not "totally destroy" (or even affect) our ability to analyse the algorithms, and there is no reason why even a purist should avoid it.

$\endgroup$
  • $\begingroup$ Thanks for the further improvement! Unfortunately, why exactly die-fixing causes l-1 items to be demoted is not entirely clear to me now. If you could expand upon that just a little bit, the answer would be perfect! :] $\endgroup$ – hyperfekt May 22 '17 at 22:20
  • 1
    $\begingroup$ It causes at most $l-1$ items to be demoted, because there are $l-1$ levels less than $l$ and a given level has at most one demoted item. $\endgroup$ – rici May 22 '17 at 22:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.