On Jan 5, 4:14 pm, [EMAIL PROTECTED] wrote:
> On Jan 5, 5:07 pm, [EMAIL PROTECTED] 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
--
http://mail.python.org/mailman/listinfo/python-list
