Maybe off-topic, but thanks for putting what tools you used to do your illustrations with, always happy to see what people are using for that.
Skip Lists Done Right
61–70 of 87 posts
Re: Skip Lists Done Right
#62What framework are you using to publish the blog?
Footer says that Hugo is being used.
Re: Skip Lists Done Right
#63What framework are you using to publish the blog?
Looks like Hugo[1] running the Bleak[2] theme.
[1] http://gohugo.io/
[2] https://github.com/zenithar/hugo-theme-bleakRe: Skip Lists Done Right
#64Earlier quoted context omitted.
what's your method for quickly searching an ordered list? Binary search falls apart since you don't have free random access.
Skip lists allow for that, sort of. In Lisp, most people would just, you know, not use a list for that. You can do that, you know... The only reason I asked about lispers is that lispers really like lisps, and I was curious if any of them had implemented skip lists for some reason, and if so, how.
> ... just, you know ... you know ...
Yes, I know. Do you? You made the suggestion that skip lists are inferior to ordered lists, not me. (good for "increasing access times on ordered lists") I'm still perplexed as to your rationale for that statement.
Re: Skip Lists Done Right
#65While I really do like this article and the really interesting techniques it showed me, I'm bothered by the fact that they constantly mention performance but there's not a single benchmark on that page. It's not that I don't believe that these are huge theoretical gains, it's just that I'd like to see how these perform in practice compared to other approaches.
Re: Skip Lists Done Right
#66So my takeaway is that two main use cases for this DS are: 1: as an alternative to a distributed hash tables 2: as an alternative to a self-balancing tree such AVL tree etc. Are there any other common uses cases for skip lists?
Some memory allocators use them for tracking free blocks because insertions/removals are cheap and they're good at best-fit style searches.
Re: Skip Lists Done Right
#67I've read this page before, and again today, and I still don't understand how these unrolled lists are supposed to work in practice.
Based on the author's example at https://i.imgur.com/FYpPQPh.png, how do you take an unrolled skiplist that has a bottom row like this:
[1,2,3] -> [4,5,_] -> [7,8,9]
Re: Skip Lists Done Right
#68> 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?
http://dl.acm.org/citation.cfm?id=139478
http://www.cs.ucsb.edu/~ravenben/research/CS252/252Paper.pdf
I have an old implementation (in C) of paged, deterministic skip lists here:
Re: Skip Lists Done Right
#69Skip lists are a hidden gem! I first learned about them from a GitHub developer at OSCon a few years ago, and at time they seemed like black magic. It's a shame that universities (or at least mine) don't teach more interesting algorithms like this... it would make the algorithms/data structures coursework so much more interesting.
Illinois covers them.
Re: Skip Lists Done Right
#70Skip lists are probably the easiest way of getting O(log(n)) lookups on ordered lists. Recently I got rid of huge bottleneck on an oldish piece of software by moving from a vanilla linked list to a skip list. And I did do many things suggested in the article (e.g. having a vector of fixed length for the pointers, and thus a fixed tallness). Funnily enough, for my case, I managed to do without a RNG just fine. I just…
> Skip lists are probably the easiest way of getting O(log(n)) lookups on ordered lists. I wouldn't say that. The algorithms for AVL/red-black/splay trees are not especially complex, and they contain much less subtlety than skip lists. If you just look them up on wikipedia and see the list of operations, it's not particularly hard to implement them. Skip lists, on the other hand, are very easy to get wrong (this is t…
Binary search tree rotations are hard to implement correctly, but relatively easy to test that you have them right.
There are a lot of subtleties in any stochastic algorithm (like a skip list) that are much harder to correctly test.
While we're discussing "easy to implement" algorithms, I find Tries (aka radix trees) to be by far the easiest to implement for both ordered and unordered sets/maps. Naive implementations are very space inefficient though.