Random numbers [LWN.net]

Random numbers

Posted May 16, 2020 13:24 UTC (Sat) by mathstuf (subscriber, #69389)
In reply to: Random numbers by martinfick
Parent article: The weighted TEO cpuidle governor

If you have 4 each around 20%-30%, sure. But if you have a fifth at 1%, probably not. Wouldn't it be more expensive to detect the first case and handle it specially than to just handle the general case?

to post comments

Random numbers

Posted May 16, 2020 19:33 UTC (Sat) by Wol (subscriber, #4433) [Link] (2 responses)

Or just randomly select any one over average. So if you've got 8, randomly select any of those over 13%

Cheers,
Wol

Random numbers

Posted May 16, 2020 20:18 UTC (Sat) by mathstuf (subscriber, #69389) [Link] (1 responses)

That still seems to pessimize a bit too much to me. If you have all of them right around 12.5%, why use a selection algorithm that makes half (on average) effectively 0%? Instead of introducing a divide for your average, just track the sum, make a random number within [0, sum) (any other scheme is likely to have something here anyways to get a number within your domain), then subtract off each bucket's size until you get a value < 0 and you've found your selection. Tracking is then just counting into each bucket and the sum and you reweight to avoid overflows every so often. Reweighting after each measurement seems excessively expensive.

Random numbers

Posted May 16, 2020 22:30 UTC (Sat) by Wol (subscriber, #4433) [Link]

If your scheme is quicker than mine at doing the calculation, then fine. I was just thinking that less than half the choices would be above average (and the more widely spread the scores are, the smaller the above-average proportion). So if you want one of the high-rankers, at random, just grabbing anything above average isn't a bad way of doing it.

Cheers,
Wol