首页 / 问题 / 正文

如何优化这段Python代码以生成所有字距为1的单词？

32 投票
12 回答
6562 浏览
提问于 2025-04-15 11:14

性能分析显示，我写的一个小单词游戏中，这段代码是最慢的部分：

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只差一个字母的单词。
  • wordlist已经预先过滤，只包含与word字母数相同的单词，所以word1和word2的字母数是一样的。
  • 我对Python还很陌生（刚学了3天），所以对命名规范或其他风格方面的建议也很欢迎。
  • wordlist使用的是12dict单词列表中的"2+2lemma.txt"文件。

结果：

谢谢大家，经过不同建议的组合，我让程序的运行速度提高了一倍（在我自己优化的基础上，所以比我最初的实现快了大约4倍）。

我用两组输入进行测试，称之为A和B。

优化1：遍历word1和word2的索引 ... 从

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：

除了distance方法外，我还增加了一个单独的方法来处理只差一个字母的情况（我在其他地方仍然需要使用distance方法来进行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"只差一个字母的所有字符串的列表，然后检查这些字符串是否在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"，并反向比较会不会有不同，这时我意识到我在寻找两个列表的交集。我用集合交集来处理字母替代：

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语言中会更快。我尝试了两个小时让自己写的C模块构建并链接，但没有成功，尽管我试着跟随这个和这个的例子，似乎在Windows中的过程有点不同？我不知道，但我放弃了。无论如何，这里是程序的完整代码，文本文件来自12dict单词列表中的"2+2lemma.txt"文件。抱歉代码有点乱，这只是我临时拼凑的。另外，我忘了从单词列表中去掉逗号，这实际上是一个bug，你可以选择保留这个bug以便进行相同的比较，或者通过在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方法调用的总时间。快速输入集是"verse poets"，而长输入集是"poets verse"。不同机器之间的时间会有所不同，所以如果有人尝试这个，请比较程序的结果，以及使用C模块的结果。

代码优化 字符串处理 性能分析 计算复杂度 优化 单词游戏 集合交集 A*搜索

12 个回答

6
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 中取出的成对值。
回答于 2025-04-15 由 Python大师
分享 举报
10

你的函数 distance 计算的是总距离，但其实你只关心距离是否等于1。在大多数情况下，你可以在检查几个字符后就知道距离是否大于1，这样可以提前返回，节省很多时间。

除此之外，可能还有更好的算法，但我一时想不出来。

补充： 还有一个想法。

你可以分成两种情况，看看第一个字符是否匹配。如果不匹配，那么剩下的单词必须完全匹配，你可以一次性检查这一点。否则，就像你之前做的那样处理。你甚至可以用递归的方法，但我觉得这样可能不会更快。

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 的测试，结果如下：

  • 原始的 distance()：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
回答于 2025-04-15 由 Python大师
分享 举报
24

如果你的单词列表很长，可能更有效的方法是先生成所有与“word”只有一个字母不同的单词，然后再检查这些单词是否在列表中。我对Python不太了解，但应该有一种合适的数据结构可以让你快速查找单词。

我这样建议是因为如果你的单词长度适中（大约10个字母），那么你只需要寻找250个可能的单词。如果你的单词列表超过几百个单词，这样的方法可能会更快。

回答于 2025-04-15 由 Python大师
分享 举报

撰写回答