Even Random Distribution vs Weighted Random Distribution

Weighted_random_distribution.md

Origin artical

This is just for personal memorial use.

Given a map X = { A: 2, B: 4, C: 1, D: 3 }

By randomly choosing one charactor, we want ABCD appears according to their weight. It means B appears two times than A.

Solution

1. Expanding

One of the easiest solutions is to simply expand our set so that each entry in it appears as many times as its weight.

X -> [A,A,B,B,B,B,C,D,D,D]

2. In-place(Unsorted)

Sum all weights, and randomly pick from 0 to totalWeight-1 as wRandom, then we loop the given map and add each element's weight as wTarget untill it is greater than xRandom, then we get the target value we want

wRndNr = random.randint(0, wTotal - 1)
s = 0
for w in weights.items():
        s += w[1]
        if s > wRndNr:
                break;

3. In-place(Sorted)

Instead of adding from head to end, but substracting the number backward.

4. Pre-calculate

Conclusion

If you need speedy selections

• Use expanded if the number of items in your set is low, and your weights are not very high.

• Use pre-calculated if your set has lots of numbers and/or your weights are high.

If you need speedy updates

• Use in-place (unsorted) for the fastest updates.

• Use in-place (sorted) for somewhat slower updates and somewhat faster selections.

If you need low memory usage

• Don't use expanded.

• If you need simplicity

• Use expanded or in-place (unsorted).