A public forum for discussing the design of software, from the user interface to the code architecture. Now closed.
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
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.
Tuesday, August 01, 2006
This topic is archived. No further replies will be accepted.Other recent topics
Powered by FogBugz