代码之家 › 专栏 › 技术社区 › s-m-e

以(伪)随机顺序从大列表中高效地生成元素

generator random python-3.x python

10

s-m-e · 技术社区 · 8 年前

我正在尝试以牺牲内存为代价展开几个嵌套循环,以获得(可能)更好的性能。在我的场景中,我最终会得到一个大约3亿个元素(元组)的列表,我必须以(或多或少)随机顺序生成。

在这个数量级上, random.shuffle(some_list) 真的不再是一条路了。

下面的示例说明了该问题。请注意,在x86\u 64 Linux和CPython 3.6.4上,它将消耗大约11GB的内存。

def get_random_element():
    some_long_list = list(range(0, 300000000))
    for random_item in some_long_list:
        yield random_item

到目前为止,我的想法是只需在每次迭代中生成一个随机索引,并从列表中随机抽取元素(无限期)。它可能多次产生某些元素,并完全跳过其他元素,这是一个值得考虑的权衡。

在内存和CPU时间的合理范围内,我还有哪些其他选项可以只生成列表中的每个元素一次?

1 回复 | 直到 8 年前

1

3

Severin Pappadeux 8 年前

这是Fisher-Yates Knuth就地采样( https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle )

内存稳定,大约4Gb(是的,我使用的是100000000)

# Fisher-Yates-Knuth sampling, in-place Durstenfeld version

import numpy as np

def swap(data, posA, posB):
    if posA != posB:
        data[posB], data[posA] = data[posA], data[posB]

def get_random_element(data, datalen):
    pos = datalen

    while pos > 0:
        idx = np.random.randint(low=0, high=pos) # sample in the [0...pos) range

        pos -= 1
        swap(data, idx, pos)

        yield data[pos]


length = 100000000
some_long_list = list(range(0, length))

gen = get_random_element(some_long_list, length)

for k in range(0, length):
    print(next(gen))

更新

为了提高速度,您可能还需要内联swap()