从已知长度的生成器列表中产生一个随机排列

Question

我有一系列生成器，它们生成需要合理内存量的对象（它们是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]

最终的结果是，我有了一个新的生成器，它将生成输入生成器中所有元素的随机排列，而不必存储子生成器生成的结果

它仍然需要构建一个索引列表，当您有数百万个索引时，这是相当昂贵的。有办法吗？有人能提出更好的方法吗

Answer 1

建议：应使用二维索引。因为预先为第二维度生成索引是很昂贵的，所以我一次只做一代

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]

这非常简单，只需从一个特定的 一次随机选择一个生成器

Answer 2

这就是我最后所做的。我相信这个解决方案比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