解决anagram时的内存错误

Question

我想解决下面的问题:

anagram是一种文字游戏,是重新排列单词或短语的字母以产生新单词或短语的结果,使用所有原始字母恰好一次; 例如,orchestra = carthorse.使用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.虽然它没有参数是没用的,但有一个参数它非常有用:

从流中读取并返回行列表.可以指定提示来控制读取的行数:如果到目前为止所有行的总大小(以字节/字符为单位)超过提示,则不会再读取行.

因此,f.readlines(1000)让您一次读取大约1K的缓冲区,而不会获得部分线条.当然,现在,split您不必使用换行符,而是必须使用rstrip它们:

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

但是,你还有另外一个问题.如果你一次只能阅读大约100个单词,那么找到一个字谜的可能性非常小.例如,orchestra不会carthorse在字典中的任何地方附近,所以除非你记住整个文件,否则无法找到.但那应该没事; 像web2这样的典型Unix字典有大约200K行; 你可以轻松地将它读入内存并保持它的状态,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时,事情变得有点棘手,但是你想要遵循相同的基本原则:找到让你以恒定或对数时间而不是线性或更糟的方式做事的数据结构,以及找到不需要你通过指数或因子数量的候选人蛮力的算法.