如何优化此 Python 代码以生成单词距离为 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，它应该获取所有内容单词列表中与 word 恰好有 1 个字母不同的单词。
• wordlist 经过预过滤，只包含与 word 包含相同数量字母的单词，因此保证 word1 和 word2 具有相同数量的单词字符。
• 我对 Python 相当陌生（三天前开始学习），所以对命名约定或其他风格事物的评论也很感激。
• 对于单词列表，请使用“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

我可能可以做得更好一种较低级别的语言，但我现在对此感到满意。 感谢大家！

再次编辑：更多结果 使用马克的方法检查第一个字母不匹配的情况，从 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”并执行以下操作是否会有任何区别当我意识到我正在寻找两个列表的交集时，以另一种方式进行比较。 我将其替换为字母上的交集：

return set(oneoff) & set(wordlist)

Bam！ 3.74-> 0.23和34.40→ 2.25

这确实是令人惊奇的，与我最初的天真的实现的总速度差异： 23.79 -> 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 模块的结果比较。

Answer 1

如果您的单词列表很长，那么从“单词”生成所有可能的 1 字母差异，然后检查列表中的哪些单词是否会更有效？ 我不懂Python，但应该有一个适合单词列表​​的数据结构，允许日志时间查找。

我建议这样做是因为，如果您的单词长度合理（~10 个字母），那么您只需寻找 250 个潜在单词，如果您的单词列表大于几百个单词，这可能会更快。

Answer 2

你的函数 distance 正在计算总距离，而你实际上只关心 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：我删除了检查字符串是否相同长度的检查，因为你说它是多余的。 在我自己的代码和is_neighbors 函数 由 MizardX 提供，我得到以下内容：

• 原始距离（）：3.7秒
• 我的DifferentByOne（）：1.1秒
• MizardX的is_neighbors（）：3.7秒

编辑3：（可能在这里进入社区维基领域，但是......）

尝试你的最终定义is_neighbors() 与 izip 而不是 zip：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 的对。

Answer 4

人们主要通过尝试编写更快的函数来解决这个问题，但可能还有另一种方法。

“距离”被调用超过 500 万次

这是为什么？ 也许更好的优化方法是尝试减少对 distance 的调用次数，而不是减少 distance 执行时间的毫秒数。 如果不看完整的脚本就无法判断，但优化特定功能通常是不必要的。

如果这是不可能的，也许你可以把它写成一个 C 模块？

Answer 5

使用相同参数调用距离函数的频率是多少？ 实现优化的一个简单方法是使用记忆。

您可能还可以创建某种字典，其中包含冻结的字母集和互不相同的单词列表，并在其中查找值。 该数据结构可以通过 pickle 存储和加载，也可以在启动时从头开始生成。

仅当您使用的单词非常长时，短路评估才会给您带来收益，因为您使用的汉明距离算法基本上是 O(n)，其中 n 是单词长度。

我用 timeit 做了一些实验，寻找一些可能具有说明性的替代方法。

Timeit 结果

您的解决方案

d = """\
def distance(word1, word2):
    difference = 0
    for i in range(len(word1)):
        if word1[i] != word2[i]:
            difference += 1
    return difference
"""
t1 = timeit.Timer('distance("hello", "belko")', d)
print t1.timeit() # prints 6.502113536776391

One Liner

d = """\
from itertools import izip
def hamdist(s1, s2):
    return sum(ch1 != ch2 for ch1, ch2 in izip(s1,s2))
"""
t2 = timeit.Timer('hamdist("hello", "belko")', d)
print t2.timeit() # prints 10.985101179

Shortcut 评估

d = """\
def distance_is_one(word1, word2):
    diff = 0
    for i in xrange(len(word1)):
        if word1[i] != word2[i]:
            diff += 1
        if diff > 1:
            return False
    return diff == 1
"""
t3 = timeit.Timer('hamdist("hello", "belko")', d)
print t2.timeit() # prints 6.63337

Answer 6

如果差值是 2 或更多，你可以先让循环中断。

您也可以更改

for i in range(len(word1)):

为

for i in xrange(len(word1)):

因为 xrange 按需生成序列，而不是一次生成整个数字范围。

您也可以尝试比较字长，这样会更快。 另请注意，如果 word1 大于 word2，您的代码将无法工作。

此后您在算法上无法做太多其他事情，也就是说，通过将该部分移植到 C，您可能会发现更多的加速。

编辑2

尝试解释我对 Sumudu 算法与逐个字符验证差异的分析。

当你有一个长度为 L 的单词时，你将生成的“相差一”单词的数量将为 25L。 从现代计算机上集合的实现中我们知道，搜索速度大约为 log(n) base 2，其中 n 是要搜索的元素数量。

看到你测试的 500 万个单词中的大多数都不在集合中，大多数时候，你将遍历整个集合，这意味着它真的变成了 log(25L) 而不是仅 log(25L)/2。 （这是假设集合的最佳情况，逐个字符串比较相当于逐个字符比较）

现在我们看一下确定“逐个差异”的时间复杂度。 如果我们假设你必须检查整个单词，那么每个单词的操作次数就变成L。 我们知道大多数单词很快就会相差 2。 并且知道大多数前缀占据单词的一小部分，我们可以逻辑地假设您大部分时间都会中断 L/2，即单词的一半（这是一个保守的估计） 。

因此，现在我们绘制两个搜索的时间复杂度，L/2 和 log(25L)，并记住这甚至考虑了字符串匹配与字符匹配相同的速度（高度支持套）。 你有方程 log(25*L) > L/2，可以简化为log(25)> L/2 - log(L)。 从图中可以看出，使用字符匹配算法应该会更快，直到达到非常大量的 L。

