There's a better way to do this, you use inverse CDF to avoid all the RNG calls.
Generate a random number, then skip items until you reach that number:
selectRandomFromIteratorOptimized(iterator)
{
if (!iterator.moveNext()) {
return null;
}
var winner = iterator.current();
var count = 1;
while (true) {
var u = random_float_open(0.0, 1.0);
var skip = (int)Math.Floor(Math.Log(u) / Math.Log(1.0 - (1.0 / (count + 1))));
for (var i = 0; i < skip; ++i) {
if (!iterator.moveNext()) {
return winner;
}
++count;
}
if (!iterator.moveNext()) {
return winner;
}
++count;
winner = iterator.current();
}
}
Back in the day, Windows OS kernel programming avoided use of floating point numbers - certainly transcendental functions would've been frowned upon - when CPUs didn't include an FPU.
I don't know if they've relaxed this since the days of non-FPU CPUs - anyone know? If they let the Weather app use a webview, there must be some floating point usage in there.
This code is at a much higher level though - at the user shell level, explorer.exe.
Anyways, asking Google's AI to remove the above code's use of floating point results in code resembling the original version.
Better in which way? It doesn't seem like the RNG is much of a bottleneck[0]. So this code is just more complicated than the original[1] IMO. It is also most likely more costly by involving a bunch of extra divs, logs and (for XP-level HW) floating points, though admittedly the bottleneck on XP-level HW was most likely still the disk.
Trying to best Windows devs on performance becomes almost comical if you read the comment for the RtlRandomEx:
it is faster than RtlRandom() since it saves one multiplication, one addition and
one modulus operation. This almost doubles the performance since it halves the number of
clocks even on a pipelined Integer Unit such as the P6/ia64 processors i.e. ~ 52% perf gain.
reply