> Ever implemented a balanced binary tree? Me neither, seems a pain! Red-Black, AVL, rotation, uncles/aunts, balance factors, sub-trees - that's a lot to keep track of.
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.
Meh. I feel like too often us nerds & certain authoritarian tendencies often expressed there-in have a hard on for 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.
The argument wasn't "avoid randomized algorithms", the argument was "be forthcoming about the tradeoffs so your reader can understand the world and make an informed decision".
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.
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.