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)
  • 5
    Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. – Mast Mar 2 at 16:20
up vote 36 down vote accepted

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.

  • thanks for the insight. The context is actually only on the example with data : ['data_0, ...,...], and if there are any duplicates..i was assuming data like [1,1] is represented with ids: data_0 is 1, data data_1 is the other 1. Your point no. 4, 7 and 8 are nice and in context.. the others are deep. – Arief Mar 2 at 17:03
  • May i know why your point 7. Quadratic runtime behaviour..? – Arief Mar 2 at 17:18
  • @Arief: see updated post – Gareth Rees Mar 2 at 18:16
  • Gareth thanks again. Btw.. i think m-idx is not the remainder length of the list.. you meant m-i maybe – Arief Mar 3 at 3:30
  • 1
    @Arief: If you just want the runtime complexity, you look at the TimeComplexity page on the Python wiki. If you need the full details, you look at the implementation. – Gareth Rees Mar 3 at 10:11

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.
  • Graipher, thanks for the insight. globals() is never heard of before, but looks useful. Why eval is not recommended..? – Arief Mar 2 at 17:07
  • @Arief It is in general not recommended because people often use it to execute strings coming from a user. Since those can contain anything, this is potentially dangerous. Here it would be a not entirely bad choice for the reason stated above. But better not using eval when you could have, instead of using it when you really shouldn't have. Especially if there is an alternative that works just as well. – Graipher Mar 2 at 17:12
  • @Arief Also, if all you have is eval, everything looks like a string to be evaled... – Graipher Mar 2 at 17:13
  • Graipher ok.., thanks again. – Arief Mar 3 at 3:32

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.

  • Mathias, thanks. I was assuming a data like [1,1] is represented with ids, like data_0 for 1, and data_1 for the other 1. What do u think of this..? – Arief Mar 2 at 17:22
  • @Arief so you're saying that we need to map our values to a list of unique identifiers before calling one of your function; and then map back the result of your sampling to our initial data... That's really cumbersome, remarkably inefficient and totally undocumented! – Mathias Ettinger Mar 2 at 18:57
  • that is wrong. deepcopy is not needed and the use of deepcopy is absolutely bad. No algorithm modifies an element of data. If datais modified then a shallow copy created by 'copy.copy` is sufficient. – miracle173 Mar 3 at 8:32
  • @miracle173 there. It's just that I repeated the use of deepcopy because every one of the 20 functions start with that statement, but right, data = list(data) is more than enough. – Mathias Ettinger Mar 3 at 8:37

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

  • I like your choice of set() since he's selecting samples w/o replacement. However, your code could be simplified even more by removing the while loop that checks whether idx is already in visited. it's not necessary because a set.add will not append a duplicate. With the removal of the while loop, the for loop will need to change to 'while len(visited) < n' to control when the function ends, so instead of looping a fixed n times it will stop when visited has n samples. – floydn Nov 4 at 15:57
  • but then you'd have to do a test to check whether it is a new index before yielding, or return the set instead of using a generator. – Maarten Fabré Nov 5 at 8:46
  • I see what you are saying. I now studied your code in its totality instead of focusing on the for loop in random_indices3(). I think it should return the set because internally you're tracking the contents of the set anyway in visited so I don't see any benefit of the generator. By the way, 'data[idx]' should be 'data[i]'. – floydn Nov 5 at 20:30

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.