python - 如何优化这段 Python 代码(来自 ThinkPython，练习 10.10)

Question

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

这是练习:

“如果从每个词中交替取字母形成一个新词，则两个词‘互锁’。例如，‘shoe’和‘cold’互锁形成‘schooled’。编写一个程序，找出所有互锁的词对。提示: 不要枚举所有对!”

(对于这些单词列表问题，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