20 способов сделать случайную выборку


Вот это (небольшой проект) Код для практикующих питона, она включает в себя 20 различных функций, что каждый работает, чтобы вернуться \$выборки N\$ случайным образом из набора данных.

Код в основном используется random модуль.

Я хотел бы знать :

  • Что улучшать.
  • Лучшие способы сделать случайного бесповторного. (возможно, используя рекурсивный метод и т. д.)

В настоящее время проект только позволяет с помощью встроенных модулей.

GitHub ссылке

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)


Комментарии
4 ответа

Это будет стоит вашего времени, чтобы взглянуть на реализацию random.sample чтобы увидеть, как это работает. (Это отличается от всех 20 реализаций в посте, и это будет поучительно, чтобы выяснить, почему.)

В этом ответе я ограничусь описанием ошибки (или способов, в которых код в пост неадекватен в сравнении с random.sample).

1. Ошибки и misfeatures


  1. Все варианты код не если любой из пунктов не может быть скопирован:

    >>> 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

    но random.sample не имеет никаких проблем с некопируемые объекты:

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

    Нет необходимости сделать глубокий копию данных. В версии 6, 10, 11, 12, 14, 15, 16, и 20 (что изменить data), мелкую копию списка, то есть data[:]это все, что нужно. В противном случае копии не требуется вовсе.


  2. Варианты 3, 4, 5, 8, 9, 13, и 19 неудачу, если товары не сопоставимы по вопросам равенства. Например:

    >>> 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

    но random.sample не имеет никаких проблем с непревзойденным объекты:

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

  3. Версий 3, 4, 5, 17, 19 и войти в бесконечный цикл, если образец нужен дубликат объекта:

    >>> 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. Версия 19 не может даже быть остановлен прерывание клавиатуры, потому что если прерывание происходит в try: блок except: ловит его.

  5. Версии 8 и 9 выполнена с переполнением стека, если образец нужен дубликат объекта:

    >>> 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. Версия 5 возвращает словарь, значения которых являются выбранные предметы, а не список.

  7. Варианты 6, 10, 11, 12, 14, и 20 квадратичное время выполнения поведение. Они используют data.pop или data.remove для каждого элемента в образце, и эти методы принимают время, пропорциональное длине списка. См. п. 2 ниже для более подробной информации.

  8. Описание примера 20 неверно: выражение (-1)^(i)==1 это всегда ложь, и так random.sample никогда не вызывается. Возможно, вы думали о выражение (-1) ** i == 1.

2. Производительности

Давайте проанализируем производительность версии 6. Я перепишу его немного так, чтобы каждая строка имеет только одну или две операции:

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

Вот таблица, показывающая, во сколько раз каждая линия выполняется, и сколько времени потребуется для выполнения:

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

Здесь \$т_1, \лдоц t_7\$ являются константами, которые зависят от деталей реализации на языке Python. Важное замечание находится на линии, отмеченные (*): это занимает время, пропорциональное оставшейся части длины списка поп элемент из списка. Это потому, что Python имеет скопировать позже элементы в списке, чтобы заполнить пробел, оставленный появившемся пункт.

Мы знаем, что каждая итерация цикла удаляет один элемент из dataтак, на \$Я\$й итерации цикла, мы будем иметь \$М = К - и - 1\$, где$к\$ - это начальная длина data. В среднем случае, выскочил индекс будет в середине списка, так и общего времени в среднем случае является $$ \eqalign{ т(п, K) и= т_1 + \sum_{0≤я

Мы можем увидеть это в действии, давая версии 6 больше и больше ресурсов, и времени, сколько времени это занимает:

>>> 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

Вы можете видеть, что, хотя вход на второй тестовый случай, только в 10 раз, как в первый, время автономной работы почти в 100 раз дольше. Вот что я подразумеваю под "квадратичной среды поведения".

Сравнить с 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

Вот, когда вход в 10 раз, время выполнения составляет всего около 10 раз дольше.

36
ответ дан 1 марта 2018 в 02:03 Источник Поделиться

Вы не должны использовать eval без очень веской причины. Это не очень хорошая причина.

Хотя здесь на самом деле вы полностью контролируете то, что передается в evalэто хорошие советы. Всякий раз, когда вы окажетесь с помощью evalпожалуй, нет лучшего способа. Здесь я хотел бы использовать globals() чтобы получить словарь все глобально определенными объектами (см. ниже).


Но во-первых, сделать эти строки в комментарии функции они описывают:

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

Эту строку можно ознакомиться с Дандер атрибут sampling_1.__doc__.
Обратите внимание, что вы также не нужно deepcopy в data в этом случае (возможно, потребуется его позже функция, я не читал их все...).

Ваш класс будет намного проще, с помощью globals() чтобы получить все функции, чье имя начинается с "sampling_" (технически, все объекты, поэтому если у вас есть переменная с именем, совпадающим, что вы получите сообщение об ошибке и придется фильтра на объект, вызываемый):

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))

Я также сделал свой цикл проще, пробегаем по элементам вместо индексов. Вы, вероятно, следует взглянуть на петли, как родной.

Я даже не уверен, если вы нуждаетесь в этом классе вообще. Вы можете просто сделать это напрямую:

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))

Это сейчас под if __name__ == '__main__' охранник, который гарантирует, что это будет выполняться только, когда вы непосредственно запустите этот скрипт, но не если импортировать части из другого скрипта.


Наконец, в Python есть официальный стиль-руководство, PEP8. Он рекомендует:


  • Не использовать ; в конце строки. Это является совершенно излишним в нормальный код

  • Использовать lower_case для переменных и функций и PascalCase только для классов.

  • Добавить пробелы после запятых, так что range(1, 21)

  • Добавить пробелы вокруг операторов (в том числе =разве при указании сайта Аргументы)

  • Отдельные методы в классы с одной пустой строкой, определения функций вне классов и классов с двумя пустыми строками.

16
ответ дан 1 марта 2018 в 02:03 Источник Поделиться

Кроме того, хорошие очки от @Graipher'ы ответ:


  • Примеры Н° 6, 7, 10, 11, 12, 14, 15, 16, и 20 только одно, что изменять входные данные и, таким образом, только их нужно копировать входные данные не изменить его.

  • Примеры н° 3, 4, 5, 8, 9, 13, и 19 не выполнять правильный отбор.

    Рассмотрим входные данные [1, 0, 0, 0, 0, 0, 0, 0, 0, 0]тогда при выборке двух элементов, могу ли я иметь два типа вывода: два \$0\$ с вероятностью близкой к 90% и одна \$1\$ и одна \$0\$ с вероятностью, близкой к 10%. Используя любой из этих реализации приведет к [0, 1] или [1, 0] 100% времени, что явно далеко за пределы ожидаемых 10%.

    Это потому, что, при попытке выборки без замены, ориентироваться на стоимости в руку вместо элемента. Не в смысле замены не нужно, чтобы выбрать элемент н°\$я$ (за любые \$я$) более чем один раз, это не значит, что я должна исключить дубликаты из их подобрали более чем один раз.


14
ответ дан 1 марта 2018 в 02:03 Источник Поделиться

Еще один момент для меня было бы использовать генераторы вместо функции, возвращающие списки.

Я также хотел извлечь способы вы посмотрите на индексы

Например:

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

Станет

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)

Обычно set также лучше, чтобы проверить, является ли нечто в ней, чем list

10
ответ дан 2 марта 2018 в 09:03 Источник Поделиться