2 ms·
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: selectR
by nerdo 21d ago
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();
}
}
- canucker2016 21d agoBack 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.
- amag 21d agoBetter 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. [0]: https://github.com/tongzx/nt5src/blob/daad8a087a4e75422ec96b7911f1df4669989611/Source/XPSP1/NT/base/ntos/rtl/random.c#L120 https://github.com/tongzx/nt5src/blob/daad8a087a4e75422ec96b... [1]: https://github.com/tongzx/nt5src/blob/daad8a087a4e75422ec96b7911f1df4669989611/Source/XPSP1/NT/shell/shell32/userpict.cpp#L458 https://github.com/tongzx/nt5src/blob/daad8a087a4e75422ec96b...