[HN Gopher] Let's Talk SkipList
___________________________________________________________________
Let's Talk SkipList
Author : signa11
Score : 52 points
Date : 2022-08-07 06:08 UTC (16 hours ago)
(HTM) web link (ketansingh.me)
(TXT) w3m dump (ketansingh.me)
| slyrus wrote:
| ISTR SkipLists being used by the NCBI toolkit for DNA/AA sequence
| data way back in the day. Of course now I can't find any
| reference to it, but did find this paper on SkipLists in multiple
| alignments from 2003:
|
| https://www.ncbi.nlm.nih.gov/pmc/articles/PMC521198/
| vvern wrote:
| CockroachDB uses a skip list for its "timestamp cache" data
| structure, used to implement serializable isolation. The data
| structure records reads and exists to ensure that writes cannot
| rewrite history.
|
| This[1] library is the basis of the implementation in the
| database.
|
| [1] https://github.com/andy-kimball/arenaskl
| nfgrep wrote:
| I remember implementing a skip-list in order to do some hacky
| ray-casting on the GPU. Pretty significant performance
| improvement, and fun to implement!
| nfgrep wrote:
| Actually, the "skip list" I implemented wasn't as general as
| the ones talked about here. I had the "skips" pre-computed at
| specific intervals to skip sometimes huge numbers of entries,
| sometimes just a few, it wasn't equally distributed. Didn't
| know there was a more general implementation, neat!
| KerrAvon wrote:
| Cold take:
|
| I remain unconvinced that skiplists cannot be better replaced in
| most cases with a good hash table/dictionary implementation.
|
| Also, most linked lists should actually be deques.
| dreamcompiler wrote:
| A skip list is an ordered data structure with lookup time
| O[logn]. Hash tables are unordered, with lookup time O[1]. They
| serve different purposes.
| PotatoPancakes wrote:
| > I remain unconvinced that skiplists cannot be better replaced
| in most cases with a good hash table/dictionary implementation.
|
| Skiplists are ordered. Perhaps without much advantage compared
| to, say, a balanced BST. But Hash tables aren't ordered, so
| they aren't as good for storing data when preserving order is
| important.
|
| > Also, most linked lists should actually be deques.
|
| Yep, for almost all purposes, so long as using the extra memory
| for the reverse pointers isn't an issue. Deques are more
| flexible and much easier to work with (and especially to debug)
| than singly-linked lists. Not much of a take, I think a large
| proportion of developers would vehemently agree with you there.
| anfelor wrote:
| There is also a nice new datastructure called Zip Trees [1] which
| is isomorphic to skip lists in the sense that it performs exactly
| the same comparisons on insertion/deletion (but it can skip some
| redundant ones). I would expect zip trees to be faster than skip
| lists in practice.
|
| [1]: https://arxiv.org/abs/1806.06726
| rektide wrote:
| Go Terps (University of Maryland, College Park)! First described
| by Bill Pugh in 1989.
| mbfg wrote:
| Is it me, or does the post not explain what the benefits are of a
| skiplist? Ok, maybe it's just "a here's how to implement" post,
| but seems strange.
| killingtime74 wrote:
| You're right it didn't. I believe the main benefit vs binary
| search in arrays is that it's linked list like nature makes
| insertion and removal Faster
___________________________________________________________________
(page generated 2022-08-07 23:01 UTC)