Code Review (Skip List)

[CBFalconer]

Dr Chaos wrote:
.... snip ...

Yes, but this particular application (skip lists) does not really
require an exceptionally good random mantissa. Simplistic
pseudo-random generators usually perform very well.

I fail to see any reason for the existence of skip-lists, since
access is much slower than hash tables, and any hash table can be
walked and made into a list (including a skip-list) on demand.
The result can then be merge-sorted in O(nLOGn) on any field(s)
desired. What am I missing?

 

[Ben Pfaff]

I fail to see any reason for the existence of skip-lists, since
access is much slower than hash tables, and any hash table can be
walked and made into a list (including a skip-list) on demand.
The result can then be merge-sorted in O(nLOGn) on any field(s)
desired. What am I missing?

You're missing that for some applications is useful to be able to
traverse a list in sorted order and modify the list, keeping it
in sorted order, at the same time. Neither a hash table nor a
sorted list is ideal for such applications: a hash table cannot
be efficiently traversed in sorted order and a sorted list cannot
be efficiently modified in sorted order. The paper on binary and
balanced trees available from my website at
http://benpfaff.org/papers describes two such applications; skip
lists can be used for the same applications, but I have not
implemented them (yet).

 

[Andrey Tarasevich]

I fail to see any reason for the existence of skip-lists, since
access is much slower than hash tables, and any hash table can be
walked and made into a list (including a skip-list) on demand.
The result can then be merge-sorted in O(nLOGn) on any field(s)
desired. What am I missing?
...

As you already noted yourself, hash-based containers do not immediately
impose any meaningful ordering on the stored sequence of elements. Skip
lists do. Sorted sequences have many useful applications besides
implementing look-up tables.

Performing an additional sorting step on hash table (as you suggested
above) is, of course, completely unacceptable in virtually any
application that needs to maintain a sorted sequence in on-line mode.

 

[CBFalconer]

As you already noted yourself, hash-based containers do not
immediately impose any meaningful ordering on the stored sequence
of elements. Skip lists do. Sorted sequences have many useful
applications besides implementing look-up tables.

Performing an additional sorting step on hash table (as you
suggested above) is, of course, completely unacceptable in
virtually any application that needs to maintain a sorted
sequence in on-line mode.

I see. In many cases the optimum would be to insert the item in
both the skip-list and the hash table. Of course a combination
hash/red-black tree might perform the same function. The
skip-list would be better when the predecessor is needed.

Please don't remove attributions for quotations you leave
unsnipped.

 

[Charles Richmond]

I fail to see any reason for the existence of skip-lists, since
access is much slower than hash tables, and any hash table can be
walked and made into a list (including a skip-list) on demand.
The result can then be merge-sorted in O(nLOGn) on any field(s)
desired. What am I missing?

The same might be said of AVL trees...or given AVL trees, why
do we need Red-Black trees??? I suppose that some folks feel
more comfortable with balanced trees than with hash tables...

I personally found skip-lists to be interesting...even though
I have *never* used them in a project of any sort.

--
+-------------------------------
| Charles and Francis Richmond
| richmond at plano dot net
| Re-Defeat Bush!!!
+-------------------------------