我正在从 Allen Downey 的 Think Python 中学习 python，我在这里的练习 6 被困住了。我为它写了一个解决方案，乍一看，它似乎比这里给出的答案有所改进。但是在运行两者后，我发现我的解决方案需要一整天（约 22 小时）来计算答案，而作者的解决方案只需要几秒钟。谁能告诉我作者的解决方案如何如此之快，当它遍历包含 113,812 个单词的字典并对每个单词应用递归函数以计算结果时？
我的解决方案：
known_red = {'sprite': 6, 'a': 1, 'i': 1, '': 0} #Global dict of known reducible words, with their length as values
def compute_children(word):
"""Returns a list of all valid words that can be constructed from the word by removing one letter from the word"""
from dict_exercises import words_dict
wdict = words_dict() #Builds a dictionary containing all valid English words as keys
wdict['i'] = 'i'
wdict['a'] = 'a'
wdict[''] = ''
res = []
for i in range(len(word)):
child = word[:i] + word[i+1:]
if nword in wdict:
res.append(nword)
return res
def is_reducible(word):
"""Returns true if a word is reducible to ''. Recursively, a word is reducible if any of its children are reducible"""
if word in known_red:
return True
children = compute_children(word)
for child in children:
if is_reducible(child):
known_red[word] = len(word)
return True
return False
def longest_reducible():
"""Finds the longest reducible word in the dictionary"""
from dict_exercises import words_dict
wdict = words_dict()
reducibles = []
for word in wdict:
if 'i' in word or 'a' in word: #Word can only be reducible if it is reducible to either 'I' or 'a', since they are the only one-letter words possible
if word not in known_red and is_reducible(word):
known_red[word] = len(word)
for word, length in known_red.items():
reducibles.append((length, word))
reducibles.sort(reverse=True)
return reducibles[0][1]