6
$\begingroup$

Skip lists are taught as a standard of the undergrad CS curriculum at many major universities. However, from my reading* I can't find any practical situation where you would use a skip list over a treap. Also they have the same asymptotic performance for all the main operations.

As a result this left me wondering:

Should you ever choose a skip list over a treap?

*A few web links that suggest that treaps are faster in practice or a just very fast in practice.

http://pinporelmundo.blogspot.co.uk/2011/06/skip-lists-compared-with-treaps-and-red.html https://stackoverflow.com/a/16009599/2179021 https://stackoverflow.com/a/18303163/2179021

and here is a link suggesting that skip lists are almost never useful

https://www.quora.com/Why-arent-skip-lists-used-more-often-instead-of-balanced-trees

$\endgroup$
  • $\begingroup$ In which situation? Which cost measures are of interest? Which operations are used most often? "Same asymptotic performance" (I guess you mean "Big-Oh") is an awfully coarse measure! $\endgroup$ – Raphael Oct 29 '15 at 17:39
  • $\begingroup$ @Raphael That's really the question. In what situation would you choose skips lists over treaps? $\endgroup$ – Lembik Oct 29 '15 at 17:41
  • $\begingroup$ I guess my issue the then that a) your question is broad, b) it admits trivial answers (e.g. "the treap implementation I have is awful") and c) we don't know what kinds of scenarios you are willing to accept. $\endgroup$ – Raphael Oct 29 '15 at 17:44
  • $\begingroup$ @Raphael Let's at least assume the implementations are good! If there are really no obvious or common scenarios in which one should use a skip list then that is itself very interesting. $\endgroup$ – Lembik Oct 29 '15 at 17:46
  • $\begingroup$ Related chat discussion starting here. $\endgroup$ – Raphael Oct 29 '15 at 18:21
1
$\begingroup$

here is an extensive 13 page analysis of considerations in this area including empirical analysis. coders sometimes ask for "one size fits all" answers. of course "best" implementation depends on the actual "forces" applied on the implementation. a single implementation may even behave ("dramatically") differently on different amounts of data and different conditions. for some data structures there is no significant difference and either can be acceptable.

raw performance is not the only factor. factors might involve how hard it is to implement/ test the structure vs whether it is already implemented etc. and this paper also considers caching considerations effect on performance. this research finds that skip lists have good variable-node-size performance (ie not all nodes have same size) and paged skip lists outperforms B+-trees in their case.

see p7 and fig6 p 10.

The AVL tree is the best performing fixed-node-size data structure, and the paged skip list is the best performing variable-node-size data structure. Moreover, the gap between the cache-conscious data structures and their counterparts is growing, as shown by the 100 cycle memory latency configuration. The paged skip list outperforms the sequential search B+-tree by 12% on the Intel processor.

$\endgroup$

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.