Random numbers
Random numbers
Posted May 16, 2020 20:18 UTC (Sat) by mathstuf (subscriber, #69389)In reply to: Random numbers by Wol
Parent article: The weighted TEO cpuidle governor
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.
Posted May 16, 2020 22:30 UTC (Sat)
by Wol (subscriber, #4433)
[Link]
Cheers,
Random numbers
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.
Wol