4

我一直在努力让我的 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 慢。

我很惊讶我找不到一种方法来获得一个比 ham_1 运行得更快的 Pythonic 版本。我很难相信 ham_1 是纯 python 的下限。

有人想吗?

4

2 回答 2

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进行查找,因此它们较慢。

于 2015-02-04T19:41:08.930 回答
-1

我想知道从某种更广泛的意义上说,这是否更像 Pythonic。如果您使用http://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.distance.hamming.html ... 一个已经实现您正在寻找的模块怎么办?

于 2015-02-04T19:45:38.057 回答