如何优化此Python代码以生成word-distance 1的所有单词？

Question

分析显示这是我写的一个小字游戏的代码中最慢的部分:

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,它应该让wordlist中的所有单词与word1个字母完全不同.
• wordlist被预先过滤为只有包含相同数量字母的单词,word所以它保证word1并word2具有相同数量的字符.
• 我是Python的新手(3天前开始学习它)所以对命名约定或其他风格的东西的评论也很受欢迎.
• 对于wordlist,使用"2 + 2lemma.txt"文件获取12dict单词列表

结果:

谢谢大家,通过不同建议的组合,我现在运行程序的速度提高了两倍(除了我自己在询问之前做的优化之外,所以从初始实现开始,速度提高了4倍)

我测试了2组输入,我称之为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个字母的所有字符串,然后检查哪些字符串在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"会有什么不同,并且当它碰到我时我正在寻找2个列表的交集时,做了比较.我用字母上的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正在进行一场大辩论,你可以在他的回答评论中看到.他声称使用原始方法(使用is_neighbor而不是使用集合)会更快,如果它被移植到C.我尝试了2个小时来获得我编写的C模块,并且在尝试之后可以链接而没有太大成功按照这个和这个例子,看起来这个过程在Windows中有点不同？我不知道,但我放弃了.无论如何,这是程序的完整代码,文本文件来自12dict单词列表,使用"2 + 2lemma.txt"文件.对不起,如果代码有点混乱,这只是我一起攻击的东西.此外,我忘了从单词列表中删除逗号,这样实际上是一个错误,你可以为了相同的比较而留下它,或者通过在cleanentries中的chars列表中添加一个逗号来修复它.

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模块.

Answer 1

如果你的单词列表很长,从'word'生成所有可能的1个字母差异可能更有效率,那么检查列表中的哪些？我不知道任何Python,但应该有一个合适的wordlist数据结构,允许进行日志时间查找.

我建议这样做,因为如果你的单词是合理的长度(~10个字母),那么你只会寻找250个潜在单词,如果你的单词列表大于几百个单词,这可能会更快.

Answer 2

distance当你真正关心距离= 1时,你的功能是计算总距离.大多数情况下你会知道它在几个字符内> 1,所以你可以提前返回并节省大量时间.

除此之外,可能有更好的算法,但我想不到它.

编辑:另一个想法.

您可以根据第一个字符是否匹配来制作2个案例.如果不匹配,则单词的其余部分必须完全匹配,您可以一次性测试.否则,与你正在做的事情类似.你甚至可以递归地做,但我认为这不会更快.

def DifferentByOne(word1, word2):
    if word1[0] != word2[0]:
        return word1[1:] == word2[1:]
    same = True
    for i in range(1, len(word1)):
        if word1[i] != word2[i]:
            if same:
                same = False
            else:
                return False
    return not same

编辑2:我已经删除了检查以查看字符串是否长度相同,因为你说它是多余的.在我自己的代码和MizardX 提供的is_neighbors函数上运行Ryan的测试,我得到以下结果:

• 原始距离():3.7秒
• 我的DifferentByOne():1.1秒
• MizardX的is_neighbors():3.7秒

编辑3 :(可能在这里进入社区维基领域,但......)

使用izip而不是zip来尝试最终定义is_neighbors():2.9秒.

这是我的最新版本,仍然是1.1秒:

def DifferentByOne(word1, word2):
    if word1[0] != word2[0]:
        return word1[1:] == word2[1:]
    different = False
    for i in range(1, len(word1)):
        if word1[i] != word2[i]:
            if different:
                return False
            different = True
    return different

Answer 3

from itertools import izip

def is_neighbors(word1,word2):
    different = False
    for c1,c2 in izip(word1,word2):
        if c1 != c2:
            if different:
                return False
            different = True
    return different

或者可能是izip代码内容:

def is_neighbors(word1,word2):
    different = False
    next1 = iter(word1).next
    next2 = iter(word2).next
    try:
        while 1:
            if next1() != next2():
                if different:
                    return False
                different = True
    except StopIteration:
        pass
    return different

并重写getchildren:

def iterchildren(word, wordlist):
    return ( w for w in wordlist if is_neighbors(word, w) )

• izip(a,b)从a和中返回一对迭代器b.
• zip(a,b)返回a和的对列表b.