Получение случайных выборок из генератора python

ProgramBox

Получение случайных выборок из генератора python

Post author:admin
Запись опубликована:16 марта, 2023
Post category:Вопросы по программированию

#python #python-3.x #random #itertools

#python #python-3.x #Случайный #python-itertools

Вопрос:

Я использую функцию for pair in itertools.combinations(bug_map.keys(), 2): для генерации всех пар элементов в моей базе данных. Проблема в том, что количество элементов составляет около 6,6 Тыс., и поэтому количество комбинаций составляет 21,7 М. Кроме того, комбинации генерируются в порядке лексикографической сортировки.

Предположим, что я бы взял случайные пары из генератора, не «выдавая» их все (только подмножество n размерности), что я могу сделать?

1. Разве вы не можете полностью отказаться от генератора и просто выбирать случайные ключи bug_map.keys() ?

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

3. Я не понимаю, чем выбор пар случайных ключей отличается в «ранжировании вероятности» от попыток выбора случайных элементов combinations . Возможно, вы хотели бы более подробно рассказать об этом в своем вопросе.

4. Сколько случайных комбинаций вы хотите сгенерировать? Это более актуально, как может показаться, поскольку это влияет на вероятность столкновений и, следовательно, на то, как с ними обращаться.

5. @tobias_k Как я понял из вопроса, количество комбинаций, генерируемых случайным образом, должно быть значительно меньше общего количества возможных комбинаций. По крайней мере, спрашивающий попросил бы заменить все комбинации только случайным подмножеством.

Ответ №1:

Если вам разрешено получать все 6K элементы в виде списка, вы сначала получаете их все, а затем используете стандартные python random.choices() для генерации пакета выборок с заменой. Затем примените сортировку (по мере сортировки комбинаций). Затем удалите кортежи, которые имеют один и тот же элемент внутри дважды или более, и кортежи, которые равны. Повторяйте пакетную генерацию, пока мы не получим достаточное n количество кортежей.

Вы можете указать any k как длину желаемых кортежей для генерации в моем коде, а n также как количество кортежей k-длины для генерации.

Этот алгоритм генерирует аналогичный шаблон распределения вероятностей, создавая все комбинации k длины, а затем выбирая случайное подмножество размера n .

Попробуйте онлайн!

 import random

#random.seed(0) # Do this only for testing to have reproducible random results

l = list(range(1000, 1000   6600)) # Example list of all input elements

k = 2 # Length of each tuple to generate
n = 30 # Number of tuples to generate

batch = max(1, n // 4) # Number of k-tuples to sample at once
maybe_sort = lambda x: sorted(x) if is_sorted else x

res = []

while True:
    if len(res) >= n:
        res = res[:n]
        break
    a = random.choices(range(len(l)), k = k * batch) # Generate random samples from inputs with replacement
    a = sorted(res   [tuple(sorted(a[i * k   j] for j in range(k))) for i in range(batch)])
    res = [a[0]]
    for e in a[1:]:
        if all(e0 != e1 for e0, e1 in zip(e[:-1], e[1:])) and res[-1] != e:
            res.append(e)

print([tuple(l[i] for i in tup) for tup in res])

1. Вы рисуете с заменой, когда вы должны рисовать без замены. Вам нужно random.sample .

2. Я вижу, что вы делаете это, чтобы не получать одну и ту же комбинацию дважды (как вы могли бы, просто повторно вызывая sample с размером выборки 2), но таким образом вы также никогда не сможете получить две комбинации, которые разделяют только один элемент.

3. @tobias_k Когда вы написали этот комментарий, я уже понял это раньше и был на полпути к внедрению нового алгоритма, основанного на случайной совокупности with replacemenent . Обновлено описание и код. Для меня этот алгоритм теперь выглядит как правильный.

4. @F.Petrulio Мой алгоритм, приведенный выше, реализован на чистом Python, потому что вы сказали, что есть только 6.5K элементы, для обработки которых в таком алгоритме в чистом Python требуется доля секунды. Если проблема в производительности, я могу легко повторно реализовать свой алгоритм numpy , просто скажите.

5. Кроме того, если в моем алгоритме есть какие-то математические проблемы, мы можем найти правильное исправление, и я его улучшу.

Ответ №2:

Это может показаться тривиальным, но если желаемое количество выборок значительно меньше общего количества возможных комбинаций (21,8 M), то вы можете просто повторно генерировать a ramdom.sample , пока у вас не будет достаточно много. Могут быть коллизии, но (опять же, если требуемое количество выборок сравнительно мало) вероятность для них будет незначительной и не приведет к замедлению.

 import random

lst = range(6000)
n = 1000000
k = 2

samples = set()
while len(samples) < n:
    samples.add(tuple(random.sample(lst, k)))

Даже для 1 000 000 случайных выборок это привело только к ~ 12 тыс. столкновений, т. Е. Около 1% «потраченных впустую» итераций, что, вероятно, не такая уж большая проблема.

Обратите внимание, что, кроме combinations , пары, возвращаемые ramdom.sample не упорядочены (первый элемент может быть больше второго), поэтому вы можете использовать tuple(sorted(...))