fastest method to choose a random element

[Paul Hankin]

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.
>
> 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?

Here's a pragmatic optimisation for any algorithm: first test some
elements at random in case you get lucky or most of the elements are
good.

Eg, that optimisation applied to the naive shuffle algorithm.

import random
import itertools

def pick_random_fast(seq, prop):
    L = len(seq)
    stabs = 5
    for i in xrange(stabs):
        r = random.randrange(L)
        if prop(seq[r]): return seq[r]
    random.shuffle(seq)
    return itertools.ifilter(prop, seq).next()

I've used 5 'stabs' here. Perhaps it should be a function of L, but I
suppose you can tune it for your data.

--
Paul Hankin