Re: sorting by rand?

Peter Seebach wrote:
If the numbers that rand() generates are good enough, the chance of collisions preserving order should be the same as the chance of the next iteration of randomizing putting them back in the same order, shouldn't it?

I think not quite. Imagine a hypothetical pair of entities. They have a
1/bignum chance of a collision, which preserves their relative sorting.

If you do it twice, the probability that the same pair of entities collided
both times is 1/bignum^2. They might otherwise end up in the same order, or
not, but there's only a 1/bignum^2 chance that they ended up in the same
order *due to a collision*.

-s



You're right. I guess I'm just inclined to discount a such a small difference in orderings. And the difference in our benchmarks may have been due to the fact that I'm using a different algorithm (for each element i, swap i with an element from i...end). Or perhaps because I have more method calls, as I made a method Array#randomize! (that calls Array#swap! n times)

Dan

.

Relevant Pages

  • Re: sorting by rand?
    ... collisions preserving order should be the same as the chance of the next ... Imagine a hypothetical pair of entities. ... 1/bignum chance of a collision, ...
    (comp.lang.ruby)
  • Re: binary file compare...
    ... could you please accept that hashes collide and that no matter how many ... that guarantees a non-zero chance of corrupting your data. ... I'm just going to go ahead and take the above as an admission by you that the chance of collision is non-zero, and that if we accept that fact you cannot rely on a hash function to tell you if two files are identical. ...
    (comp.lang.python)
  • Re: Is MD5 outdated ?
    ... But I was searching for a 'statistical formula' ... > birthday on the same day of a year. ... chance of a collision reaches 50% when the number of people in the room ... possible "birthdays" so you need around 2**64 files to expect a collision. ...
    (sci.crypt)
  • Re: Transparent compression in the FS
    ... A mathematical proof for that is easy. ... > But those pushing this approach argue that the chance of collision is ... > less than the chance of hardware errors, ... send the line "unsubscribe linux-kernel" in ...
    (Linux-Kernel)
  • Re: Corner cutting
    ... Approaching the junction slowy to give the other driver more chance to spot ... you and give yourself more chance of avoiding the collision would be a ... Approaching slowy is indeed a useful ploy for avoiding conflict in these cases. ...
    (uk.rec.driving)