如何优化这段Python代码（来源于ThinkPython，第10.10题）

Question

我正在学习艾伦·道尼的《如何像计算机科学家一样思考》，并且我写了一个我认为是正确的解决方案来完成第10.10题。但是，这个程序运行了超过10个小时（！），所以我在想是不是漏掉了一些很明显的优化方法。

题目是：

“两个单词如果交替取字母能组成一个新单词，就叫做‘交错’。比如，‘shoe’和‘cold’交错可以组成‘schooled’。写一个程序，找出所有可以交错的单词对。提示：不要列举所有的单词对！”

（对于这些单词列表的问题，道尼提供了一个包含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对这样的单词。问题在于嵌套循环，对吧？我的意思是，即使我只在处理长度相同的单词列表，长度为7的单词就有21727个，这意味着我的程序必须检查超过4亿个“交错组合”来看看它们是否是真正的单词——而这仅仅是针对长度为7的单词。

所以，这段代码运行了10个小时（而且没有找到任何长度为5或更长的单词对，如果你感兴趣的话）。有没有更好的方法来解决这个问题？

提前感谢任何见解。我知道“过早优化是万恶之源”——也许我已经陷入了这个陷阱——但一般来说，虽然我通常能写出正确运行的代码，但我常常在写出运行效率好的代码上遇到困难。

Answer 1

交锁的另一种定义：

import itertools

def interlock(str1, str2):
    "Takes two strings of equal length and 'interlocks' them."
    return ''.join(itertools.chain(*zip(str1, str2)))

Answer 2

这是一个替代版本：

with open('words.txt') as inf:
    words = set(wd.strip() for wd in inf)

word_gen = ((word, word[::2], word[1::2]) for word in words)
interlocked = [word for word,a,b in word_gen if a in words and b in words]

在我的电脑上，这段代码运行了0.16秒，返回了1254个单词。

---

编辑：正如@John Machin在为什么这个程序在Python中比在Objective-C中快？中指出的，这可以通过懒执行来进一步优化（只有在第一次切片得到有效单词时才执行第二次切片）：

with open('words.txt') as inf:
    words = set(wd.strip() for wd in inf)
interlocked = [word for word in words if word[::2] in words and word[1::2] in words]

这样执行时间减少了三分之一，变成了0.104秒。

Answer 3

换个方式来做：遍历所有的单词，把它们分成两个单词，一个取奇数位置的字母，另一个取偶数位置的字母。然后在字典里查找这两个单词。

顺便提一下，这两个交错的单词不一定要长度相同——它们的长度也可以相差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