> Together we came up with a solution that solves this with O(n) memory usage where n is the number of choices, and O(log n) CPU cost. And it allows you to decide if you want to be more random or more deterministic.
I think you can do the same thing and solve all the same problems in O(1) time per sample using the alias method plus shuffling while blending between regular uniform samples and jittered uniform samples.
- Build your alias map of M buckets, the distribution you want to sample
- Take a set of N uniform samples, and use a knob to blend between regular and jittered. It looks like:
r=lerp(knob, 0.5, rand())/N
- Shuffle the uniform samples, e.g. std::random_shuffle(). This can be done incrementally, per sample (https://en.wikipedia.org/wiki/Fisher–Yates_shuffle).
- Plug the uniform sample into the alias map to find your sampled choice.
- Repeat when you run out of the N uniform samples.
https://en.wikipedia.org/wiki/Alias_method
http://www.keithschwarz.com/darts-dice-coins/
I think you can do the same thing and solve all the same problems in O(1) time per sample using the alias method plus shuffling while blending between regular uniform samples and jittered uniform samples.
- Build your alias map of M buckets, the distribution you want to sample
- Take a set of N uniform samples, and use a knob to blend between regular and jittered. It looks like: r=lerp(knob, 0.5, rand())/N
- Shuffle the uniform samples, e.g. std::random_shuffle(). This can be done incrementally, per sample (https://en.wikipedia.org/wiki/Fisher–Yates_shuffle).
- Plug the uniform sample into the alias map to find your sampled choice.
- Repeat when you run out of the N uniform samples.
https://en.wikipedia.org/wiki/Alias_method
http://www.keithschwarz.com/darts-dice-coins/