fastest method to choose a random element

[ajaksu]

Hi there :)

On Jan 5, 2:14 pm, c... at mailinator.com wrote:
> On Jan 5, 5:07 pm, c... at mailinator.com wrote:
>
> > Hello, Paul and Arnaud.
> > While I think about your answers: do you think there is any way to
> > avoid shuffle?
> > It may take unnecessary long on a long list most of whose elements
> > have the property.

I've been thinking about this one before you asked and only got a bad
solution: you don't need to shuffle the list if you can construct a
random list of indexes to loop through, but my timings show that I
can't do that faster than "shuffle(range(x))" for worst cases (i.e.,
iterate thru the whole list) :)

The rather good news is that shuffling a list of arbitrary objects is
pretty fast (as compared to a list of integers).

OTOH, if you do know that the chances are high enough, you can try
choosing items randomly without substitution (adapted from random.py's
sample):

from random import random

def randpickuntil(lst, prop=bool):
    selected = set()
    for i in xrange(len(lst)):
        j = int(random() * n)
        while j in selected:
                j = int(random() * n)
        if prop(lst[j]):
            return lst[j]
        selected_add(j)


> Umm...
> You provide nice answers in the case many elements are picked from the
> same list.
> Any ideas for the case when the picker is called many times on a
> program, but never twice with the same list?

If the lists share items, a cache could help a lot. Otherwise, you'd
benefit more from finding a good way to test the property (could you
give a hint on what it is?). How do objects acquire that property, is
it a sum of independent factors?

HTH,
Daniel