Hacker Newsnew | comments | show | ask | jobs | submitlogin

Exactly. Skip lists are great for two reasons (and as far as I know, only these two reasons):

1. They're really cool and clever. This is a valid reason.

2. They offer easier concurrency than most alternatives. It's straightforward (though not quite easy, unless you have transactional memory) to make a lock-free concurrent skip list. Try that with a heap or a red-black tree, and you'll quickly run into all sorts of memory conflicts and crazy-complicated locking. The fact that a skip list only provides probabilistic logarithmic time bounds really makes coordination between threads easier.

(Note that it's possible to do some similar stuff with modified versions of other data structures. For example, you can make a good concurrent dictionary by taking a red-black tree, relaxing the invariants, and adding a periodic rebalancing thread to run in the background. But that's a topic too long to fit into this post.)




I think the biggest advantage of skip lists is that if a man held a gun to my head and forced me to implement a logarithmic time algorithm I could implement skip lists in an hour or so from memory. Any of the others...maybe given a week and a couple of good books.

-----


  ... if a man held a gun to my head and forced me
  to implement a logarithmic time algorithm I could
  implement skip lists in an hour or so ...
Does this happen to you often?

-----




Applications are open for YC Summer 2015

Guidelines | FAQ | Support | Lists | Bookmarklet | DMCA | Y Combinator | Apply | Contact

Search: