The Design of Software (CLOSED)

A public forum for discussing the design of software, from the user interface to the code architecture. Now closed.

The "Design of Software" discussion group has been merged with the main Joel on Software discussion group.

The archives will remain online indefinitely.

Skiplist datastructure

Hi guys
i m wondering if any of you guys have used a skiplist datastructure and, if you can share the performance issues of constructing and use Skiplists.

under which situations do we need skiplists
nvidia Send private email
Sunday, July 30, 2006
I have used a (modified) skiplist in one particular area of our application where we have a large range of keys that fit well into the skiplist model for our needs of looking up the information.

I say "modified" because I added a method that allows us to pull back the "closest on the low side" entry if no exact match is found because we need an entry that may cover a range of values, so an exact match key is not present.

For our data, the performance vastly improved with the skiplist because it really fit the lookup model we had.  We had far too many entries to do a linear scan and a hashtable model didn't fit for how we needed the "range" potential.

I really like it for its use, but I don't find myself needing it very often.
Sunday, July 30, 2006
Take a look at the latest edition of Sedgewick's Algorithms books - he does an analysis of the performance of skip-lists vs. other binary tree lookup structures.
Chris Tavares Send private email
Monday, July 31, 2006
In my experience, once you realize you need a skiplist or binary tree because it's the only thing that makes it possible to quickly locate a '*range* of items, it doesn't really matter which one you pick, at least not performance-wise.

They are all implemented the same way: a structure of nodes that point to each other, and the thing that *totally* dominates performance is cache misses, not how many cycles it takes to rebalance your favorite binary tree.

Monday, July 31, 2006
I went to the University of Maryland, where the inventor of the skiplist (Dr. Bill Pugh) is a tenured professor of computer science. My data structures professor (NOT Bill Pugh), when we got to the lecture on skiplists, had only this to say:

Q: What can a skiplist get you that you can't get with a hash table or binary tree?

A: A PhD.
Jeff Dutky Send private email
Tuesday, August 01, 2006

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
Powered by FogBugz