0

这是我的代码和一些注释：

import re
import itertools

nouns = ['bacon', 'cheese', 'eggs', 'milk', 'houses', 'dog']
CC = ['and', 'or']

def search_and_replace(text):
    noun_patt = r'\b(' + '|'.join(nouns) + r')\b'
    CC_patt = r'\b(' + '|'.join(CC) + r')\b'
    patt = r'({0},? )+{1} {0}'.format(noun_patt, CC_patt)

    searched = re.search(patt, text) 
    phrase = searched.group()
    print "Check re.search match object exists:", phrase # "bacon, eggs, and milk" prints

    perm_phrase = itertools.permutations(phrase)
    print "Check permutated list exists:", perm_phrase # permutation object position in memory prints

    perm_phrase_list = list(perm_phrase)
    print "Permutated object as list:", perm_phrase_list # THIS IS WHERE MEMORY MAXES AND COMPUTER FREEZES!!!
    # So print does not happen.

    return perm_phrase_list

def main():
    text = "I like bacon, eggs, and milk"
    print search_and_replace(text)


if __name__ == '__main__':
    main()

从我在代码中的注释可以看出，这行代码perm_phrase_list = list(perm_phrase)占用了太多的物理内存，以至于我的电脑死机了。（我在每行代码之后打印以找出问题开始的位置，我通常不会在函数中打印）。我想知道为什么在尝试从排列创建此列表时会发生这种情况？

如果我可以在这段代码中使用 permutations 方法将非常方便！否则，我只需要创建等效的东西来重新排序列表中的元素。

我正在使用 Python 2.7

4

3 回答 3

3

您正在将字符串喂给itertools.permutations(); 这意味着它将为所有可能的字符组合生成排列：

>>> phrase = re.search(patt, text).group()
>>> phrase
'bacon, eggs, and milk'
>>> next(itertools.permutations(phrase))
('b', 'a', 'c', 'o', 'n', ',', ' ', 'e', 'g', 'g', 's', ',', ' ', 'a', 'n', 'd', ' ', 'm', 'i', 'l', 'k')

您的短语有 21 个字符长，结果为 21！（阶乘）== 51090942171709440000 种不同的排列；每个 21 个字符的元组。

在我的 64 位 Mac 上，一个这样的元组总共需要 21 * 38 + 224 字节 = 1022 字节的内存。字符是实习的，所以你真的只需要每个元组的内存，并且可以忽略字符的 768 个字节。那就是 51090942171709440000 * 224 bytes 几乎是10 zebibytes。

那是一个完整的记忆。

您可能不想生成短语的所有可能的 21 个字符排列。你需要重新考虑你想用你的方法做什么，生成更少的输出并且只一个一个地循环生成的组合，而不是尝试将它们全部扩展成一个列表对象。

我怀疑您想为任何匹配的单词创建排列，但是您的正则表达式不会为您提供单独的匹配单词。您不能重复捕获组，您需要捕获整个，然后拆分：

noun_patt = r'\b(?:' + '|'.join(nouns) + r')\b'
CC_patt = r'\b(' + '|'.join(CC) + r')\b'
patt = r'((?:{0},? )+){1} ({0})'.format(noun_patt, CC_patt)

这些(?:..)组是非捕获组，以避免混淆我们的结果。

这现在给出了两个捕获组，一个带有逗号分隔的名词，一个带有最后一个名词。在空格和逗号上拆分第一个：

searched = re.search(patt, text) 
nouns = filter(None, re.split(r',\s*', searched.group(1))) + [searched.group(3)]

现在您可以排列这些名词：

for comb in itertools.permutations(nouns):
    # do something with this specific permutation

因为您的样本只产生 3 个名词，所以 6 个排列可以安全地变成一个列表：

>>> nouns
['bacon', 'eggs', 'milk']
>>> list(itertools.permutations(nouns))
[('bacon', 'eggs', 'milk'), ('bacon', 'milk', 'eggs'), ('eggs', 'bacon', 'milk'), ('eggs', 'milk', 'bacon'), ('milk', 'bacon', 'eggs'), ('milk', 'eggs', 'bacon')]

我们也许可以将它们重新组合成句子：

>>> cc = searched.group(2)
>>> for comb in itertools.permutations(nouns):
...     print ', '.join(comb[:-1]), cc, comb[-1]
... 
bacon, eggs and milk
bacon, milk and eggs
eggs, bacon and milk
eggs, milk and bacon
milk, bacon and eggs
milk, eggs and bacon
于 2013-09-23T19:15:55.920 回答
1

该行代码perm_phrase_list = list(perm_phrase)将尝试构建一个列表。如果它非常大，可能会占用大量内存，因此您不应该这样做。要“转储”结果，您应该遍历生成器：

for item in perm_phrase: print item #doesn't build the list
于 2013-09-23T19:02:17.883 回答
1

首先，您没有任何充分的理由将所有值存储在列表中；您可以像遍历列表一样轻松地遍历迭代器。所以，只需返回perm_phrase。如果您只想打印出值，请编写如下内容：

def main():
    text = "I like bacon, eggs, and milk"
    for perm in search_and_replace(text):
        print perm

显然，您可以根据需要设置格式，包括添加括号和逗号并打印repr(perm)以使其看起来完全像一个列表。

通过迭代迭代器，您一次只生成一个值，而不是一次生成所有值，因此不存在内存存储问题。（您还可以通过“流水线化”每个排列的代码来提高速度，提高缓存命中率等）

但与此同时，您的问题是您想要 (4! = 24) 的单词排列，而不是 (21! = 51090942171709440000) 的字符排列。为此，您需要split在某个时候将字符串转换为单词。例如：

perm_phrase = itertools.permutations(phrase.split())

现在，您可以轻松地将所有这些内容一次性放入内存中。但是你最好还是使用迭代器，除非你有充分的理由将它们一次全部存储在内存中。

于 2013-09-23T19:21:29.043 回答