3 ms·
> 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-fa
by 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.