4 ms·
anorwell is right, I'm wrong: Actually, his technique is way faster (1 random generation per element, vs. log(n) or log(u)), but you're absolutely right, you n
by leif 16y ago
anorwell is right, I'm wrong:
Actually, his technique is way faster (1 random generation per element, vs. log(n) or log(u)), but you're absolutely right, you need to take the higher order bits first or your skiplist will be very far from correct.
(P.S. I'd love to have you reviewing my code ;-)
- anorwell 16y ago> 1 random generation per element, vs. log(n) or log(u) The expected height of an element is 2, and the maximum height is 32. So there is at most a constant-factor performance difference, and in practice we should find this constant to be small. It's not clear whether any small performance gain is worth the loss of clarity in presentation of the algorithm and code.
- Xk 16y agoNot only that, but if you were to write this in (say) Java, which uses a linear congruential random number generator, doing it this way would probably be even faster due to the higher quality random numbers. The least significant bits on a linear congruential generator aren't terribly random.