20 Ways to do Random Sampling

Question

Here is a (small project) code for practicing Python, it comprises 20 variety of functions that each works to return \$n\$ random samples from a set of data.

The code mostly uses the random module.

I would like to know :

• What to improve.
• Better ways to do random sampling without replacement. (perhaps using recursive method, etc.)

The project currently only allows using built-in modules.

Github link

import random
import copy
import itertools

data=["data_{}".format(i) for i in range(100)];

print("Data : ")
print(data);

ex_1 = "1. Sampling by directly use the random.sample function.";
def sampling_1(data, n=10):
    data=copy.deepcopy(data);
    return random.sample(data, n)

ex_2 = "2. Sampling by directly use the random.sample function, but through the indexes, \
then use list comprehension to construct the sample.";
def sampling_2(data, n=10):
    data=copy.deepcopy(data);
    idxs=random.sample(range(len(data)), n)
    sample=[data[i] for i in idxs];
    return sample

ex_3="3. Sampling the index of data's list \
in a for-loop, using random.randint, and store in a list. \
The index choosing will be repeated if index already chosen before.";
def sampling_3(data, n=10):
    data=copy.deepcopy(data);
    N=len(data);
    sample=[];
    for i in range(n):
        idx = random.randint(0,N-1);
        while data[idx] in sample:
            idx = random.randint(0,N-1);
        sample.append(data[idx]);
    return sample

ex_4="4. Sampling the index of data's list \
using while, using random.randint, and store in a list. \
The index choosing will be repeated if index already chosen before.";
def sampling_4(data, n=10):
    data=copy.deepcopy(data);
    N=len(data);
    sample=[]; 
    while len(sample)<n:
        idx = random.randint(0,N-1);
        if not (data[idx] in sample):
            sample.append(data[idx]);
    return sample

ex_5="5. Sampling the index of data's list \
in a for-loop, using random.randint, and store in a dictionary. \
The index choosing will be repeated if index already chosen before.";
def sampling_5(data, n=10):
    data=copy.deepcopy(data);
    N=len(data);
    sample={}; 
    for i in range(n):
        idx = random.randint(0,N-1);
        while data[idx] in sample:
            idx = random.randint(0,N-1);
        sample[i]=data[idx];
    return sample

ex_6="6. Sampling by using random.randint and store the sample in list. \
The copied-original data is popped after each sampling, to avoid repetition.";
def sampling_6(data, n=10):
    data=copy.deepcopy(data);
    sample=[];
    for i in range(n):
        idx = random.randint(0,len(data)-1);
        sample.append(data.pop(idx));
    return sample

ex_7="7. Sampling the index of data's list \
using random.randint, and list comprehension. \
The initial indexes list will keep being updated using .pop in the list comprehension, \
such that the sampling is without replacement.";
def sampling_7(data, n=10):
    data=copy.deepcopy(data);
    N=len(data);
    idxs=list(range(N));
    rand_idxs=[idxs.pop(random.randint(0,len(idxs)-1)) \
               for i in range(n)];
    sample=[data[i] for i in rand_idxs];
    return sample

ex_8 = "8. Sampling without replacement by a recursive method. \
The function take_new works as a \"cyclic\" function until we get a new sample from data."
def sampling_8(data, n=10):
    data=copy.deepcopy(data);
    N=len(data);
    sample=[];
    def take_new():
        idx=random.randint(0, N-1);
        if data[idx] in sample:
            return take_new()
        else:
            sample.append(data[idx]);
            return None
    for i in range(n): take_new();
    return sample

ex_9 = "9. Similar as no.8, but with additional \"cyclic\" condition \
: if number of samples less than n.";
def sampling_9(data, n=10):
    data=copy.deepcopy(data);
    N=len(data);
    sample=[];
    def take_new():
        idx=random.randint(0, N-1);
        if data[idx] in sample:
            return take_new()
        else:
            sample.append(data[idx]);
        if len(sample)<n:
            return take_new()
    take_new();
    return sample

