fastest method to choose a random element

[ajaksu]

> OTOH, if you do know that the chances are high enough, you can try
> choosing items randomly without substitution (adapted from random.py's
> sample):

Sorry, this works:

def randpickuntil(lst, prop=bool):
    selected = set()
    n = len(lst)
    for i in xrange(n):
        j = int(random() * n)
        while j in selected:
                j = int(random() * n)
        if prop(lst[j]):
            return lst[j]
        selected.add(j)

Gotta say it's much faster on average than shuffle for moderately to
highly probable tests, but might become pathological (i.e. run for
minutes) for very large lists in which prop(x) is False for all.