"hat" container class [C++]

[AngleWyrm]

Thus, the problem that you really want to solve is this:
Given a weights on a finite set, realize a datastructure that allows for
constant time generation of a random element in the set with probability
distribution defined by the given weights.

Example: Set { a, b, c } weights: w(a) = 5, w(b)=12, w(c)=9.

We want a fast algorithm that yields a with probability 5/25, b ....

In the 1970s, J.A. Walker came up with the following idea. I will explain
it for the example above. Consider the following table:

After some study of both J.A. Walker's alias method (ACM p253, An Efficient
Method For Generating Discrete Random Variables With General Distribution), and
Donald Knuth's implementation of the table generation method(TAOCP vol 2,
seminumerical algorithms, p.550), it seems that this technique is very efficient
when the probability distribution is fixed before selection. This addresses a
large subset of uses, but leaves out a particular class of problem...

In the case where the distribution changes dynamically as choices are added to
or removed from the set, the above technique must recalculate a lookup table for
each insert/delete operation, a linear-time operation. Examples of this problem
space are: Drawing weighted lottery balls, random selection from a changing
client list, or an estimation by successive approximation.

 

[Kai-Uwe Bux]

After some study of both J.A. Walker's alias method (ACM p253, An
Efficient Method For Generating Discrete Random Variables With General
Distribution), and Donald Knuth's implementation of the table generation
method(TAOCP vol 2, seminumerical algorithms, p.550), it seems that this
technique is very efficient when the probability distribution is fixed
before selection. This addresses a large subset of uses, but leaves out a
particular class of problem...

In the case where the distribution changes dynamically as choices are
added to or removed from the set, the above technique must recalculate a
lookup table for each insert/delete operation, a linear-time operation.
Examples of this problem space are: Drawing weighted lottery balls, random
selection from a changing client list, or an estimation by successive
approximation.

Yup, updating the magic table for Walker's method is unfortunately linear
time. On the other hand, for the more general problem, you already have a
solution where all orperations are O(log(n)) time: generating a random
variable, adding / deleting an option, and changing a weight. It is tricky
to do better than O(log(n)), and might not be worth the effort since the
set of options has to be *really* big to take advantage of the asymptotic
improvement.

Somewhere up in this thread, I got the impressiont that you were now
searching for an add-on that would provide increased performance for the
special case of a fixed set of options with non-changing weights.


Best

Kai-Uwe Bux