此外，我不知道您是否在优化中计算出 2 或更多差异的中断，但从 Mark 的回答来看，我已经在 2 或更多差异上中断，实际上，如果第一个差异字母，它在第一个字母后就中断了，即使进行了所有这些优化，更改为使用集合也只会让它们出局。 不过我有兴趣尝试你的想法

我是这个问题中第一个建议打破 2 或更多差异的人。 问题是，Mark 的字符串切片思想 (if word1[0] != word2[0]: return word1[1:] == word2[1:]) 只是将我们正在做的事情放入 C 中。你认为 word1[1:] == word2[1:] 是计算出来的吗？ 我们正在做同样的事情。

我读了几次你的解释，但我不太明白，你介意解释得更深入一点吗？ 另外，我对 C 也不是很熟悉，过去几年我一直在使用高级语言（最接近的是 6 年前在高中学习 C++

至于生成 C 代码，我有点忙。我相信您能够做到这一点，因为您以前用 C 编写过，您也可以尝试 C#，它可能具有类似的性能特征

更多说明

的更深入的解释。

def getchildren(word, wordlist):
    oneoff = one_letter_off_strings(word)
    return set(oneoff) & set(wordlist)

这是对 Davy8 Your one_letter_off_strings 函数将创建一组 25L 字符串（其中 L 是字母数）。

从单词列表创建一组将创建一组 D 字符串（其中 D 是字典的长度）。 必须遍历每个oneoff并查看它是否存在于单词列表中。

此操作的时间复杂度如上所述。此操作的效率较低。将你想要的单词与单词列表中的每个单词进行比较，Sumudu的方法是C语言而不是算法的优化。

更多说明2

总共只有 4500 个单词（因为单词列表在传递给算法之前已预先过滤了 5 个字母的单词），与 125 个单字母单词相交。 您似乎是在说交集是 log(smaller) 或换句话说 log(125, 2)。 再次假设你所说的，比较一个单词在 L/2 个字母中的断裂，我会将其四舍五入为 2，即使对于 5 个字母的单词，它更有可能是 3。这种比较进行了 4500 次，所以 9000。log(125,2) 约为 6.9，log(4500,2) 约为 12。请告诉我我是否误解了您的数字。

要创建 125 个单字母单词与 4500 个字典的交集，您需要进行 125 * 4500 次比较。 这不是 log(125,2)。 假设字典已预先排序，则最多为 125 * log(4500, 2)。 集合没有神奇的捷径。您在这里还进行了字符串与字符串的比较，而不是字符与字符的比较。

Answer 7

对于这样一个具有如此大性能影响的简单函数，我可能会创建一个 C 库并使用 ctypes。 Reddit 的一位创始人声称，他们使用这种技术使网站速度提高了 2 倍。

您还可以在此函数上使用psyco，但要注意它会占用大量内存。

Answer 8

我不知道它是否会显着影响您的速度，但您可以从将列表理解转换为生成器表达式开始。 它仍然是可迭代的，所以在用法上应该没有太大不同：

def getchildren(word, wordlist):
    return [ w for w in wordlist if distance(word, w) == 1 ]

to

def getchildren(word, wordlist):
    return ( w for w in wordlist if distance(word, w) == 1 )

主要问题是列表理解会在内存中构建自身并占用相当多的空间，而生成器将动态创建列表，因此无需存储整个内容。

另外，根据未知的答案，这可能是一种更“Pythonic”的编写 distance() 的方式：

def distance(word1, word2):
    difference = 0
    for x,y in zip (word1, word2):
        if x == y:
            difference += 1
    return difference

但是当 len (word1) != len (word2) 时，它的意图令人困惑，在 zip 的情况下，它只会返回尽可能多的值字符作为最短的单词。 （这可能是一种优化......）

Answer 9

试试这个：

def distance(word1, word2):
  return sum([not c1 == c2 for c1, c2 in zip(word1,word2)])

另外，你有你的游戏的链接吗？ 我喜欢被文字游戏摧毁

Answer 10

我首先想到的是：

from operator import ne

def distance(word1, word2):
    return sum(map(ne, word1, word2))

它很有可能比人们发布的其他函数运行得更快，因为它没有解释循环，只是调用 Python 原语。 而且它足够短，您可以合理地将其内联到调用者中。

对于您的更高级别的问题，我将研究为度量空间中的相似性搜索而开发的数据结构，例如 这篇论文或这本书，我都没有读过（它们是在搜索我读过但不记得的论文时出现的）。

Answer 11

对于这个片段：

for x,y in zip (word1, word2):
    if x != y:
        difference += 1
return difference

我会使用这个：

return sum(1 for i in xrange(len(word1)) if word1[i] == word2[i])

相同的模式将遵循所提供的代码......

Answer 12

其他人都只专注于显式距离计算，而没有做任何关于构建距离 1 候选的事情。
您可以通过使用名为 Trie 将隐式距离计算与生成所有距离1邻居词的任务合并。 Trie 是一个链表，其中每个节点代表一个字母，“下一个”字段是一个最多包含 26 个条目的字典，指向下一个节点。

这是伪代码：针对给定的单词迭代遍历 Trie； 在每个节点将所有距离 0 和距离 1 的邻居添加到结果中； 保持距离计数器并减少它。 您不需要递归，只需要一个需要额外的 distance_so_far 整数参数的查找函数。

可以通过为长度 3、长度 4、长度 5 等单词构建单独的尝试来获得 O(N) 空间增加的额外速度的较小权衡。