fastest method to choose a random element

[Arnaud Delobelle]

On Jan 5, 8:50 pm, Paul Hankin <paul.han... at gmail.com> wrote:
> On Jan 5, 5:12 pm, Paul Hankin <paul.han... at gmail.com> wrote:
>
>
>
> > On Jan 5, 4: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.
>
> > You could generate a random shuffle of range(len(seq)) lazily, and use
> > that to iterate over your sequence.
>
> > import random
> > import itertools
>
> > def randxrange(n):
> >     "Generate the numbers 0 to n-1 in a random order"
> >     x = range(n)
> >     for i in xrange(n):
> >         r = random.randrange(n - i)
> >         yield x[r]
> >         x[r] = x[n - i - 1]
>
> > def shuffled(seq):
> >     "Generate the elements of seq in a random order"
> >     return (seq[i] for i in randxrange(len(seq)))
>
> > def pick_random(seq, prop):
> >     return itertools.ifilter(prop, shuffled(seq)).next()
>
> At the risk of filling this thread with my posts, here's a much
> simplified and faster version of this code that uses no extra storage.
>
> import random
>
> def pick_random(seq, prop):
>     L = len(seq)
>     for i in xrange(L):
>         r = random.randrange(L - i)
>         if prop(seq[r]):
>             return seq[r]
>         seq[r] = seq[L - i - 1]
>
> --
> Paul Hankin

Great!  This is so simple it must be the best way to do it.  Thanks
for that: I could feel there must be an elegant way, but I couldn't
put my finger on it.  The only downside, of course, is that it mutates
seq.  Moreover, it can be slightly modified to be a generator (in case
one wants to draw many elements from the sequence), improving vastly
on the generator function I proposed earlier.

def pick_random(seq, prop):
    for i in xrange(len(seq), 0, -1):
        r = random.randrange(i)
        if prop(seq[r]):
            return seq[r]
        seq[r] = seq[i - 1]


# Generator version.
def random_picker(seq, prop):
    for i in xrange(len(seq), 0, -1):
        while True:
            r = random.randrange(i)
            if not prop(seq[r]): break
            yield seq[r]
        seq[r] = seq[i - 1]

--
Arnaud