random iteration of a sequence using generators

[srpiton]

Hello everybody. Anybody has any ideas with the following problem?

We start with a list, and we wish to construct a generator that yields each element of the list exactly once, but in random order.

In other words, an iterator version of random.shuffle(list)

The motivation is the following: suppose you have a huge list and wish to extract one random element that satisfies a certain property. Typically, you expect many elements to have the property, so this approach:

-Select a random element, check if it has the property. If that is the case, yield the element, otherwise, loop

is more efficient that this other one:

-Filter the list and select one element.

However the first approach will have find trouble if none, or few elements have the property if your iteration of the list does not guarantee that every element is yielded at least once, and will not be efficient if the iteration does not guarantee that every element is yielded at most once.

Thanks everybody

[bartonc]

Not sure if this satisfies all your requirements, but distribution looks good:

>>> from random import randint
>>> def YieldRandomItem(aList):
...     beenYielded = []
...     size = len(aList) - 1
...     for item in aList:
...         i = randint(0, size)
...         while i in beenYielded:
...             i = randint(0, size)
...         beenYielded.append(i)
...         yield aList[i]
...         
>>> myList = range(20)
>>> for item in YieldRandomItem(myList):
...     print item
...     
9
10
19
11
12
1
14
18
16
7
5
2
3
6
8
17
13
4
15
 
>>> for item in YieldRandomItem(myList):
...     print item
...     
5
15
7
19
2
12
4
14
6
11
13
 
10
1
17
9
3
8
18
16
>>> 

[srpiton]

Thanks for your answer, bartonc.
Well, this certainly works as a general method, though for the particular problem that motivated my question I would rather generate random numbers and check if they have the required property:

x=choice(aList)
while not property(x):
     x=choice(aList)
return x
 

However, I'd bet this can be done even better. I would like to do without having to check the property several times on the same item. Your proposal does this, but at the cost of having to make the check 'i in beenYielded' several times on the same item.

------

As a solution to the general problem, your solution won't do bad, specially if 'YieldRandomItem' is called for only a few items of the list (which was the motivation), but I believe it's possible to do even better, may be at the cost of having random numbers of poorer quality.

One comment about your solution: the number of iterations of the 'while' loop required to yield the i'th element follows a geometric distribution, with expected time: n/(n-i)
The total expected time if 'YieldRandomItem' has to run through the whole list is thus:
n/n+n/(n-1)+n/(n-2)+...+n
which is aproximately
n log(n)

So it takes generation of n log(n) random numbers and performing the check 'i in beenYielded' n log(n) times.

This last part takes 'n' operations for each check, which increases the total cost greatly, but the cost of a search operation 'x in aList' can be reduced to 'log(n)' if the list is replaced by a set.

-------

May be a method in the random module that pops a random element from a set would be helpful....