it has too high memory cost though, compared to float + binary search it scales larger than O(n)

its <= twice the size, not sure that really matters. I was also looking at

Fast Generation of Discrete Random Variables | Journal of Statistical Software

which seems memory optimal but was more complex

for simplicity I would go with a binary search approach, but that is cool

was curious what gpt5 thought: > Few items (n ≤ ~32) or few draws per build (draws ≤ ~10–20·n): use a prefix-sum + binary search. It’s tiny, obvious, and usually just as fast. > Many items and lots of samples from the same distribution (draws ≫ n): use Walker’s alias. It pays for itself and gives you flat O(1) sampling. > Weights change frequently: neither vanilla alias nor plain prefix-sums are ideal—use a Fenwick/segment tree (O(log n) updates & samples). maybe an ideal library like this would implement it as "Roaring Discrete Probability Distribution Sampling". although that doesn't roll off the tongue as much. The dynamic update thing is an interesting use case. There may be times where you need millions of samples really quick for some reason... maybe rolling unique drops for 1000s of players in a raid? For libraries its probably best not to assume how its being used and just go fast.

L00t

This algorithm is brilliant! So simple!