ex_10 = "10. Similar as no.7, but the sampling is using map and directly from the data, not it's indexes.";
def sampling_10(data, n=10):
    data=copy.deepcopy(data);
    dummy=range(n);
    sample=list(map(lambda x: data.pop(random.randint(0,len(data)-1)),dummy));
    return sample

ex_11 = "11. Same as no.10, but using list comprehension.";
def sampling_11(data, n=10):
    data=copy.deepcopy(data);
    dummy=range(n);
    sample=[data.pop(random.randint(0,len(data)-1)) for i in dummy];
    return sample

ex_12 = "12. Similar as no.10, but using list.append in while loop.";
def sampling_12(data, n=10):
    data=copy.deepcopy(data);
    sample=[];
    while len(sample)<n:
        sample.append(data.pop(random.randint(0,len(data)-1)));
    return sample

ex_13 = "13. Similar as no.9, but try-except rather than using \
if len(sample)<n.";
def sampling_13(data, n=10):
    data=copy.deepcopy(data);
    N=len(data);
    sample=[];
    def take_new():
        idx=random.randint(0, N-1);
        if data[idx] in sample:
            return take_new()
        else:
            sample.append(data[idx]);
        try :
            sample[n-1]
        except:
            return take_new()
    take_new();
    return sample

ex_14 = "14. Using random.choice n times, while removing \
 the chosen sample from the original data.";
def sampling_14(data, n=10):
    data=copy.deepcopy(data);
    sample=[];
    for i in range(n):
        rand=random.choice(data);
        data.remove(rand);
        sample.append(rand);
    return sample

ex_15 = "15. Define a remove-and-return function, such that we \
can use random.choice in list comprehension to collect n samples.";
def sampling_15(data, n=10):
    data=copy.deepcopy(data);
    def rem_n_ret(x, rem):
        rem.remove(x);
        return x
    sample=[rem_n_ret(random.choice(data), data) \
            for i in range(n)]
    return sample

ex_16 = "16. Sampling by shuffling the data, then get only \
the first n elements.";
def sampling_16(data, n=10):
    data=copy.deepcopy(data);
    random.shuffle(data);
    sample=data[0:n];
    return sample

ex_17 = "17. Sampling by taking samples from a uniform distribution, \
 and treat them as the random generated index.";
def sampling_17(data, n=10):
    data=copy.deepcopy(data); 
    idxs = [];
    while len(idxs)<n:
        rand=int(random.uniform(0, len(data)))
        if rand in idxs:
            pass
        else:
            idxs.append(rand);
    sample=[data[i] for i in idxs];
    return sample

ex_18 = "18. Sampling by taking samples from random.random, multiply by N, and floor it, \
then treat them as random generated index.";
def sampling_18(data, n=10):
    data=copy.deepcopy(data);
    N=len(data);
    idxs=[];
    while len(idxs)<n:
        rand=int(random.random()*N);
        if rand in idxs:
            pass
        else:
            idxs.append(rand)
    sample=[data[i] for i in idxs];
    return sample    

ex_19 = "19. We can also use try-except this way, to ensure that \
the sampling is without replacement.";
def sampling_19(data, n=10):
    data=copy.deepcopy(data);
    sample=[];
    dummy=[0];
    while len(sample)<n:
        rand=random.choice(data);
        try:
            dummy[sample.count(rand)]
            sample.append(rand);
        except:
            pass
    return sample

ex_20 = "20. Combining the use of random.sample and random.choice. At each iteration, \
a sample is withdrawn from data, the method used is switched at next iteration.";
def sampling_20(data, n=10):
    data=copy.deepcopy(data);
    sample=[];
    for i in range(n):
        if (-1)^(i)==1:
            rand=random.sample(data,1);
        else:
            rand=random.choice(data);
        data.remove(rand);
        sample.append(rand);
    return sample          

##################

