我有一系列生成器,这些生成器产生需要合理内存的对象(它们是ipaddress.IPv4Network实例,从中产生一个完整的ipaddress.IPv4Address实例)。
gens = [a, b, c, ...]每个发生器产生的元素数量是确定的,例如:
gen_lens = [17000000, 1024, 8192, ...]我想按随机顺序取一批n长度的已得到的值。任何生成器中的每个项目只能选择一次。
我目前的想法是获取可以产生的可能元素的总数(等于最大数组索引- 1),然后使用Fisher-Yates-Knuth算法这样的随机顺序遍历这个列表,生成给定随机索引的项:
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]因此,最终的结果是,我有一个新的生成器,它将从我的输入生成器中产生一个所有元素的随机排列,而不必存储我的子生成器产生的所有结果。
它仍然需要构建一个索引列表,当您有数百万个索引时,这是相当昂贵的。有办法绕过吗?有人能提出更好的方法吗?
发布于 2020-12-15 12:08:15
这就是我最后所做的。我认为这个解决方案比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发布于 2020-12-10 18:53:23
建议:采用二维指标。由于预先生成第二维度的索引很昂贵,所以每次只生成一次索引。
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]这是非常直截了当的,并简单地给出项目从一个特定的随机选择生成器在一次。
https://stackoverflow.com/questions/65238921
复制相似问题