Re: "hat" container class [C++]

From: Kai-Uwe Bux (jkherciueh_at_gmx.net)
Date: 07/17/04 

Date: Sat, 17 Jul 2004 00:34:16 -0400

AngleWyrm wrote:

> "AngleWyrm" <no_spam_anglewyrm@hotmail.com> wrote in message
> news:YwLHc.60533$Oq2.12929@attbi_s52...
>> "Kai-Uwe Bux" <jkherciueh@gmx.net> wrote in message
>> news:cbr39k$f4u$1@news01.cit.cornell.edu...
> > 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.
>

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

Relevant Pages

  • FA: France kiloware COMMEMORATIVE with 2007 + HV
    ... Up for auction on ebay, ... weights 100 grams. ... Great selection, low duplication. ...
    (rec.collecting.stamps.marketplace)
  • Re: Problem on an nxn grid
    ... This is actually for the "minimum-weight matching" ... problem, with all non-negative weights. ... Sum this selection and call it ts_max. ... (such as rejecting the first weight out of hand) ...
    (sci.math)
Loading