python - 使用 itertools 的排列爆炸内存

Question

我正在使用 itertools 中的排列来制作句子 block 列表的可能组合列表，但即使在我的 64GB 机器上，它似乎也会很快地消耗内存。在内存管理方面我不是最好的，所以我想了解如何使我的代码更好。如果我可以计算出包含数千个这样的 block 的列表，那就太好了。现在我只能买得起10个。

import itertools
from os import sys

arq_in = sys.argv[1]
f1 = open(arq_in, 'r')

list_items = []
items = []

lines = f1.readlines()
for line in lines:
    line =line.strip()
    list_items.append(line)

for L in range(0, len(list_items)+1):
    for subset in itertools.permutations(list_items, L):
        items.append(subset)

output = "\n".join(" ".join(map(str,l)) for l in items)
print output

这是我的输入:

ah k l ih r ih ng hh w ae r
ah s eh k ih n d t w ih ch t
ah s iy k r ih t w ah r l d
ah s l iy p ih ng k ae p s l
ah v ay t ah m ah n ae n d
d aw n ih n b ih k ah r ih ng
d ey t ah p oy n t s ih n
ey jh ih n s iy hh ay ah r d ah
f ih ng g ah r hh ae d ah
ih g z ih s t ih n w ao r m
ih k s p r eh sh ih n ih n dh ah
ih n d ah l jh ih n ae n
ih n m ay ey jh ih n s iy
ih n v eh s t ih n b l ae k
ih z m eh zh ah r d ih n
m ae ch ih ng y aa r n ih n
r iy d ih ng ih n p uh r
s ah ch ah d ih z ae s t ah r
s ih s t ah m ae n d ae d
th r eh d m ae ch ih ng y aa r n

Answer 1

按照以下方式运行它将确保您不会耗尽内存，因为我们使用的是惰性求值(这意味着，我们只会在需要时才计算下一次迭代)。

这种方法的优点是不将整个事情保留在内存中，因此即使它仍然会运行很长时间直到完成(它在我的机器上运行一个多小时并且还没有完成!)但它不会崩溃:

import itertools
from os import sys

def lazy_iter(lines):
    list_items = []
    for line in lines:
        line =line.strip()
        list_items.append(line)

    for L in range(0, len(list_items)+1):
        for subset in itertools.permutations(list_items, L):
            yield subset


if __name__ == "__main__":
    arq_in = sys.argv[1]
    f1 = open(arq_in, 'r')
    lines = f1.readlines()    
    for l in lazy_iter(lines):
        print map(str,l)

假设您确实不想将任何此类 l 作为字符串进行打印，则可以将迭代限制为仅针对您想要生成的项目数运行并按照您的需要对它们中的每一个进行操作。