Picking random items from an iterator (Python recipe) by Simon Brunning

ActiveState Code (http://code.activestate.com/recipes/426332/)

random.sample handles iterators. Worth noting that random.sample handles iterators:

py> import random
py> i = iter(range(10))
py> random.sample(i, 2)
[2, 0]

I don't know if it makes any guarantees about efficiency though.

Comparison with random.sample. Unlike random.sample, the OP's recipe samples with replacement -- whether that is a feature or bug is another question. Given an iterator input, the OP's function has the virtue of not pulling all the data into memory at once; in contrast, random.sample will sometimes (depending on the ratio of population size to sample size) pull all the data into memory. In terms of operating efficiency, the OP's recipe uses far too many calls to the underlying random number generator; in contrast, random.sample makes at many fewer calls. Here's an alternate recipe that gives the best of both worlds (memory efficiency and fewer calls to the generator):

from random import random, shuffle

def random_items(iterable, k=1):
    result = [None] * k
    for i, item in enumerate(iterable):
        if i < k:
            result[i] = item
        else:
            j = int(random() * (i+1))
            if j < k:
                result[j] = item
    shuffle(result)
    return result

Clever. Oooh, nice, Raymond.

further split your loop. assuming that generally len(iterable) >> k, for efficiency's sake you'd be better off splitting the loop in two parts, to avoid the soon-to-be-useless comparison i assuming that generally len(iterable) >> k, for efficiency's sake you'd be better off splitting the loop in two parts, to avoid the soon-to-be-useless comparison i

Correctness. Please correct me if I'm wrong, but it seems like the first items in the iterable will have a much greater chance of being picked than the higher ones.

Consider

random_items(iter(range(1000)), 5)

In this case, after the first 5 items are in result the algorithm will begin generating random numbers and replacing items in result with k/n probability, with k being the desired number of random items and n being the index of each item in the iterable. So the chance for 20 being in the result (at some point during the algorithm) is 5/20, and the chance for 950 would be 5/950. Also, the lower numbers get replaced so in this case, there is almost no chance that the numbers 0-45 will be in the final array.

This is a good algorithm for picking some numbers from an iterable, but it does not seem to pick uniformly random items.

And yet ... When we actually try it, say running it 1000 times so each item can expect to be picked 5 times in total:

lcTotalPicks = [0] * 1000
for i in range(1000):
    lcPicks = random_items(iter(range(1000)), 5)
    for j in lcPicks:
        lcTotalPicks[j] += 1

we find no significant difference between the first 20 and the last 20 items:

print lcTotalPicks[0:20]
print lcTotalPicks[980:1000]

[4, 4, 7, 9, 4, 2, 4, 2, 7, 4, 8, 9, 4, 7, 6, 7, 8, 8, 5, 1]
[4, 3, 1, 9, 9, 3, 4, 9, 8, 8, 3, 5, 6, 5, 4, 5, 5, 7, 4, 6]

Indeed, lower numbers are more likely to be in the result, and also more likely to be replaced. The two effects cancel out, and every number has the same "almost no chance" (5/1000) to be included in the final result.