class RandSampling:
    def __init__(self):
        self.funcs=tuple([eval("sampling_{}".format(i)) for i in range(1,21)]);
        self.func_desc=tuple([eval("ex_{}".format(i)) for i in range(1,21)]);
    def call_function(self, number, n):
        return self.funcs[number](n);
    def show_all(self, data, n=10):
        for i in range(len(self.funcs)):
            print("\n");
            print(self.func_desc[i]);
            print(self.funcs[i](data, n));

Rand=RandSampling();
Rand.show_all(data, 10)

Answer 1

It would be worth your while to take a look at the implementation of random.sample to see how it works. (It's different from all 20 implementations in the post, and it will be instructive to figure out why.)

In this answer I will confine myself to describing bugs (or ways in which the code in the post is inadequate in comparison with random.sample).

1. Bugs and misfeatures

1. All versions of the code fail if any of the items cannot be copied:

   >>> class Uncopyable(int):
   ...     def __deepcopy__(self, memo):
   ...         raise RuntimeError("not copyable")
   ... 
   >>> sampling_1([Uncopyable(1)], 1)
   Traceback (most recent call last):
     File "<stdin>", line 1, in <module>
     File "cr188610.py", line 12, in sampling_1
       data=copy.deepcopy(data);
     File "python3.6/copy.py", line 150, in deepcopy
       y = copier(x, memo)
     File "python3.6/copy.py", line 215, in _deepcopy_list
       append(deepcopy(a, memo))
     File "python3.6/copy.py", line 161, in deepcopy
       y = copier(memo)
     File "<stdin>", line 3, in __deepcopy__
   RuntimeError: not copyable
   

   but random.sample has no problem with uncopyable objects:

   >>> random.sample([Uncopyable(1)], 1)
   [1]
   

   There is no need to take a deep copy of the data. In versions 6, 10, 11, 12, 14, 15, 16, and 20 (that modify data), a shallow copy of the list, that is, data[:], is all that's needed. Otherwise no copy is required at all.

2. Versions 3, 4, 5, 8, 9, 13, and 19 fail if items are not comparable for equality. For example:

   >>> class Uncomparable(int):
   ...     def __eq__(self, other):
   ...         raise TypeError("not comparable")
   ... 
   TypeError: not comparable
   >>> sampling_3([Uncomparable(1), Uncomparable(2)], 2)
   Traceback (most recent call last):
     File "<stdin>", line 1, in <module>
     File "cr188610.py", line 32, in sampling_3
       while data[idx] in sample:
     File "<stdin>", line 3, in __eq__
   TypeError: not comparable
   

   but random.sample has no problem with uncomparable objects:

   >>> random.sample([Uncomparable(1), Uncomparable(2)], 2)
   [1, 2]
   

3. Versions 3, 4, 5, 17, and 19 go into an infinite loop if the sample needs a duplicate object:

   >>> sampling_3([1, 1], 2)
   ^C
   Traceback (most recent call last):
     File "<stdin>", line 1, in <module>
     File "cr188610.py", line 33, in sampling_3
       idx = random.randint(0,N-1);
     File "/python3.6/random.py", line 221, in randint
       return self.randrange(a, b+1)
     File "/python3.6/random.py", line 196, in randrange
       if step == 1 and width > 0:
   KeyboardInterrupt
   

4. Version 19 might not even be stopped by a keyboard interrupt, because if the interrupt occurs in the try: block, the except: catches it.

5. Versions 8 and 9 fail with a stack overflow if the sample needs a duplicate object:

   >>> sampling_8([1, 1], 2)
   Traceback (most recent call last):
     File "<stdin>", line 1, in <module>
     File "cr188610.py", line 100, in sampling_8
       for i in range(n): take_new();
     File "cr188610.py", line 96, in take_new
       return take_new()
     [Previous line repeated 992 more times]
     File "cr188610.py", line 94, in take_new
       idx=random.randint(0, N-1);
     File "python3.6/random.py", line 221, in randint
       return self.randrange(a, b+1)
     File "python3.6/random.py", line 197, in randrange
       return istart + self._randbelow(width)
     File "python3.6/random.py", line 231, in _randbelow
       if type(random) is BuiltinMethod or type(getrandbits) is Method:
   RecursionError: maximum recursion depth exceeded while calling a Python object
   

6. Version 5 returns a dictionary whose values are the sampled items, instead of a list.

7. Versions 6, 10, 11, 12, 14, and 20 have quadratic runtime behavour. They use data.pop or data.remove for each item in the sample, and these methods take time proportional to the length of the list. See §2 below for more details.

8. The description of example 20 is wrong: the expression (-1)^(i)==1 is always false, and so random.sample is never called. Possibly you were thinking of the expression (-1) ** i == 1.

2. Performance

Let's analyze the performance of version 6. I'll rewrite it a little so that each line has only one or two operations:

sample = [];
for i in range(n):
    m = len(data) - 1
    idx = random.randint(0, m)
    item = data.pop(idx)
    sample.append(item)
return sample

Here's a table showing how many times each line is executed, and how long it takes to execute:

LINE                             EXEC   TIME
------------------------------   ----   ---------
sample = [];                     1      t1
for i in range(n):               n      t2
    m = len(data) - 1            n      t3
    idx = random.randint(0, m)   n      t4
    item = data.pop(idx)         n      t5(m-idx)    (*)
    sample.append(item)          n      t6
return sample                    1      t7

Here \$t_1, \ldots, t_7\$ are constants that depend on the details of the Python implementation. The important observation is on the line marked (*): it takes time proportional to the remainder of the length of the list to pop an item from the list. That's because Python has to copy the later items in the list down to fill the gap left by the popped item.

We know that each iteration of the loop removes one item from data, so on the \$i\$th iteration of the loop, we will have \$m = k - i - 1\$, where \$k\$ is the initial length of data. In the average case, the popped index will be halfway along the list, so the total runtime in the average case is $$ \eqalign{ T(n, k) &= t_1 + \sum_{0≤i<n}\left(t_2 + t_3 + t_4 + t_5{m\over2} + t_6\right) + t_7 \\ &= t_1 + \sum_{0≤i<n}\left(t_2 + t_3 + t_4 + t_5{k - i - 1\over2} + t_6\right) + t_7 \\ &= {t_5\over2}nk - {t_5\over2}\sum_{0≤i<n}i + n\left(t_2 + t_3 + t_4 - {t_5\over2} + t_6\right) + t_1 + t_7 } $$ and we know that $$ \sum_{0≤i<n}i = {n^2 - n\over 2}$$ and so $$ T(n, k) = {t_5\over2}n\left(k - {n\over2}\right) + n\left(t_2 + t_3 + t_4 - {t_5\over4} + t_6\right) + t_1 + t_7 $$ I've gone into this in excruciating detail just in case you're not familiar with analysis of algorithms, and want to see all the details written out. But the important result of the analysis is the first term: $$ {t_5\over2}n\left(k - {n\over2}\right) $$ We know that \$k\$ has to be at least as big as \$n\$, so this term is at least $${t_5\over4}n^2$$ which is quadratic in \$n\$.

We can see this in action by giving version 6 longer and longer inputs, and timing how long it takes:

>>> from timeit import timeit
>>> timeit(lambda:sampling_6(list(range(10**5)), 10**5), number=1)
0.8873438290320337
>>> timeit(lambda:sampling_6(list(range(10**6)), 10**6), number=1)
80.59396354103228

You can see that although the input in the second test case is only 10 times as big as in the first, the runtime is nearly 100 times as long. That's what I mean by "quadratic runtime behaviour".

Compare with random.sample:

>>> timeit(lambda:random.sample(range(10**5), 10**5), number=1)
0.12471016502240673
>>> timeit(lambda:random.sample(range(10**6), 10**6), number=1)
1.3061895630089566

Here, when the input is 10 times as big, the runtime is only about 10 times as long.

Answer 2

You should not use eval without a very good reason. This is not a very good reason.

Even though here you are actually fully in control of what gets passed to eval, this is good general advice. Whenever you find yourself using eval, there is probably a better way. Here I would use globals() to get a dictionary of all globally defined objects (see below).

---

But first, make those strings the docstrings of the function they are describing:

def sampling_1(data, n=10):
    """1. Sampling by directly use the random.sample function."""
    return random.sample(data, n)

This string can be accessed with the dunder attribute sampling_1.__doc__. Note that you also don't need to deepcopy the data in this case (you might need it in a later function, I did not read them all...).

Your class becomes a lot easier, with using globals() to get all functions whose name starts with "sampling_" (technically, all objects, so if you have a variable with a name that matches that you will get an error and will have to filter on the object being callable):

class RandSampling:
    def __init__(self):
        self.funcs = [func
                      for name, func in sorted(globals().items())
                      if name.startswith("sampling_")]

    def call_function(self, number, n):
        return self.funcs[number](n)

    def show_all(self, data, n=10):
        for func in self.funcs):
            print("\n")
            print(func.__doc_)
            print(func(data, n))

