ActiveState Powered by ActiveState

Recipe 273085: sample with replacement

For taking k random samples (with replacement) from a population, where k may be greater than len(population).

Python 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
# credit author(s) of random.py
import random

def sample_wr(population, k):
    "Chooses k random elements (with replacement) from a population"
    n = len(population)
    _random, _int = random.random, int  # speed hack 
    result = [None] * k
    for i in xrange(k):
        j = _int(_random() * n)
        result[i] = population[j]
    return result

Discussion

random.sample() lets you do random sampling without replacement. sample_wr() lets you sample with replacement.

Some simple examples:

tosses = sample_wr(('H', 'T'), 100) # simulate 100 coin tosses rolls = sample_wr(range(1,7), 100) # simulate 100 dice rolls

make a random string from 200 characters over a given alphabet

from string import letters as alphabet rstr = ''.join(sample_wr(alphabet, 200))

NOTE:

You could use

from random import choice sample = [choice(population) for i in xrange(k)]

but that is 2-4 times slower than sample_wr(population, k) for 10E3 <= k <= 10E6

from random import random n = len(population) sample = [population[int(random()*n)] for i in xrange(k)]

is better but still slower.

Comments

  1. 1. At 9:27 p.m. on 11 mar 2004, Raymond Hettinger said:

    math.floor() beats int(). It is faster still to use _int=math.floor for this situation (rounding positive numbers downward).

  2. 2. At 9:36 p.m. on 11 mar 2004, Raymond Hettinger said:

    Nix the previous comment. The float result still needs to be converted back to an integer at some point.

  3. 3. At 1:36 a.m. on 14 mar 2004, Raymond Hettinger said:

    In Py2.4, pre-allocation no longer rules. In the next version of Python, list comprehensions have been super-optimized and cannot be beat by pre-allocating and using indices.

    def sample_wr(population, k):
    "Chooses k random elements (with replacement) from a population"
    n = len(population)
    _random, _int = random.random, int  # speed hack
    return [_int(_random() * n) for i in xrange(k)]

    And you can go bit faster using itertools:

    def sample_wr(population, k):
    "Chooses k random elements (with replacement) from a population"
    n = len(population)
    _random, _int = random.random, int  # speed hack
    return [_int(_random() * n) for i in itertools.repeat(None, k)]
  4. 4. At 9:43 a.m. on 14 mar 2004, Sean Ross (the author) said:

    correction, accolades, and propositions. return [population[_int(_random() * n)] for i in ... ]

    I've been following python-dev, so I'm aware of the optimizations you've been making. Congratulations on your results to date, and thank you for your time and efforts.

    I wonder, do you suppose the developers would accept changing random.sample to allow for sampling with replacement?

    replacement=False by default (backwards compatible)

    random.sample(population, k, replacement=True)

  5. 5. At 9:56 p.m. on 16 mar 2004, Raymond Hettinger said:

    Adding a replace=False option to random.sample. For several reasons, probably not.

    The straight-forward list comp does the trick pretty well. Anything that someone can bang out without much thought is rarely a good candidate for building into the library unless the pattern is very general and the use cases very common. The reasoning is that it is typically easier to bang out a couple of lines than to learn and remember dozens of method variations. Part of the justification for the inclusion of sampling without replacement is that it took a great deal of skill and time to implement correctly.

    The other issue is that there are plenty of use cases that just do not need the whole sample all a once (those are best served by a simple for-loop). In contrast, sampling without replacement requires some state memory between calls.

    Also, adding a new method is typically preferred to adding a keyword switch (for example, see itertools ifilter() and ifilterfalse()). However, for the reasons listed above, the inclusion of this as a separate method is unlikely.

    I put all of this here because it is useful to a wider audience. Feel free to email me for any further discussion.

Sign in to comment