如何优化这个Python代码(来自ThinkPython,练习10.10)

Question

我正在研究Allen Downey的" 如何像计算机科学家一样思考",并且我已经编写了我认为是练习10.10的功能正确的解决方案.但是运行起来只需要10个多小时(!),所以我想知道我是否缺少一些非常明显且有用的优化.

这是练习:

"两个单词'互锁',如果从每个单词中取代交替的字母形成一个新单词.例如,'shoe'和'cold'互锁形成'schooled'.编写一个程序,找到所有互锁的单词对.提示:Don'列举所有对!"

(对于这些单词列表问题,Downey提供了一个包含113809个单词的文件.我们可以假设这些单词在列表中,列表中每个项目一个单词.)

这是我的解决方案:

from bisect import bisect_left

def index(lst, target):
    """If target is in list, returns the index of target; otherwise returns None"""
    i = bisect_left(lst, target)
    if i != len(lst) and lst[i] == target:
        return i
    else:
        return None

def interlock(str1, str2):
    "Takes two strings of equal length and 'interlocks' them."
    if len(str1) == len(str2):
        lst1 = list(str1)
        lst2 = list(str2)
        result = []
        for i in range(len(lst1)):
            result.append(lst1[i])
            result.append(lst2[i])
        return ''.join(result)
    else:
        return None

def interlockings(word_lst):
    """Checks each pair of equal-length words to see if their interlocking is a word; prints each successful pair and the total number of successful pairs."""
    total = 0
    for i in range(1, 12):  # 12 because max word length is 22
        # to shorten the loops, get a sublist of words of equal length
        sub_lst = filter(lambda(x): len(x) == i, word_lst)
        for word1 in sub_lst[:-1]:
            for word2 in sub_lst[sub_lst.index(word1)+1:]: # pair word1 only with words that come after word1
                word1word2 = interlock(word1, word2) # interlock word1 with word2
                word2word1 = interlock(word2, word1) # interlock word2 with word1
                if index(lst, word1word2): # check to see if word1word2 is actually a word
                    total += 1
                    print "Word 1: %s, Word 2: %s, Interlock: %s" % (word1, word2, word1word2)
                if index(lst, word2word1): # check to see if word2word1 is actually a word
                    total += 1
                    print "Word 2, %s, Word 1: %s, Interlock: %s" % (word2, word1, word2word1)
    print "Total interlockings: ", total

印刷报表不是问题; 我的程序只发现了652对这样的对.问题是嵌套循环,对吧？我的意思是,即使我循环遍历仅包含相同长度的单词的列表,也有(例如)21727个长度为7的单词,这意味着我的程序必须检查超过4亿个"联锁"以查看它们是否'重新实际的话 - 这只是长度为7个字.

所以再次,这段代码需要10个小时才能运行(并且发现没有涉及长度为5或更长的单词的对,以防你好奇).有没有更好的方法来解决这个问题？

提前感谢任何和所有的见解.我知道"过早的优化是所有邪恶的根源" - 也许我已经陷入了这个陷阱---但总的来说,虽然我通常可以编写正确运行的代码,但我经常会遇到写作困难代码运行良好.

Answer 1

反过来说:迭代所有单词并通过取奇数和偶数字母将它们分成两个单词.然后在字典中查找这两个单词.

作为一个侧节点,互锁的两个单词不一定必须具有相同的长度 - 长度也可能相差1.

一些(未经测试的)代码:

words = set(line.strip() for line in open("words"))
for w in words:
    even, odd = w[::2], w[1::2]
    if even in words and odd in words:
        print even, odd