Произвольная выборка из большого комбинированного генератора - PullRequest
Новая
       31

Произвольная выборка из большого комбинированного генератора

2 голосов
/ 30 апреля 2019

На высоком уровне я пытаюсь сэмплировать элементы n_samples по всем комбинациям из n элементов из списка.При небольших значениях n и сравнительно небольшой длине списка (n <= 5, len (list) <75) это нормально - я просто использую itertools для генерации комбинаций, преобразования в список и случайной выборки правильного числа с использованием random.sample,</p>

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

Это создаетпроблема при больших значениях n и len (list) - с 120 элементами списка и n = 5, этот сценарий использования означает, что мне приходится многократно выполнять преобразование списка, и поэтому я становлюсь ограниченным по времени из-за генератора -> преобразования списка длягенератор с ~ 190 миллионами предметов.Это занимает очень много времени (более 20 минут для особо плохих примеров).

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

Я перешел на использование метода iterator.islice, чтобы брать только первые элементы n_samples из генератора и использовать их.Это резко увеличивает скорость (пример, который занимал 20 минут, теперь занимает 34 секунды), но производительность поражает.Я думаю, это связано с тем, как itertools генерирует комбинации - например, 

list(itertools.combinations(list(range(4)), 2))

создает этот список: [(0, 1), (0, 2), (0, 3), (1,2), (1, 3), (2, 3)]

, поэтому кажется, что если у меня достаточно длинный список и достаточно большой n, выборка даже 100 000+ элементов, просто потянув их с генератораприведет к 100 000+ предметов, где первый элемент такой же, что не идеально.Как я уже сказал, мне не нужна идеальная случайная выборка, но я думаю, что это связано с падением производительности при использовании этого метода вместо случайной выборки по всему списку.

По сути, мне нужен хороший способэффективно выбирать элементы n_samples (где n_samples где-то от 10k до 500k) из всех возможных комбинаций длины n (где n обычно находится в диапазоне около 2-8) из списка длин, который может варьироваться от ~ 20 до ~ 200.

Большое спасибо за любые советы или ресурсы, которые вы можете предоставить!

1 Ответ

1 голос
/ 01 мая 2019

Исходя из того, что вы описываете, я считаю, что у вас будет намного более эффективный алгоритм, если вы выберете каждый компонент случайным образом, независимо от других, и продолжите, пока у вас не будет необходимого образца.ГСЧ (генераторы случайных чисел) достаточно быстрые, чтобы восполнить необходимость замены случайного дубликата.Сохраните выбранные вами комбинации в виде набора кортежей (хэшируемого), и вы сможете искать включение набора в постоянное время, делая коллекцию линейным временем.Примерно так: 

from random import randint

# For illustration, the "lsits" include letters, symbols, 3-letter words, and low primes
list1 = "pythonic"
list2 = "~!@#$%^&*()"
list3 = ["dog", "cat", "ape", "red", "cwm", "pox"]
list4 = [2, 3, 5, 7, 11, 13, 17, 19]

combo = [list1, list2, list3, list4]
my_sample = set()
needed_size = 10

while len(my_sample) < needed_size:
    # Choose one random item from each list; that forms an element
    elem = tuple([comp[randint(0, len(comp)-1)] for comp in combo])
    # Using a set elminates duplicates easily
    my_sample.add(elem)

print(my_sample)

Вывод: 

{('h', '$', 'pox', 7),
 ('y', '(', 'cat', 11),
 ('n', '@', 'cat', 7),
 ('i', '^', 'ape', 13),
 ('y', '#', 'pox', 11),
 ('o', '%', 'dog', 7),
 ('p', '^', 'cwm', 13),
 ('c', '*', 'dog', 19),
 ('o', ')', 'pox', 11),
 ('h', '~', 'cat', 5)}

Другая возможность - сгенерировать одно случайное число в диапазоне произведений длин (8 *10 * 6 * 8 в данном случае), а затем используйте целочисленное деление и mod, чтобы разбить это на четыре случайных индекса.

Еще одна возможность - просто сгенерировать первый набор случайных индексов, а затемувеличивайте их по своему усмотрению, по очереди просматривая списки.В этом случае вы захотите, чтобы длины вашего списка были попарно взаимно простыми;Вы можете гарантировать это, добавляя элемент None по мере необходимости.Любая комбинация с None отбрасывается.

Эти идеи заставляют вас двигаться?

...