Also, I can confirm that unrolling skiplists makes them significantly more time and memory-efficient. I started working on a library for that (called “skiparray”; I was thinking of it as a B-Tree-like skiplist), but got sidetracked into working on the property-based testing library (theft) I was using to test it.
I haven’t figured out yet if it’s faster to unroll the skiplist into blocks of key/value pairs, or into only keys and forward pointers, and put all the values in a bottom layer (roughly analogous to B Trees vs. B+ Trees). It may be beneficial to store more keys and forward pointers per node, and group the bottom key/value pairs into a block with a different size than the upper layers.
It both amuses and pleases me that the code backing this article was written in Python :)
Everybody loves to rant and roar about it, but at the end of the day a lot of excellent work gets done despite the syntactic whitespace or whatever else your favorite hobby horse complaint is.
I have an ISC-licensed skiplist library for C.
Also, I can confirm that unrolling skiplists makes them significantly more time and memory-efficient. I started working on a library for that (called “skiparray”; I was thinking of it as a B-Tree-like skiplist), but got sidetracked into working on the property-based testing library (theft) I was using to test it.
I haven’t figured out yet if it’s faster to unroll the skiplist into blocks of key/value pairs, or into only keys and forward pointers, and put all the values in a bottom layer (roughly analogous to B Trees vs. B+ Trees). It may be beneficial to store more keys and forward pointers per node, and group the bottom key/value pairs into a block with a different size than the upper layers.
Surprisingly, there was another article about skip lists posted today.
It both amuses and pleases me that the code backing this article was written in Python :)
Everybody loves to rant and roar about it, but at the end of the day a lot of excellent work gets done despite the syntactic whitespace or whatever else your favorite hobby horse complaint is.