分析显示这是我编写的一个小文字游戏代码中最慢的部分：
def distance(word1, word2):
difference = 0
for i in range(len(word1)):
if word1[i] != word2[i]:
difference += 1
return difference
def getchildren(word, wordlist):
return [ w for w in wordlist if distance(word, w) == 1 ]
笔记：
distance()被调用超过 500 万次，其中大部分来自 getchildren，它应该获取单词列表中与word恰好相差 1 个字母的所有单词。- wordlist 被预先过滤为仅包含包含相同数量字母的单词，
word因此可以保证word1并且word2具有相同数量的字符。 - 我对 Python 相当陌生（3 天前开始学习它），所以对命名约定或其他样式的评论也很感激。
- 对于单词表，使用“2+2lemma.txt”文件获取12dict 单词表
结果：
谢谢大家，结合不同的建议，我现在让程序运行速度提高了两倍（除了我在询问之前自己进行的优化，所以速度比我最初的实现提高了大约 4 倍）
我用两组输入进行了测试，我将它们称为 A 和 B
优化 1：迭代 word1,2 的索引... from
for i in range(len(word1)):
if word1[i] != word2[i]:
difference += 1
return difference
迭代字母对使用zip(word1, word2)
for x,y in zip (word1, word2):
if x != y:
difference += 1
return difference
输入 A 的执行时间从 11.92 到 9.18，输入 B 的执行时间从 79.30 到 74.59
优化 2：除了距离方法（我在其他地方仍然需要 A* 启发式）之外，还添加了一种单独的方法
def is_neighbors(word1,word2):
different = False
for c1,c2 in zip(word1,word2):
if c1 != c2:
if different:
return False
different = True
return different
输入 A 的执行时间从 9.18 到 8.83，输入 B 的执行时间从 74.59 到 70.14
优化3：这里的大赢家是使用izip而不是zip
输入 A 的执行时间从 8.83 到 5.02，输入 B 的执行时间从 70.14 到 41.69
我可能会更好地用较低级别的语言编写它，但我现在对此感到满意。谢谢大家！
再次编辑：更多结果使用 Mark 的方法检查第一个字母不匹配的情况使其从 5.02 -> 3.59 和 41.69 -> 29.82 下降
在此基础上并合并izip而不是range，我最终得到了这个：
def is_neighbors(word1,word2):
if word1[0] != word2[0]:
return word1[1:] == word2[1:]
different = False
for x,y in izip(word1[1:],word2[1:]):
if x != y:
if different:
return False
different = True
return different
挤压得更多，使时间从 3.59 -> 3.38 和 29.82 -> 27.88
甚至更多的结果！
尝试 Sumudu 的建议，即我生成一个与“word”相差 1 个字母的所有字符串的列表，然后检查哪些字符串在 wordlist中，而不是 is_neighbor 函数，我最终得到了这个：
def one_letter_off_strings(word):
import string
dif_list = []
for i in xrange(len(word)):
dif_list.extend((word[:i] + l + word[i+1:] for l in string.ascii_lowercase if l != word[i]))
return dif_list
def getchildren(word, wordlist):
oneoff = one_letter_off_strings(word)
return ( w for w in oneoff if w in wordlist )
最终速度变慢了（3.38 -> 3.74 和 27.88 -> 34.40），但看起来很有希望。起初我认为我需要优化的部分是“one_letter_off_strings”，但分析显示并非如此，而且慢的部分实际上是
( w for w in oneoff if w in wordlist )
我想如果我切换“oneoff”和“wordlist”并在我正在寻找两个列表的交集时以另一种方式进行比较，是否会有任何区别。我用字母上的 set-intersection替换它：
return set(oneoff) & set(wordlist)
砰！3.74 -> 0.23 和 34.40 -> 2.25
这真是令人惊讶，与我最初的幼稚实现的总速度差异：23.79 -> 0.23 和 180.07 -> 2.25，比原来的实现快大约 80 到 100 倍。
如果有人有兴趣，我会发表博客文章来描述程序并描述所做的优化，包括此处未提及的优化（因为它位于不同的代码部分中）。
大辩论：
好的，我和 Unknown 正在进行一场大辩论，您可以在他的回答的评论中阅读。他声称，如果将其移植到 C 中，使用原始方法（使用 is_neighbor 而不是使用集合）会更快。我尝试了 2 个小时来获得我编写的 C 模块来构建和可链接，但在尝试后没有太大成功按照这个和这个例子，看起来这个过程在Windows中有点不同？我不知道，但我放弃了。无论如何，这是程序的完整代码，文本文件来自12dict单词列表使用“2+2lemma.txt”文件。对不起，如果代码有点乱，这只是我一起破解的。此外，我忘记从单词列表中删除逗号，因此这实际上是一个错误，您可以保留它以进行相同的比较，或者通过在 cleanentries 的字符列表中添加逗号来修复它。
from itertools import izip
def unique(seq):
seen = {}
result = []
for item in seq:
if item in seen:
continue
seen[item] = 1
result.append(item)
return result
def cleanentries(li):
pass
return unique( [w.strip('[]') for w in li if w != "->"] )
def distance(word1, word2):
difference = 0
for x,y in izip (word1, word2):
if x != y:
difference += 1
return difference
def is_neighbors(word1,word2):
if word1[0] != word2[0]:
return word1[1:] == word2[1:]
different = False
for x,y in izip(word1[1:],word2[1:]):
if x != y:
if different:
return False
different = True
return different
def one_letter_off_strings(word):
import string
dif_list = []
for i in xrange(len(word)):
dif_list.extend((word[:i] + l + word[i+1:] for l in string.ascii_lowercase if l != word[i]))
return dif_list
def getchildren(word, wordlist):
oneoff = one_letter_off_strings(word)
return set(oneoff) & set(wordlist)
def AStar(start, goal, wordlist):
import Queue
closedset = []
openset = [start]
pqueue = Queue.PriorityQueue(0)
g_score = {start:0} #Distance from start along optimal path.
h_score = {start:distance(start, goal)}
f_score = {start:h_score[start]}
pqueue.put((f_score[start], start))
parent_dict = {}
while len(openset) > 0:
x = pqueue.get(False)[1]
if x == goal:
return reconstruct_path(parent_dict,goal)
openset.remove(x)
closedset.append(x)
sortedOpen = [(f_score[w], w, g_score[w], h_score[w]) for w in openset]
sortedOpen.sort()
for y in getchildren(x, wordlist):
if y in closedset:
continue
temp_g_score = g_score[x] + 1
temp_is_better = False
appended = False
if (not y in openset):
openset.append(y)
appended = True
h_score[y] = distance(y, goal)
temp_is_better = True
elif temp_g_score < g_score[y] :
temp_is_better = True
else :
pass
if temp_is_better:
parent_dict[y] = x
g_score[y] = temp_g_score
f_score[y] = g_score[y] + h_score[y]
if appended :
pqueue.put((f_score[y], y))
return None
def reconstruct_path(parent_dict,node):
if node in parent_dict.keys():
p = reconstruct_path(parent_dict,parent_dict[node])
p.append(node)
return p
else:
return []
wordfile = open("2+2lemma.txt")
wordlist = cleanentries(wordfile.read().split())
wordfile.close()
words = []
while True:
userentry = raw_input("Hello, enter the 2 words to play with separated by a space:\n ")
words = [w.lower() for w in userentry.split()]
if(len(words) == 2 and len(words[0]) == len(words[1])):
break
print "You selected %s and %s as your words" % (words[0], words[1])
wordlist = [ w for w in wordlist if len(words[0]) == len(w)]
answer = AStar(words[0], words[1], wordlist)
if answer != None:
print "Minimum number of steps is %s" % (len(answer))
reply = raw_input("Would you like the answer(y/n)? ")
if(reply.lower() == "y"):
answer.insert(0, words[0])
print "\n".join(answer)
else:
print "Good luck!"
else:
print "Sorry, there's no answer to yours"
reply = raw_input("Press enter to exit")
我留下了 is_neighbors 方法，即使它没有被使用。这是建议移植到 C 的方法。要使用它，只需将 getchildren 替换为：
def getchildren(word, wordlist):
return ( w for w in wordlist if is_neighbors(word, w))
至于让它作为 C 模块工作，我并没有那么远，但这就是我想出的：
#include "Python.h"
static PyObject *
py_is_neighbor(PyObject *self, Pyobject *args)
{
int length;
const char *word1, *word2;
if (!PyArg_ParseTuple(args, "ss", &word1, &word2, &length))
return NULL;
int i;
int different = 0;
for (i =0; i < length; i++)
{
if (*(word1 + i) != *(word2 + i))
{
if (different)
{
return Py_BuildValue("i", different);
}
different = 1;
}
}
return Py_BuildValue("i", different);
}
PyMethodDef methods[] = {
{"isneighbor", py_is_neighbor, METH_VARARGS, "Returns whether words are neighbors"},
{NULL, NULL, 0, NULL}
};
PyMODINIT_FUNC
initIsNeighbor(void)
{
Py_InitModule("isneighbor", methods);
}
我使用以下方法对此进行了分析：
python -m cProfile "Wordgame.py"
记录的时间是AStar方法调用的总时间。快速输入集是“诗歌诗人”，而长输入集是“诗人诗歌”。不同机器之间的时间显然会有所不同，因此如果有人最终尝试这样做，请按原样比较程序的结果，以及与 C 模块的比较。
