[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.python

fastest method to choose a random element

caca

1/4/2008 7:56:00 PM

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.

A simple approach is:

import random
def random_pick(a_list,property):
'''Returns a random element from a list that has the property

Returns None if no element has the property
'''
random.shuffle(a_list)
for i in a_list:
if property(i): return i

but that requires to shuffle the list every time.

A second approach, that works if we know that at least one element of
the list has the property, is:

import random
def random_pick(a_list,property):
'''Returns a random element from a list that has the property

Loops forever if no element has the property
'''
while 1:
i=random.choice(a_list)
if property(i): return i

which is more efficient (on average) if many elements of the list have
the property and less efficient if only few elements of the list has
the property (and goes crazy if no element has the property)

Yet another one:

import random
def random_pick(a_list,property):
'''Returns a random element from a list that has the property
'''
b_list=[x for x in a_list if property(x)]
try:
return random.choice(b_list)
finally: return None

but this one checks the property on all the elements, which is no
good.

I don't need strong random numbers, so a simple solution like:
import random
globalRNG=random.Random()

def random_pick(a_list,property):
'''Returns a random element from a list that has the property

Works only if len(a_list)+1 is prime: uses Fermat's little theorem
'''
a=globalRNG(1,len(a_list))
ind=a
for i in xrange(len(a_list)):
x=a_list[a-1]
if property(x):return x
ind*=a

but this works only if len(a_list)+1 is prime!!! Now this one could be
saved if there were an efficient method to find a prime number given
than a number n but not very much greater...

Any other ideas? Thanks everybody
23 Answers

Paddy

1/5/2008 6:37:00 AM

0

On Jan 4, 7:55 pm, c...@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.
>
> A simple approach is:
>
> import random
> def random_pick(a_list,property):
> '''Returns a random element from a list that has the property
>
> Returns None if no element has the property
> '''
> random.shuffle(a_list)
> for i in a_list:
> if property(i): return i
>
> but that requires to shuffle the list every time.
>
> A second approach, that works if we know that at least one element of
> the list has the property, is:
>
> import random
> def random_pick(a_list,property):
> '''Returns a random element from a list that has the property
>
> Loops forever if no element has the property
> '''
> while 1:
> i=random.choice(a_list)
> if property(i): return i
>
> which is more efficient (on average) if many elements of the list have
> the property and less efficient if only few elements of the list has
> the property (and goes crazy if no element has the property)
>
> Yet another one:
>
> import random
> def random_pick(a_list,property):
> '''Returns a random element from a list that has the property
> '''
> b_list=[x for x in a_list if property(x)]
> try:
> return random.choice(b_list)
> finally: return None
>
> but this one checks the property on all the elements, which is no
> good.
>
> I don't need strong random numbers, so a simple solution like:
> import random
> globalRNG=random.Random()
>
> def random_pick(a_list,property):
> '''Returns a random element from a list that has the property
>
> Works only if len(a_list)+1 is prime: uses Fermat's little theorem
> '''
> a=globalRNG(1,len(a_list))
> ind=a
> for i in xrange(len(a_list)):
> x=a_list[a-1]
> if property(x):return x
> ind*=a
>
> but this works only if len(a_list)+1 is prime!!! Now this one could be
> saved if there were an efficient method to find a prime number given
> than a number n but not very much greater...
>
> Any other ideas? Thanks everybody

Caching might help.

If random_pick is called several times with the same list(s) then
cache the result of
[property(i) for i in a_list] against a_list.

If random_pick is called several times with list(s) whith multiple
instances of list items then cache
property(i) against i for i in a_list .

You could do both.

You might investigate wether property(i) could be implemented using a
faster algorithm, maybe table lookup, or interpolation from initial
table lookup.

- Paddy.

caca

1/5/2008 10:16:00 AM

0


> Caching might help.
>
> If random_pick is called several times with the same list(s) then
> cache the result of
> [property(i) for i in a_list] against a_list.
>
> If random_pick is called several times with list(s) with multiple
> instances of list items then cache
> property(i) against i for i in a_list .
>
> You could do both.
>
> You might investigate wether property(i) could be implemented using a
> faster algorithm, maybe table lookup, or interpolation from initial
> table lookup.
>
> - Paddy.

Thanks, Paddy. Those are interesting general comments for the general
problem.
By the way, I noticed two things:

I forgot to write randint in the third approach:

> > a=globalRNG.randint(1,len(a_list))

The warning "The group you are posting to is a Usenet group. Messages
posted to this group will make your email address visible to anyone on
the Internet." means a person, but not a bot, may see my email
address, so it is safe to use my real address next time...

Paul Hankin

1/5/2008 11:22:00 AM

0

On Jan 4, 7:55 pm, c...@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

Arnaud Delobelle

1/5/2008 12:45:00 PM

0

On Jan 4, 7:55 pm, c...@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.

The generator function below yields an infinite sequence of randomly
picked elements from the list who satisfy the property, or nothing if
the list contains no element satisfying the property. It guarantees
that each time, prop() will either not be called or will be called
just enough to find one single item that satisfies it. The catch is
that you need to have an estimate for the number of items that satisfy
the property in the list.

import random
from itertools import islice, ifilter

def picker(lst, prop, np):
# lst: list of items to pick elements from
# prop: property that picked elements must fulfil
# np: (good estimate of) number of items that
# satisfy the property
random.shuffle(lst)
plst = [] # items we know fulfil prop
for item in ifilter(prop, lst):
# The next random item may be one already yielded
while True:
i = random.randrange(np)
if i >= len(plst): break
yield plst[i]
# Or it may be a new one
plst.append(item)
if len(plst) > np: np = len(plst)
yield item
# Now we know all items fulfilling prop
if not plst: return
while True:
yield plst[random.randrange(len(plst))]


def test(picker, n=1000):
res = {}
for val in islice(picker, n):
res[val] = res.get(val, 0) + 1
return res


Example:

>>> p = picker(range(20), lambda x: x % 2, 10)
>>> test(p)
{1: 113, 3: 96, 5: 87, 7: 91, 9: 109, 11: 91, 13: 106, 15: 101, 17:
109, 19: 97}


>>> p = picker(range(20), lambda x: False, 10)
>>> p.next()
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
StopIteration

I don't know if there is a good idea in there, I'll let you be the
judge :)

