fastest method to choose a random element

Carl Banks pavlovevidence at gmail.com
Sat Jan 5 22:15:16 CET 2008


On Sat, 05 Jan 2008 08:14:46 -0800, caca 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.
> 
> 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?

ISTM the best thing would be to reimplement the shuffle algorithm, but to 
stop shuffling as soon as you get a hit.  The drawback is that it's a 
destructive operation, but that doesn't sound like it's an issue for you.

Here's something for starters:

def random_element_with_property(x,test_property_func):
    for i in xrange(len(x)-1):
        j = random.randrange(i+1,len(x))
        tmp = x[j]
        if test_property_func(tmp):
            return tmp
        x[j] = x[i]
        x[i] = tmp
    return None


Then, for example, use it like this:

def odd(i): return i&1
e = random_element_with_property(range(20),odd)



Carl Banks



More information about the Python-list mailing list