News for hackers. Stuff that matters.
Re:Skip Lists Done Right by qznc on Monday December 19, 2016 @06:53AM (#13210856)
> I can't seem to find my favorite trick: deterministic (ie. without rng) skipping by linking on traversal instead of insert/delete.

Says one comment. Can anyone explain that?

Re:Skip Lists Done Right by jabr on Monday December 19, 2016 @05:59PM (#13215758)
Re:Skip Lists Done Right by mac01021 on Monday December 19, 2016 @08:19AM (#13211175)
It sounds like they mean that, if you have all the data you want for your skiplist and all you need going forward is a read-only data structure for doing lookups, then you can put your data in order in a regular list and then build up the towers of skip links in deterministic fashion to get an optimally balanced distribution.

Doesn't seem like much of a trick, though. If you can do that, then you can just stick it all in an array and bsearch to find things.

Re:Skip Lists Done Right by mfukar on Monday December 19, 2016 @07:49AM (#13211070)
I initially thought it might be referring to deterministic skip lists (Munro, Papadakis, Sedgewick, http://www.ic.unicamp.br/~celio/peer2peer/skip-net-graph/det...), but the "linking on traversal" part stumps me. Maybe it's referring to the top-down approach in section 3 of the paper.