分析显示这是我编写的一个小文字游戏中最慢的代码段:
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个字母的所有单词。 word
包含相同数量字母的单词,因此可以保证word1
和word2
具有相同数量的字符。 结果:
谢谢大家,结合不同的建议,我使程序现在运行的速度提高了两倍(在我问之前我自己做了一些优化,所以速度比最初的实现快了4倍)
我测试了两组输入,分别称为A和B
优化1:遍历word1,2 ...的索引
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个字母的字符串的列表,然后检查以查看单词列表中的哪些字符串,而不是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)
am! 3.74-> 0.23和34.40-> 2.25
与我最初的幼稚实现相比,这真是太神奇了,总的速度差异:
23.79-> 0.23和180.07-> 2.25,因此比原始实现快80到100倍。
如果有人感兴趣,我会写博客文章describing the program和describing the optimizations,其中包括此处未提及的内容(因为它在代码的不同部分)。
大辩论:
好的,我和Unknown正在进行一场大辩论,您可以在his answer的注释中阅读。他声称,如果将其移植到C,使用原始方法(使用is_neighbor而不是使用set)会更快。我尝试了2个小时来获取自己编写的C模块,并尝试将其链接后没有太大的成功请遵循this和this示例,并且在Windows中该过程看起来有些不同?我不知道,但是我放弃了。无论如何,这是程序的完整代码,文本文件来自12dict word list,使用“2 + 2lemma.txt”文件。抱歉,如果代码有点困惑,那只是我一起破解的东西。我也忘记了从单词表中去除逗号,所以实际上这是一个错误,您可以为了进行相同的比较而留在其中,也可以通过在清除条目中的字符列表中添加逗号来修复该错误。
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模块的结果进行比较。
最佳答案
如果您的单词表很长,从“单词”中生成所有可能的1个字母的差异,然后检查列表中的哪些可能更有效?我不知道任何Python,但应该为单词列表提供合适的数据结构,以便进行日志时间查找。
我建议这样做是因为,如果您的单词长度合理(〜10个字母),那么您只会查找250个潜在单词,如果您的单词列表大于几百个单词,这可能会更快。
关于python - 如何优化此Python代码以生成所有单词距离为1的单词?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/788084/