在Python中解释汉明距离速度

Question

我一直在努力让我的Python更具Pythonic风格，并尝试运行短代码片段的运行时间。我的目标是提高可读性，但同时也加快执行速度。

这个例子与我阅读过的最佳实践相冲突，我很想找到我的思维过程中的缺陷所在。

问题是计算两个等长字符串之间的汉明距离。例如，字符串'aaab'和'aaaa'的汉明距离为1。

我能想到的最直接的实现方法如下：

def hamming_distance_1(s_1, s_2):
    dist = 0
    for x in range(len(s_1)):
        if s_1[x] != s_2[x]:  dist += 1
    return dist

接下来我编写了两个“Pythonic”的实现：

def hamming_distance_2(s_1, s_2): 
    return sum(i.imap(operator.countOf, s_1, s_2))

并且

def hamming_distance_3(s_1, s_2): 
    return sum(i.imap(lambda s: int(s[0]!=s[1]), i.izip(s_1, s_2)))  

在执行中：

s_1 = (''.join(random.choice('ABCDEFG') for i in range(10000)))
s_2 = (''.join(random.choice('ABCDEFG') for i in range(10000)))
print 'ham_1  ',  timeit.timeit('hamming_distance_1(s_1, s_2)',  "from __main__ import s_1,s_2, hamming_distance_1",number=1000)
print 'ham_2  ',  timeit.timeit('hamming_distance_2(s_1, s_2)',  "from __main__ import s_1,s_2, hamming_distance_2",number=1000)
print 'ham_3  ',  timeit.timeit('hamming_distance_3(s_1, s_2)',  "from __main__ import s_1,s_2, hamming_distance_3",number=1000)

返回：

ham_1   1.84980392456
ham_2   3.26420593262
ham_3   3.98718094826

我原本以为ham_3会比ham_2运行得慢，因为调用lambda被视为函数调用，比调用内置的operator.countOf要慢。

然而，我很惊讶地发现，我找不到一种更pythonic的方法来使ham_1运行得更快。我很难相信ham_1是纯Python的下限。

有什么想法吗？

- Scrocco

---

我认为只有您的第一种实现是“Pythonic”。 - YXD

最终，这是最快的解决方案，sum(i.imap(operator.ne, s_1, s_2)) 运行时间为 1.03。 - Scrocco

Answer 1

关键在于减少方法查找和函数调用：

def hamming_distance_4(s_1, s_2):
    return sum(i != j for i, j in i.izip(s_1, s_2))

在我的系统中，ham_4 1.10134792328 运行速度很快。 ham_2 和 ham_3 在循环内进行查找，因此它们较慢。

- utdemir

---

没错，就是这样。谢谢。与之相比，ham_4大约需要1.67991399765秒的运行时间。 - Scrocco

我对 ham_2 的缓慢感到困惑，经过更深入的挖掘，我意识到 operator.countOf 在字符串上运行一个 for 循环（每个字符串长度为 1），而编译器不会将其优化。使用 operator.ne 没有 for 循环，并且在您上面的示例中运行时间减少了一半。 - Scrocco

Answer 2

我想知道这是否在更广义的意义上更符合Pythonic。如果您使用 http://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.distance.hamming.html，一个已经实现了您所需内容的模块，会怎样呢？

- Jim Dennis

---

OP正在请求对字符串数组进行汉明距离计算，而不是整数。Scipy空间距离计算仅适用于整数。 - SummerEla