python - 为什么 Collections.counter 这么慢？

Question

我正在尝试解决 Rosalind 的基本问题，即计算给定序列中的核苷酸，并在列表中返回结果。对于那些不熟悉生物信息学的人来说，它只是计算字符串中 4 个不同字符('A'、'C'、'G'、'T')出现的次数。

我希望 collections.Counter 是最快的方法(首先是因为他们声称是高性能的，其次是因为我看到很多人使用它来解决这个特定问题)。

但令我惊讶的是这种方法是最慢的!

我比较了三种不同的方法，使用 timeit 并运行两种类型的实验:

• 多次运行一个长序列
• 多次运行一个短序列。

这是我的代码:

import timeit
from collections import Counter

# Method1: using count
def method1(seq):
    return [seq.count('A'), seq.count('C'), seq.count('G'), seq.count('T')]

# method 2: using a loop
def method2(seq):
    r = [0, 0, 0, 0]
    for i in seq:
        if i == 'A':
            r[0] += 1
        elif i == 'C':
            r[1] += 1
        elif i == 'G':
            r[2] += 1
        else:
            r[3] += 1
    return r

# method 3: using Collections.counter
def method3(seq):
    counter = Counter(seq)
    return [counter['A'], counter['C'], counter['G'], counter['T']]


if __name__ == '__main__':

    # Long dummy sequence
    long_seq = 'ACAGCATGCA' * 10000000
    # Short dummy sequence
    short_seq = 'ACAGCATGCA' * 1000

    # Test 1: Running a long sequence once
    print timeit.timeit("method1(long_seq)", setup='from __main__ import method1, long_seq', number=1)
    print timeit.timeit("method2(long_seq)", setup='from __main__ import method2, long_seq', number=1)
    print timeit.timeit("method3(long_seq)", setup='from __main__ import method3, long_seq', number=1)

    # Test2: Running a short sequence lots of times
    print timeit.timeit("method1(short_seq)", setup='from __main__ import method1, short_seq', number=10000)
    print timeit.timeit("method2(short_seq)", setup='from __main__ import method2, short_seq', number=10000)
    print timeit.timeit("method3(short_seq)", setup='from __main__ import method3, short_seq', number=10000)

结果:

Test1: 
Method1: 0.224009990692
Method2: 13.7929501534
Method3: 18.9483819008

Test2:
Method1: 0.224207878113
Method2: 13.8520510197
Method3: 18.9861831665

对于两个实验，方法 1 比方法 2 和 3 快!!

所以我有一组问题:

• 我是不是做错了什么，或者它确实比其他两种方法慢？有人可以运行相同的代码并分享结果吗？

• 如果我的结果是正确的，(也许这应该是另一个问题)是否有比使用方法 1 更快的方法来解决这个问题？

• 如果 count 更快，那么 collections.Counter 有什么用？

Answer 1

这不是因为 collections.Counter 慢，它实际上很快，但它是一个通用工具，计算字符只是众多应用中的一个。

另一方面，str.count 只对字符串中的字符进行计数，并且高度针对它的唯一任务进行了优化。

这意味着 str.count 可以在底层 C-char 数组上工作，同时它可以避免创建新的(或查找现有的)length-1-python-迭代期间的字符串(这是 for 和 Counter 所做的)。

---

只是为这个声明添加更多上下文。

字符串存储为 C 数组，包装为 python 对象。 str.count 知道该字符串是一个连续的数组，因此将您想要 co 的字符转换为 C-“字符”，然后在 native C 代码中遍历该数组并检查相等性和最后包装并返回找到的次数。

另一方面，for 和 Counter 使用 python 迭代协议(protocol)。字符串的每个字符都将包装为 python 对象，然后在 python 中(散列和)比较它们。

所以减速是因为:

• 每个字符都必须转换为Python对象(这是性能损失的主要原因)
• 循环是用Python完成的(不适用于python 3.x中的Counter，因为它是用C重写的)
• 每个比较都必须在 Python 中完成(而不是仅仅比较 C 中的数字——字符由数字表示)
• 计数器需要对值进行哈希处理，而您的循环需要为您的列表编制索引。

---

注意减速的原因与关于 Why are Python's arrays slow? 的问题类似.

---

我做了一些额外的基准测试，以找出在什么时候 collections.Counter 优于 str.count。为此，我创建了包含不同数量的唯一字符的随机字符串并绘制了性能图:

from collections import Counter
import random
import string

characters = string.printable  # 100 different printable characters

results_counter = []
results_count = []
nchars = []

for i in range(1, 110, 10):
    chars = characters[:i]
    string = ''.join(random.choice(chars) for _ in range(10000))
    res1 = %timeit -o Counter(string)
    res2 = %timeit -o {char: string.count(char) for char in chars}
    nchars.append(len(chars))
    results_counter.append(res1)
    results_count.append(res2)

结果是使用 matplotlib 绘制的:

import matplotlib.pyplot as plt

plt.figure()

plt.plot(nchars, [i.best * 1000 for i in results_counter], label="Counter",   c='black')
plt.plot(nchars, [i.best * 1000 for i in results_count],   label="str.count", c='red')
plt.xlabel('number of different characters')
plt.ylabel('time to count the chars in a string of length 10000 [ms]')
plt.legend()

Python 3.5 的结果

Python 3.6 的结果非常相似，所以我没有明确列出它们。

所以如果你想计算 80 个不同的字符，Counter 变得更快/可比较，因为它只遍历字符串一次，而不是像 str.count 那样遍历多次。这将弱依赖于字符串的长度(但测试显示只有非常微弱的差异 +/-2%)。

Python 2.7 的结果

在 Python-2.7 中，collections.Counter 是使用 python(而不是 C)实现的，速度要慢得多。 str.count 和 Counter 的盈亏平衡点只能通过外推来估计，因为即使有 100 个不同的字符，str.count 仍然是快 6 倍。