--
Arnaud

caca

1/5/2008 4:08:00 PM

0

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.

caca

1/5/2008 4:15:00 PM

0

On Jan 5, 5:07 pm, c...@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?

ajaksu

1/5/2008 4:58:00 PM

0

Hi there :)

On Jan 5, 2:14 pm, c...@mailinator.com wrote:
> On Jan 5, 5:07 pm, c...@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.

I've been thinking about this one before you asked and only got a bad
solution: you don't need to shuffle the list if you can construct a
random list of indexes to loop through, but my timings show that I
can't do that faster than "shuffle(range(x))" for worst cases (i.e.,
iterate thru the whole list) :)

The rather good news is that shuffling a list of arbitrary objects is
pretty fast (as compared to a list of integers).

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):

from random import random

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


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

If the lists share items, a cache could help a lot. Otherwise, you'd
benefit more from finding a good way to test the property (could you
give a hint on what it is?). How do objects acquire that property, is
it a sum of independent factors?

HTH,
Daniel

Martin v. Loewis

1/5/2008 5:13:00 PM

0

> Any other ideas?

How about this:

def random_pick(list, property):
L = len(list)
pos = start = random.randrange(L)
while 1:
x = list[pos]
if property(x): return x
pos = (pos + 1) % L
if pos == start:
raise ValueError, "no such item"

Regards,
Martin

Paul Hankin

1/5/2008 5:13:00 PM

0

On Jan 5, 4:14 pm, c...@mailinator.com wrote:
> On Jan 5, 5:07 pm, c...@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()

--
Paul Hankin

Paul Hankin

1/5/2008 5:22:00 PM

0

On Jan 5, 5:12 pm, "Martin v. Löwis" <mar...@v.loewis.de> wrote:
> > Any other ideas?
>
> How about this:
>
> def random_pick(list, property):
>     L = len(list)
>     pos = start = random.randrange(L)
>     while 1:
>         x = list[pos]
>         if property(x): return x
>         pos = (pos + 1) % L
>         if pos == start:
>            raise ValueError, "no such item"

This might be acceptable for the OP's use, but it's strongly biased
towards values which follow a long stream of things that fail
property.

print [random_pick(range(100), lambda x:x > 90)
for i in range(999)].count(91)

929

If it were uniform, it should be around 111.

--
Paul Hankin