So my takeaway is that two main use cases for this DS are:
1: as an alternative to a distributed hash tables
2: as an alternative to a self-balancing tree such AVL tree etc.
Are there any other common uses cases for skip lists?
Skip Lists Done Right
31–40 of 87 posts
Re: Skip Lists Done Right
#32Earlier quoted context omitted.
It is also very handy if you need to flatten a small (< 2 kg) household pet.
It would be bad to have a book about multiple trees which implemented less than 1 tree in its printed form.
Implemented? I don't think it implements tree, so much as inherits from tree.
Re: Skip Lists Done Right
#33Looks like I already do pretty much all those things in twoskip: https://blog.fastmail.com/2016/12/03/cyrus-databases-twoskip... (except for the level choice. Which is a bit meh to me, because a write will probably trigger 3 fsyncs, so the cost of level choice is very low) That said, my next DB won't have any skiplists in it I don't think, or at most an in-memory one, but not on disk.
>That said, my next DB won't have any skiplists in it I don't think, or at most an in-memory one, but not on disk. What will you use instead (and why)?
Adding to rawnlq's comments:
Disk access (reads and writes) still happen in chunks, even with SSDs. It's much more efficient to write entire chunks of data out than to write a few hundred bytes over a dozen different chunks.
The requirements for writing out a B-Trees to disk is in line with writing out chunks of data, which makes them very popular (and performant) with database implementations.
And this doesn't cover how performant CPUs are at performing operations over a contiguous list of data. The complexity may be O(n), but the implementation introduces a fractional constant which can outperform a O(log(n)) algorithm which involves cache misses.
Re: Skip Lists Done Right
#34Earlier quoted context omitted.
It is also very handy if you need to flatten a small (< 2 kg) household pet.
I always say college was very practical learning as at different points in time I was able to kill a mouse with both algorithms (this very book) and computer architecture.
It took you 2 books to kill 2 mice, but I'm sure with more observations it would have been obvious that your approach was actually O(logN).
Re: Skip Lists Done Right
#35Skip lists are a hidden gem! I first learned about them from a GitHub developer at OSCon a few years ago, and at time they seemed like black magic.
It's a shame that universities (or at least mine) don't teach more interesting algorithms like this... it would make the algorithms/data structures coursework so much more interesting.
Re: Skip Lists Done Right
#36Archived: https://archive.fo/H7F9e
The site doesn't work without scripts and trips up links2, so you can use the archive link instead (it works without scripts).
Re: Skip Lists Done Right
#37Skip lists are probably the easiest way of getting O(log(n)) lookups on ordered lists. Recently I got rid of huge bottleneck on an oldish piece of software by moving from a vanilla linked list to a skip list. And I did do many things suggested in the article (e.g. having a vector of fixed length for the pointers, and thus a fixed tallness). Funnily enough, for my case, I managed to do without a RNG just fine. I just…
> Skip lists are probably the easiest way of getting O(log(n)) lookups on ordered lists. I wouldn't say that. The algorithms for AVL/red-black/splay trees are not especially complex, and they contain much less subtlety than skip lists. If you just look them up on wikipedia and see the list of operations, it's not particularly hard to implement them. Skip lists, on the other hand, are very easy to get wrong (this is t…
I did a brief survey before deciding to go with skip lists, and found them to be easier to grasp and reason about.
(e.g. there is no need to balance trees; a skip list is very similar to a linked list, and linked lists are very simple).
I remember somebody saying that "in a sane world skip lists would always have been discovered before red-black trees".
This historical accident (skip lists were only discovered 1989; while rb-trees date back to the 1970s) is probably the reason why skip list use is not more widespread, and seen as somewhat exotic at times.
(AVL and Splay-trees also predate skip lists.)
Re: Skip Lists Done Right
#38Skip Lists. Seem handy for increasing access times on ordered lists...
Any Lispers care to comment?
Re: Skip Lists Done Right
#39The pseudocode + example given for the initial implementation of 'insert' doesn't seem right, no 'below' connection is made between the two '13' nodes.
The way to fix this would be to let 'insert' return the node inserted at the given level. There already are a few returns in the 'insert' pseudocode right now, but it doesn't seem like anything is being returned right now.
Something like this:
-- Recursive skip list insertion function.
define insert(elem, root, height, level):
if right of root define insert(elem, root, height, level):
if right of root height:
return insert(elem, below root, height, level - 1)
else:
new ← makenode elem
old ← right of root
right of root ← new
right of elem ← old
if level > 0:
below new ← insert(elem, below root, height, level - 1)
return newRe: Skip Lists Done Right
#40Skip lists are a hidden gem! I first learned about them from a GitHub developer at OSCon a few years ago, and at time they seemed like black magic. It's a shame that universities (or at least mine) don't teach more interesting algorithms like this... it would make the algorithms/data structures coursework so much more interesting.
WUSTL does teach Skip List. We spent a good two weeks learning about it. Intro, analysis, lab, test about Skip List. It's very cool and hard to get right.