为什么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有什么问题？

- user2261062

---

这确实很有趣。您可以稍微修改第一种方法，不计算最后一个（“T”），因为它们应该是序列长度减去“A”、“C”和“G”的数量。我也要运行它。 - Ma0

测试1：{方法1：0.24，方法2：19.73，方法3：4.63} 测试2：{方法1：0.26，方法2：19.35，方法3：4.30}。至少counter比方法2更快，而方法2是，无意冒犯，糟糕的代码。 - Ma0

没什么奇怪的。方法1使用的是C代码，甚至非常简单的C代码。而且你只需要做四次。难怪它快得多。 - Stefan Pochmann

关于你最后的问题，想象一下有100个核苷酸而不是4个。要编写method1，您需要将“sequence”转换为“set”，并运行循环以处理集合的元素。这可能会变得越来越低效。 - Ma0

Answer 1

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

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

这意味着str.count可以在迭代过程中处理底层的C-char数组，同时它可以避免在迭代过程中创建新的（或查找现有的）长度为1的Python字符串（这是for和Counter所做的事情）。

---

仅为此声明增加一些背景。

一个字符串被存储为C数组并包装成Python对象。 str.count知道该字符串是一个连续的数组，因此将要计数的字符转换为C-"字符"，然后在本地C代码中迭代数组并检查相等性，最后包装并返回找到的出现次数。

另一方面，for和Counter使用Python迭代协议。您字符串的每个字符都将被包装为Python对象，然后它们（哈希和）在Python内部进行比较。

所以减速是因为：

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

---

请注意，减速的原因类似于为什么Python的数组很慢？这个问题。

---

我进行了一些额外的基准测试，以找出在哪个点上应该优先使用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），因此速度较慢。即使有100个不同的字符，str.count的速度仍然比Counter快6倍，因此无法准确估计str.count和Counter的分界点。

- MSeifert

---

虽然对于用户制作的循环，这是可以理解的，但人们仍然会想知道为什么Counter也不使用C代码。这似乎有些愚蠢。 - JulienD

Counter 在 Python 3.6 中确实使用了 C 代码，这使得它的性能比 for 循环要好，但仍然不如 str.count。 - Grisha

请尝试使用Python 2和Python 3。在Python 3中，Counter已经被重写为C语言。 - dawg

@dawg 不错。我忘了提到这些时间是使用python-3.x完成的。现在我已经包含了python-2.x的时间。 - MSeifert

Answer 2

这里的时间差异很容易解释。它归结于Python内部运行和本地代码的区别。后者始终更快，因为它不需要大量的评估开销。现在，这已经是调用str.count()四次比其他任何方法都要快的原因了。尽管这个字符串迭代了四次，但是这些循环在本地代码中运行。str.count是用C实现的，因此开销非常小，非常快。这真的很难超越这一点，特别是当任务是如此简单（仅查找简单的字符相等）时。您的第二种方法是收集数组中的计数，实际上是以下版本的性能较差的版本：

def method4 (seq):
    a, c, g, t = 0, 0, 0, 0
    for i in seq:
        if i == 'A':
            a += 1
        elif i == 'C':
            c += 1
        elif i == 'G':
            g += 1
        else:
            t += 1
    return [a, c, g, t]

这里，所有四个值都是单独的变量，因此更新它们非常快。实际上，这比突变列表项要快一点。

然而，总体性能“问题”在于这在 Python 中迭代字符串。因此，这会创建一个字符串迭代器，然后将每个字符作为实际字符串对象单独生成。这是很多开销的主要原因，也是为什么所有通过在 Python 中迭代字符串的解决方案都会更慢的主要原因。

collection.Counter 也有同样的问题。它是 用 Python 实现 的，因此即使它非常高效和灵活，但由于相同的问题，它永远不会接近本地速度。

- poke

Answer 3

正如其他人已经指出的那样，您正在将相当具体的代码与相当通用的代码进行比较。

请考虑，即使是将您感兴趣的字符循环拼写出来这样微不足道的事情也已经让您获得了2倍的效果。

def char_counter(text, chars='ACGT'):
    return [text.count(char) for char in chars]


%timeit method1(short_seq)
# 100000 loops, best of 3: 18.8 µs per loop
%timeit char_counter(short_seq)
# 10000 loops, best of 3: 40.8 µs per loop

%timeit method1(long_seq)
# 10 loops, best of 3: 172 ms per loop
%timeit char_counter(long_seq)
# 1 loop, best of 3: 374 ms per loop

---

你的method1()是最快的，但不是最高效的，因为每个字符都会被循环检查，没有利用到可以在一个字符被分配到其中一个字符类别时轻松跳过循环的事实。

不幸的是，Python没有提供一种快速的方法来利用你问题的具体条件。但是，你可以使用Cython来解决这个问题，这样你就能够超越你的method1()。

%%cython -c-O3 -c-march=native -a
#cython: language_level=3, boundscheck=False, wraparound=False, initializedcheck=False, cdivision=True, infer_types=True

import numpy as np


cdef void _count_acgt(
        const unsigned char[::1] text,
        unsigned long len_text,
        unsigned long[::1] counts):
    for i in range(len_text):
        if text[i] == b'A':
            counts[0] += 1
        elif text[i] == b'C':
            counts[1] += 1
        elif text[i] == b'G':
            counts[2] += 1
        else:
            counts[3] += 1


cpdef ascii_count_acgt(text):
    counts = np.zeros(4, dtype=np.uint64)
    bin_text = text.encode()
    return _count_acgt(bin_text, len(bin_text), counts)

%timeit ascii_count_acgt(short_seq)
# 100000 loops, best of 3: 12.6 µs per loop
%timeit ascii_count_acgt(long_seq)
# 10 loops, best of 3: 140 ms per loop

- norok2