首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >从已知长度的生成器列表中产生随机排列

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

Stack Overflow用户
提问于 2020-12-10 16:59:21
回答 2查看 153关注 0票数 0

我有一系列生成器,这些生成器产生需要合理内存的对象(它们是ipaddress.IPv4Network实例,从中产生一个完整的ipaddress.IPv4Address实例)。

代码语言:javascript
复制
gens = [a, b, c, ...]

每个发生器产生的元素数量是确定的,例如:

代码语言:javascript
复制
gen_lens = [17000000, 1024, 8192, ...]

我想按随机顺序取一批n长度的已得到的值。任何生成器中的每个项目只能选择一次。

我目前的想法是获取可以产生的可能元素的总数(等于最大数组索引- 1),然后使用Fisher-Yates-Knuth算法这样的随机顺序遍历这个列表,生成给定随机索引的项:

代码语言:javascript
复制
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]

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

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

EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2020-12-15 12:08:15

这就是我最后所做的。我认为这个解决方案比https://stackoverflow.com/a/65240594/1014237更好,因为它避免使用random.shuffle,所以它从不存储太多的元素(也就是说,它只存储到随机索引的batch_length数,而不是max(gen_lens)。生成随机索引的工作只在需要时进行。

代码语言:javascript
复制
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从这个生成器中消费,所以我在给定的时刻只存储我需要的任意数量的索引。该函数还使用索引和数据列表的长度来确定需要读取的内容。

代码语言:javascript
复制
# 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
票数 0
EN

Stack Overflow用户

发布于 2020-12-10 18:53:23

建议:采用二维指标。由于预先生成第二维度的索引很昂贵,所以每次只生成一次索引。

代码语言:javascript
复制
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]

这是非常直截了当的,并简单地给出项目从一个特定的随机选择生成器在一次。

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/65238921

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档