fastest method to choose a random element

[Paul Hankin]

On Jan 4, 7:55 pm, c... 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.
>
>   This is the setting: I need to pick from a list a random element
> that satisfies a given property. All or none of the elements may have
> the property. Most of the time, many of the elements will satisfy the
> property, and the property is a bit expensive to evaluate. Chance of
> having the property are uniform among elements.

Here's some code that uses a cached random sorting of the list. It
assumes you'll want more than one random element. It never calls
'prop' on the same element twice, and it's O(n) even when the elements
that pass 'prop' are sparse. I hope this is useful to you!

import random

class RandomPicker(object):
    def __init__(self, seq, prop=lambda x:True):
        seq = list(seq)
        random.shuffle(seq)
        # Store with the item whether we've computed prop on it
already.
        self.random_list = [(x, False) for x in seq]
        self.prop = prop
    def pick(self):
        for i, (x, p) in enumerate(self.random_list):
            if p or self.prop(x):
                if not p:
                    # Record the fact that self.prop passed.
                    self.random_list[i] = (x, True)
                # Chop off the items that prop failed on.
                self.random_list = self.random_list[i:]
                r = self.random_list
                # Instead of shuffling the whole list again, just
insert
                # x back in the list randomly. Since the remaining
elements
                # are randomly sorted already, this is ok.
                n = random.randint(0, len(r) - 1)
                r[0], r[n] = r[n], r[0]
                return x
        # Nothing in the list passes the 'prop' test.
        return None

# Example: pick 100 odd integers from 0 to 1000.
a = RandomPicker(xrange(1000), lambda x: x % 2 == 1)
print [a.pick() for i in xrange(100)]

--
Paul Hankin