python - 解决七巧板时出现内存错误

Question

我正在尝试解决以下问题：

字谜是一种文字游戏，是重新排列单词或短语的字母以产生一个新单词或短语的结果，而所有原始字母恰好使用一次。例如，乐团=马车。使用http://www.puzzlers.org/pub/wordlists/unixdict.txt处的单词列表，编写一个程序，查找共享相同字符且包含最多单词的单词集。

即使只有1000字节的文件大小，它也会失败。同样，每次创建新列表时，Python为什么将旧列表保留在内存中？我收到以下错误。

l=list(map(''.join, itertools.permutations(i)))

给我：

MemoryError

这是我的代码：

import itertools
def anagram():
    f=open('unixdict.txt')
    f2=open('result_anagram.txt','w')
    words = f.read(1000).split('\n')
    for i in words:
        l=[]
        l=list(map(''.join, itertools.permutations(i)))
        l.remove(i)
        for anagram in l:
            if l==i:
                f2.write(i + "\n")
    return True

anagram()

根据建议将以上代码更改为。但是仍然出现内存错误。

import itertools

def anagram():
    f=open('unixdict.txt')
    f2=open('result_anagram.txt','w')
    words = set(line.rstrip('\n') for line in f)
    for i in words:
        l= map(''.join, itertools.permutations(i))
        l =(x for x in l if x!=i)
        for anagram in l:
            if anagram in words:
                f2.write(i + "\n")
    return True

anagram()

MemoryError
 [在22.2秒内完成]

Answer 1

无论您做什么，该程序都将效率极低。

但是您可以修复此MemoryError，以便永久运行而不是失败。

首先，请注意，一个12个字母的单词具有479,001,600个排列。将所有这些存储在内存中将占用2GB以上的内存。那么，您如何解决呢？只是不要将它们全部存储在内存中。将迭代器保留为迭代器而不是创建列表，然后只需要一次容纳一个，而不是全部都适合。

这里有一个问题：您实际上是在if l==i:行中使用该列表。但这显然是一个错误。字符串列表永远不可能等于单个字符串。您也可以用raise TypeError替换该行，这时您可以替换整个循环，并且可以更快地失败。 :)

我认为您想要的是if anagram in words:。在这种情况下，除了l循环外，您不需要for，这意味着您可以放心地将其保留为惰性迭代器：

for i in words:
    l = map(''.join, itertools.permutations(i))
    l = (x for x in l if x != i)
    for anagram in l:
        if anagram in words:
            f2.write(i + "\n")

我在这里假设使用Python 3.x，因为否则完全不需要 list调用。如果您使用的是2.x，请将该 map替换为 itertools.imap。



附带说明一下， f.read(1000)通常会在结尾处得到一个额外单词的一部分，而下一个循环中将剩下的部分。尝试 readlines。虽然没有参数没有用，但是带有参数却非常有用：


  从流中读取并返回行列表。可以指定hint来控制读取的行数：如果到目前为止所有行的总大小（以字节/字符为单位）超过了hint，将不再读取更多行。


因此， f.readlines(1000)允许您一次读取大约1K的缓冲区，而不会出现部分行。当然，现在，不必必须在换行符上使用 split，而必须对它们进行 rstrip：

words = [line.rstrip('\n') for line in f.readlines(1000)]

但是，您还有另一个问题。如果您一次只能读约100个单词，那么找到字谜的机会就很小。例如，在字典中 orchestra不会在 carthorse附近，因此除非您记得整个文件，否则无法找到。但这应该没问题；典型的Unix字典（例如web2）大约有20万行；您可以轻松地将其读入内存，并以 set的形式保存，而不会在2GB内存上留下任何痕迹。所以：

words = set(line.rstrip('\n') for line in f)

另外，请注意，您正在尝试打印出字典中带有七字谜的每个单词（如果有多个七字谜，请多次打印）。即使使用高效的算法，这也将花费很长的时间，并且会喷出比您可能想要的更多的数据。一种更有用的程序可能是接受输入单词（例如，通过 input或 sys.argv[1]）并仅输出该单词的字谜的程序。



最后：


  即使使用l作为生成器，它也占用了太多的关闭时间，尽管不会因内存错误而失败。您能否解释单词作为一个集合而不是一个列表的重要性。 [完成时间为137.4s]仅200字节，您之前已经提到过，但是如何使用设置的单词克服它？


正如我在顶部说的那样：“无论您做什么，该程序都将效率极低。”

为了找到一个12个字母的单词的字母拼写，您需要进行4.79亿个排列，并对照大约20万个单词的字典检查每个单词，因此每个单词需要479M * 200K = 95万亿个支票。有两种方法可以改善这种情况，第一种涉及为作业使用正确的数据结构，第二种涉及为作业使用正确的算法。

将要从列表中迭代的事物集合更改为生成器（惰性可迭代），会将占用线性空间（479M字符串）的内容转换为占用恒定空间的内容（某个固定大小的迭代器状态，一次添加一个字符串） 。同样，将要检查的单词集合从列表更改为集合，会将花费线性时间的内容（将字符串与列表中的每个元素进行比较）变成花费固定时间的内容（哈希字符串，然后查看其中是否有内容）具有该哈希值的集合）。因此，这消除了问题的 * 200K部分。

但是您仍然遇到问题的 479M部分。而且，您无法通过更好的数据结构来消除这种情况。相反，您必须重新考虑问题。如何在不尝试所有排列的情况下检查单词的任何排列是否与其他单词匹配？

好吧，当且仅当X和Y具有相同的字母时，单词X的某些排列才与单词Y匹配。 X中字母的顺序无关紧要；如果集合相同，则至少有一个匹配的排列（或精确到一个，取决于您对重复字母的计数方式），否则，则有恰好为0。因此，与其遍历单词中的所有排列，查找，只是查找其设置。但是，是否存在重复并不重要，因此您不能仅在此处使用 set。您可以使用某种多集（ collections.Counter）作品…或者，在效率损失极小而简单性却大为提高的情况下，您可以对字母进行排序。毕竟，如果两个单词以任意顺序具有相同的字母，则当它们都进行排序时，它们的字母将具有相同的顺序。

当然，您需要知道哪些词是字谜，而不仅仅是存在一个字谜，因此您不仅要在一组字母集中查找它，还必须在将字母集映射到单词的字典中查找它。例如，如下所示：

lettersets = collections.defaultdict(set)
for word in words:
    lettersets[''.join(sorted(word))].add(word)

因此，现在，要查找单词的字谜，您要做的就是：

anagrams = lettersets[''.join(sorted(word))]

它不仅简单易读，而且是固定时间的。

而且，如果您真的想打印出所有单词的所有字谜的庞大列表...那么，这也很容易：

for _, words in lettersets.items():
    for word in words:
        print('{} is an anagram of {}'.format(word, ', '.join(words - {word})))

现在，与其花费479M * 200K的时间来查找一个单词的字谜，或花费479M * 200K * 200K的时间来查找所有单词的字谜，不如花费一个恒定的时间来查找一个单词的字谜，或花费200K的时间来查找单词的所有字谜。所有的话。 （当然，开始创建映射需要添加200K的设置时间，但是预先花200K的时间来节省200K，少得多的479M * 200K，每次查找的时间显然是一个胜利。）

当您想要进行某些操作时，事情变得有些棘手，例如，找到部分字谜或句子anagarms，但是您想要遵循相同的基本原理：找到可以在恒定或对数时间内而不是线性或更差的时间内进行操作的数据结构，以及查找不需要您通过指数或阶乘候选数来蛮横行事的算法。