fastest method to choose a random element

[Neil Cerutti]

On Jan 4, 2008 3:47 PM, Neil Cerutti <mr.cerutti at gmail.com> wrote:

> On Jan 4, 2008 2:55 PM, <caca at mailinator.com> wrote:
>
> >  Hello,
> >  This is a question for the best method (in terms of performance
> > only) to choose a random element from a list among those that satisfy
> > a certain property.
>
>
> >  A simple approach is:
> >
> > import random
> > def random_pick(a_list,property):
> >    '''Returns a random element from a list that has the property
> >
> >    Returns None if no element  has the property
> >    '''
> >    random.shuffle(a_list)
> >    for i in a_list:
> >        if property(i): return i
>
>
> I'm pretty sure you don't want to use a destructive random_pick function.
> You'll have to shuffle a copy instead to avoid that problem.
>

I thought of another one based on combining the above with the linear search
idea, minimizing the calls to the predicate function.

indexes = range(len(a_list))
random.shuffle(indexes)
for ix in indexes:
    if predicate(a_list[ix])
        return a_list[ix]
raise ValueError('no matching element in list')

-- 
Neil Cerutti
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20080104/f5d0301b/attachment-0001.html>