3 ms·

> 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 anyo

• mfukar 10y ago
  I initially thought it might be referring to deterministic skip lists (Munro, Papadakis, Sedgewick, http://www.ic.unicamp.br/~celio/peer2peer/skip-net-graph/deterministic-skip-lists-munro.pdf 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.
• mac01021 10y ago
  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.
• jabr 10y ago
  http://dl.acm.org/citation.cfm?id=139478 http://dl.acm.org/citation.cfm?id=139478 http://www.cs.ucsb.edu/~ravenben/research/CS252/252Paper.pdf http://www.cs.ucsb.edu/~ravenben/research/CS252/252Paper.pdf I have an old implementation (in C) of paged, deterministic skip lists here: https://github.com/jabr/olio/blob/master/skiplist.c https://github.com/jabr/olio/blob/master/skiplist.c https://github.com/jabr/olio/blob/master/skiplist.h https://github.com/jabr/olio/blob/master/skiplist.h