Implementing and Improving Skiplists
mattjhall.co.uk
mattjhall.co.uk
Yeah, because they give you pretty darn strong deterministic guarantees.
> Luckily the world of computer science has a data structure that is far easier to implement and has similar properties: the skiplist.
It's far easier to implement... and it doesn't provide the same guarantees.
Statistics won't promise us reliable results, but skiplists are such an excellent wonderful miraculous algorithm that delivers such excellently fast & quick results. The more data you have the less likely you all hit any actually bad probabilities.
Thanks Bill Pugh for freeing computer science from the clutches of computing absolutists, for opening a door to beyond.
Note that determinism isn't necessarily about avoiding "bad probabilities". It's about the same programing producing the same output for the same inputs. The moment you start introducing nondeterminism (whether random or not), you start having that much of a harder time debugging what the hell went wrong in your program. And you start to undermine the whole reproducibility effort that's been going on the past decade.
Which... may be fine, for your use case. But the point is there's a very real trade-off and it's not just theoretical. You need to actually think about it and make sure your audience knows the trade-off, instead of brushing it under the rug. If you want to lose the guarantee, that's fine -- but it needs to be a conscious decision, not done out of ignorance (And the comparison to "absolutists" or "authoritarians" is incredibly unwarranted and unconstructive here.)
Record the seed for all RNGs used (if you’re using more than one for your SkipList implementation) and then your Skip lists are no more harder to debug than a linked-list.
Again: the point of the comment wasn't "tell people not to do this", it was "give people enough information to make an informed decision".
Is it winter yet?
Yes. Somewhere