I also made your looping easier by looping over the elements instead of the indices. You should probably have a look at Loop like a Native.

I'm not even sure if you need that class at all. You can just do it directly:

if __name__ == "__main__":
    data = ["data_{}".format(i) for i in range(100)]
    print("Data : ")
    print(data)

    funcs = [func for name, func in sorted(globals().items())
             if name.startswith("sampling_")]
    for func in funcs:
        print("\n")
        print(func.__doc__)
        print(func(data, n))

This is now under a if __name__ == '__main__' guard, which guarantees that it will only be executed when you directly run this script, but not if you import parts of it from another script.

---

Finally, Python has an official style-guide, PEP8. It recommends:

• Not to use ; at the end of the line. It is entirely superfluous in normal code
• Use lower_case for variables and functions and PascalCase only for classes.
• Add spaces after commas, so range(1, 21)
• Add spaces around operators (including =, except when specifying keyword arguments)
• Separate your methods in classes with one blank line, function definitions outside of classes and classes with two blank lines.

Answer 3

Besides the good points of @Graipher's answer:

• Examples n° 6, 7, 10, 11, 12, 14, 15, 16, and 20 are the only one that modify the input data and thus only them need to copy the input to not modify it.

• Examples n° 3, 4, 5, 8, 9, 13, and 19 are not performing proper sampling.

  Consider an input data of [1, 0, 0, 0, 0, 0, 0, 0, 0, 0], then when sampling two elements, I can have two type of output: two \$0\$ with a probability close to 90% and one \$1\$ and one \$0\$ with a probability close to 10%. Using any of those implementation would lead to [0, 1] or [1, 0] 100% of the time, which is clearly way beyond the expected 10%.

  This is because, when you try to sample without replacements, you focus on the value at hand instead of the element. Without replacement mean I shouldn't get to pick element n°\$i\$ (for any \$i\$) more than one time, it does not mean I should exclude duplicates from being picked more than one time.

Answer 4

Another point for me would be to use generators instead of functions returning lists.

I would also extract the ways you look for the indices

For example:

ex_3="3. Sampling the index of data's list \
in a for-loop, using random.randint, and store in a list. \
The index choosing will be repeated if index already chosen before.";
def sampling_3(data, n=10):
    data=copy.deepcopy(data);
    N=len(data);
    sample=[];
    for i in range(n):
        idx = random.randint(0,N-1);
        while data[idx] in sample:
            idx = random.randint(0,N-1);
        sample.append(data[idx]);
    return sample

Would become

def sampling_3(data, n=10):
"""
Sampling the index of data's list
in a for-loop, using random.randint, and store in a list.
The index choosing will be repeated if index already chosen before.
"""
    data=data[:] # not really necessary since this does not mutate the set. Might be necessary if some other part of the program mutates `data`
    for i in random_indices3(len(data), n)
        yield data[idx]

def random_indices3(N, n):
'''
yields n random indices
'''
visited = set()
for i in range(n):
    idx = random.randint(0, N - 1)
    while idx in visited:
        idx = random.randint(0, N - 1)
    yield idx
    visited.add(idx)

Usually a set is also better to check whether something is in it than a list