Robert Kern wrote:
> [numpy implementation snipped]
> Ed Schofield has an implementation of an algorithm by Marsaglia[1] which turns
> sampling into a fast table lookup. If your probabilities have limited
> precision
> (2**-30 or so rather than the full double precision 2**-52 or so), then this
For your example, since the probabilities are all multiples of 0.01 you
could make a list of 100 elements. Set one of them to a, 5 of them to
b, 50 of them to c, etc. Then just randomly sample from the table
(which is O(1)). Of course if the probabilities can be arbitrary
floating point values the
Brian Quinlan wrote:
> The fastest algorithm that I have been able to devise for doing so is:
> O(n * log(len(lst))). Can anyone think or a solution with a better time
> complexity? If not, is there an obviously better way to do this
> (assuming n is big and the list size is small).
numpy.searc
"Paddy" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]
> Brian Quinlan wrote:
>> This is less a Python question and more a optimization/probability
>> question. Imaging that you have a list of objects and there frequency in
>> a population e.g.
>>
>> lst = [(a, 0.01), (b, 0.05), (c,
Brian Quinlan wrote:
> This is less a Python question and more a optimization/probability
> question. Imaging that you have a list of objects and there frequency in
> a population e.g.
>
> lst = [(a, 0.01), (b, 0.05), (c, 0.50), (d, 0.30), (e, 0.04), (f, 0.10)]
>
> and you want to drawn n items fro
Brian Quinlan wrote:
> The fastest algorithm that I have been able to devise for doing so is:
> O(n * log(len(lst))). Can anyone think or a solution with a better time
> complexity? If not, is there an obviously better way to do this
> (assuming n is big and the list size is small).
If list is
Brian Quinlan wrote:
> This is less a Python question and more a optimization/probability
> question. Imaging that you have a list of objects and there frequency in
> a population e.g.
>
> lst = [(a, 0.01), (b, 0.05), (c, 0.50), (d, 0.30), (e, 0.04), (f, 0.10)]
>
> and you want to drawn n items f
This is less a Python question and more a optimization/probability
question. Imaging that you have a list of objects and there frequency in
a population e.g.
lst = [(a, 0.01), (b, 0.05), (c, 0.50), (d, 0.30), (e, 0.04), (f, 0.10)]
and you want to drawn n items from that list (duplicates allowed
