Получить случайную перестановку из списка генераторов известной длины
У меня есть последовательность генераторов, которые дают объекты, требующие разумного объема памяти (они являются экземплярами ipaddress.IPv4Network, и выход из них дает целый экземпляр ipaddress.IPv4Address).
gens = [a, b, c, ...]
Каждый генератор имеет детерминированное количество элементов, которые он выдаст, например:
gen_lens = [17000000, 1024, 8192, ...]
Я хотел бы взять партии полученных значений длины n в случайном порядке. Каждый элемент любого из генераторов должен быть выбран только один раз.
Моя текущая идея состоит в том, чтобы получить общее количество возможных элементов, которые могут быть получены (равные максимальному индексу массива - 1), а затем выполнить итерацию по этому списку в случайном порядке, используя что-то вроде алгоритма Фишера-Йейтса-Кнута, получая элемент заданный случайный индекс:
random_indexes = random.shuffle(range(0, sum(gen_lens)))
for i in random_indexes:
# some windowing logic here to check which generator we should get from and set index appropriately, x = generator index, y = i - sum(gen_lens[0:x])
yield gens[x][y]
Таким образом, конечным результатом является то, что у меня есть новый генератор, который будет давать случайную перестановку всех элементов из моих входных генераторов, без необходимости сохранять все результаты того, что дают мои подгенераторы.
По-прежнему требуется создать список индексов, что довольно дорого, когда у вас есть миллионы индексов. Есть ли способ обойти это? Может ли кто-нибудь предложить лучший подход?
@ scotty3785, который, я думаю, помогает упростить захват элементов со случайным индексом! Но это не касается части случайной перестановки.
ОП, кажется, ваше предложение не учитывает условие: «Каждый элемент из любого из генераторов должен быть выбран только один раз». в партии. Правильно ли я понимаю?
Спасибо @AajKaal - я так думаю, потому что я использую дискретный список всех возможных индексов, поэтому не следует выбирать повторяющиеся элементы ни из одного из генераторов. Я действительно должен отметить, что эти генераторы на самом деле являются подписчиками, что совсем не типично для генератора Python...
Ответы 2
Предложение: следует использовать двумерные индексы. Поскольку заранее генерировать индексы для второго измерения дорого, я делаю это только для одного поколения за раз.
gens = [a, b, c, ...]
gen_lens = [17000000, 1024, 8192, ...]
shuffled_gens_indexes = list(range(len(gens)))
random.shuffle(shuffled_gens_indexes)
for gens_index in shuffled_gens_indexes:
shuffled_gen_items_indexes = list(range(gen_lens[gens_index]))
random.shuffle(shuffled_gen_items_indexes)
for gen_items_index in shuffled_gen_items_indexes:
yield gens[gens_index][gen_items_index]
Это очень просто и просто дает элементы из одного конкретного случайно выбранный генератор за раз.
Это действительно хорошо - было бы даже лучше, если бы рандомизация была для всех генераторов, что, я думаю, может быть достигнуто с помощью арифметики, которую я уже предложил в вопросе (i - sum(gen_lens[0:x]) - но, как вы упомянули, это означает, что мы должны иметь список, длина которого равна сумме всех генераторов.
Если подумать, создание перетасованного списка индексов для каждого генератора таким образом приведет к тому, что вам придется хранить и перетасовывать список длиной до max(gen_lens), что, как мы видим, довольно велико.
Это то, что я сделал в конце. Я считаю, что это решение лучше, чем https://stackoverflow.com/a/65240594/1014237, потому что оно избегает использования random.shuffle, поэтому оно никогда не хранит слишком много элементов (т.е. оно хранит только до вашего batch_length количества случайных индексов, вместо до max(gen_lens) Работа по созданию случайных индексов происходит только при необходимости.
def get_random_element(data, data_length):
pos = data_length
while pos > 0:
idx = random.randrange(start=0, stop=pos)
pos -= 1
if idx != pos:
data[pos], data[idx] = data[idx], data[pos]
yield data[pos]
def get_random_idx_generator(n):
# Create a generator of random indexes, n long
return get_random_element(list(range(n)), n)
Я использую этот генератор с itertools.islice, чтобы хранить столько случайных индексов, сколько мне нужно в данный момент. Функция также использует индекс и длину списков данных, чтобы выяснить, из чего ей нужно читать.
# Yield a batch_size long list of random IPs, using the random idx generator
def get_randomized_ips_batch(ipnetworks_list, ipnetworks_list_lens,
random_idx_generator, batch_size=1024,
as_int=False) -> Iterator[Union[ipaddress.IPv4Address, int]]:
random_indexes_batch = list(itertools.islice(random_idx_generator, batch_size))
# Figure out which ipnetwork_list our index is pointing to and yield it
for idx in random_indexes_batch:
cumulative_len = 0
gen_idx = 0
for ipnetwork_len in ipnetworks_list_lens:
if idx - cumulative_len >= ipnetwork_len:
cumulative_len += ipnetwork_len
gen_idx += 1
continue
else:
addr = ipnetworks_list[gen_idx][idx - cumulative_len - 1]
yield int(addr) if as_int else addr
break
Что такое «gen_idx» и что такое «cumulative_len»? Названия вообще не имеют смысла. Кроме того, ваш ipnetworks_list представляет собой двухмерный массив? Что в нем есть? Это не связано с «gens []» или «gen_lens []» в вопросе о происхождении. Поэтому я не могу понять ваш ответ, и я тоже не могу его запустить. Является ли «random_idx_generator» тем же самым, что и «get_random_idx_generator()»? понизить.
ipnetworks_list и ipnetworks_list_lens эквивалентны gens и gen_lens. Переменные gen_idx и cumulative_len содержат значение, которое определяет, где в списке генераторов должен быть получен элемент, на который ссылается текущий случайный индекс (idx).
Не уверен, что я на 100% понимаю ваш вопрос, но мне кажется, что
itertool.chainможет быть путь вперед. Вы можете объединять итерации вместе без обычных затрат на объединение больших итераций. docs.python.org/3/library/…