Python: itertools.product 消耗太多资源

Question

我创建了一个 Python 脚本，它通过字符排列生成单词列表。我正在使用 itertools.product 来生成我的排列。我的字符列表由字母和数字组成 01234567890abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVXYZ。这是我的代码：

#!/usr/bin/python
import itertools, hashlib, math

class Words:

    chars = '01234567890abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVXYZ'

    def __init__(self, size):
        self.make(size)

    def getLenght(self, size):
        res = []
        for i in range(1, size+1):
            res.append(math.pow(len(self.chars), i))
        return sum(res)

    def getMD5(self, text):
        m = hashlib.md5()
        m.update(text.encode('utf-8'))
        return m.hexdigest()

    def make(self, size):
        file = open('res.txt', 'w+')
        res = []
        i = 1
        for i in range(1, size+1):
            prod = list(itertools.product(self.chars, repeat=i))
            res = res + prod
        j = 1
        for r in res:
            text = ''.join(r)
            md5 = self.getMD5(text)
            res = text+'\t'+md5
            print(res + ' %.3f%%' % (j/float(self.getLenght(size))*100))
            file.write(res+'\n')
            j = j + 1
        file.close()

Words(3)

此脚本适用于最多 4 个字符的单词列表。如果我尝试 5 或 6 个字符，我的计算机会消耗 100% 的 CPU、100% 的 RAM 并死机。

有没有办法限制这些资源的使用或优化这种繁重的处理？

Answer 1

这是你想要的吗？

我已经在 make 方法中进行了所有更改：

def make(self, size):

    with open('res.txt', 'w+') as file_: # file is a builtin function in python 2
        # also, use with statements for files used on only a small block, it handles file closure even if an error is raised.
        for i in range(1, size+1):
            prod = itertools.product(self.chars, repeat=i)

            for j, r in enumerate(prod):
                text = ''.join(r)
                md5 = self.getMD5(text)
                res = text+'\t'+md5
                print(res + ' %.3f%%' % ((j+1)/float(self.get_length(size))*100))
                file_.write(res+'\n')

请注意，这仍会消耗 GB 的内存，但不会消耗虚拟内存。

编辑：正如 Padraic 所指出的，在 Python 3 中没有 file 关键字，因为它是 "bad builtin"，所以不太担心覆盖它。尽管如此，我仍将其命名为 file_。

编辑 2：

要解释为什么它比以前的原始版本更快更好，您需要了解 lazy 评估的工作原理。

假设我们有一个简单的表达式如下 (for Python 3) (use xrange for Python 2):

a = [i for i in range(1e12)]

这会立即将 1 万亿个元素计算到内存中，使您的内存溢出。

所以我们可以使用生成器来解决这个问题：

a = (i for i in range(1e12))

这里，none 个值已经被评估，只是给出了如何评估它的解释器说明。然后我们可以 一个一个 遍历每个项目并分别处理每个项目，因此在给定时间内存中几乎没有任何内容（一次只有 1 个整数）。这使得看似不可能的任务变得非常易于管理。

itertools 也是如此：它允许您通过使用迭代器而不是列表或数组来执行操作来执行内存高效、快速的操作。

在您的示例中，您有 62 个字符，并且想要重复 5 次或 62**5（将近 10 亿个元素，或超过 30 GB 的 ram）的笛卡尔积。这太大了。"

为了解决这个问题，我们可以使用迭代器。

chars = '01234567890abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVXYZ'
for i in itertools.product(chars, repeat=5):
    print(i)

在这里，在给定时间只有笛卡尔积中的一个项目在内存中，这意味着它的内存效率非常高。

但是，如果您使用 list() 计算完整的迭代器，它会耗尽迭代器并将其添加到列表中，这意味着将近 10 亿个组合突然再次出现在内存中。我们不需要一次将所有元素存储在内存中：只需 1 个即可。这就是迭代器的强大之处。

这里是 itertools module and another explanation on iterators in Python 2 的链接（3 大部分是正确的）。

Python: itertools.product 消耗太多资源

Python: itertools.product consuming too much resources

python

permutation

itertools