6 ms·
for (int R = _rand.Next(); (R & 1) == 1; R >>= 1) For C# on .NET, this may work fine, but in general, this is a bad way of extracting a 0/1 choice from a pseud
by barrkel 16y ago
for (int R = _rand.Next(); (R & 1) == 1; R >>= 1)
For C# on .NET, this may work fine, but in general, this is a bad way of extracting a 0/1 choice from a pseudo-random number generator (PRNG). Many PRNGs use linear congruential generators, which are just a multiply and an add, and have highly predictable low bits as a result (frequently just a repeating pattern with a short period, as short as 4 or 8).
Safer:
while (_rand.Next(2) == 0)
- or even simply reading the bits off the other end.
Another nice thing about skip lists is that they are relatively easy to make into cheap persistent structures (aka functional structures), that is, structures where operations return a new immutable copy of the structure, but share most of the substructure with the previous version.
- leif 16y agoanorwell 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.
- jbapple 16y ago> Another nice thing about skip lists is that they are relatively easy to make into cheap persistent structures (aka functional structures), that is, structures where operations return a new immutable copy of the structure, but share most of the substructure with the previous version. The simplest purely functional balanced dictionary structures I am aware of are 2-3 trees, which are actually another way of viewing 1-2 skip lists, a deterministic variant of skip lists! http://scholar.google.com/scholar?cluster=10746226114047023400 http://scholar.google.com/scholar?cluster=107462261140470234...
- eru 16y ago> Another nice thing about skip lists is that they are relatively easy to make into cheap persistent structures (aka functional structures), that is, structures where operations return a new immutable copy of the structure, but share most of the substructure with the previous version. How? I thought about this for a while, but could not come up with a persistent version of skiplists.
- martincmartin 16y agoMy take is to never trust the built-in random number generator of any standard library. Get a copy of Numerical Recipes and implement your own, it's only a few lines of code.
- zem 16y agowhy would you assume that the stdlib random number generator is worse than the few lines of code from numerical recipes?
- malkia 16y agoIt's not that it's worse, it's the fact that is different for each platform.
- zem 16y agoit's a random number generator! you shouldn't be relying on any particular property other than that it passes the statistical tests for randomness.
- zinkem 16y agoYou need to be able to re-create your inputs if a problem occurs. You need to be able to seed a random number generator and have it generate the same sequence for debugging.
- jerf 16y agoAt least then you know which one it is, what properties it has, and how it is initialized. Too few random number libraries document this. But as that is the primary advantage my gut would be to still at least use a library. It's not hard to come up with a Mersenne Twister library, and if you need something cryptographically secure just about the only thing I'd even consider is going straight to the OpenSSL implementation.