Hacker News Reader

Comment by barrkel | Hacker News Reader

    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.

View on HN

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 ;-)

> 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.

Not 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.

> 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=107462261140470234...

My 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.

why would you assume that the stdlib random number generator is worse than the few lines of code from numerical recipes?

At 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.

It's not that it's worse, it's the fact that is different for each platform.

it's a random number generator! you shouldn't be relying on any particular property other than that it passes the statistical tests for randomness.

You 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.

How? I thought about this for a while, but could not come up with a persistent version of skiplists.

Reply on news.ycombinator.com