为什么 Collections.counter 这么慢？
Why is Collections.counter so slow?
我正在尝试解决计算给定序列中核苷酸的 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有什么用？
并不是因为 collections.Counter 慢，它实际上很快，但它是一个通用工具，计算字符只是众多应用中的一个。
另一方面，str.count 仅对字符串中的字符进行计数，并且针对其唯一任务进行了 优化。
这意味着 str.count 可以在底层 C-char 数组上工作，同时它可以避免创建新的（或查找现有的）length-1-python-strings迭代（这是 for 和 Counter 所做的）。
只是为了给这个声明添加更多的上下文。
字符串存储为 C 数组，包装为 python 对象。 str.count 知道该字符串是一个连续数组，因此将您要 co 的字符转换为 C-"character"，然后在本机 C 代码中遍历该数组并检查是否相等，最后换行和returns 找到的次数。
另一方面，for 和 Counter 使用 python-iteration-protocol。字符串的每个字符都将包装为 python-object，然后它（散列和）在 python.
中比较它们
所以减速是因为：
- 每个字符都必须转换为一个Python对象（这是性能损失的主要原因）
- 循环在Python中完成（不适用于python3.x中的
Counter，因为它是用C重写的）
- 每个比较都必须在 Python 中完成（而不是仅仅比较 C 中的数字 - 字符由数字表示）
- 计数器需要对值进行哈希处理，您的循环需要为您的列表编制索引。
注意减速的原因与关于 的问题类似。
我做了一些额外的基准测试来找出 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 会变成 faster/comparable，因为它只遍历字符串一次，而不是像 str.count 那样遍历多次。这将弱依赖于字符串的长度（但测试显示只有非常微弱的差异 +/-2%）。
Python 2.7
的结果
在 Python-2.7 中，collections.Counter 是使用 python（而不是 C）实现的，速度要慢得多。 str.count 和 Counter 的盈亏平衡点只能通过外推来估计，因为即使有 100 个不同的字符，str.count 仍然快 6 倍。
这里的时差解释起来很简单。这一切都归结为 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 也有同样的问题。它是 implemented in Python，所以尽管它非常高效和灵活，但它也存在同样的问题，即它在速度方面永远无法接近原生。
正如其他人已经指出的，您正在比较相当具体的代码和相当一般的代码。
考虑一下，像在您感兴趣的字符上拼写出循环这样微不足道的事情已经为您买了一个因素 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
我正在尝试解决计算给定序列中核苷酸的 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有什么用？
并不是因为 collections.Counter 慢，它实际上很快，但它是一个通用工具，计算字符只是众多应用中的一个。
另一方面，str.count 仅对字符串中的字符进行计数，并且针对其唯一任务进行了 优化。
这意味着 str.count 可以在底层 C-char 数组上工作，同时它可以避免创建新的（或查找现有的）length-1-python-strings迭代（这是 for 和 Counter 所做的）。
只是为了给这个声明添加更多的上下文。
字符串存储为 C 数组，包装为 python 对象。 str.count 知道该字符串是一个连续数组，因此将您要 co 的字符转换为 C-"character"，然后在本机 C 代码中遍历该数组并检查是否相等，最后换行和returns 找到的次数。
另一方面，for 和 Counter 使用 python-iteration-protocol。字符串的每个字符都将包装为 python-object，然后它（散列和）在 python.
所以减速是因为：
- 每个字符都必须转换为一个Python对象（这是性能损失的主要原因）
- 循环在Python中完成（不适用于python3.x中的
Counter，因为它是用C重写的） - 每个比较都必须在 Python 中完成（而不是仅仅比较 C 中的数字 - 字符由数字表示）
- 计数器需要对值进行哈希处理，您的循环需要为您的列表编制索引。
注意减速的原因与关于
我做了一些额外的基准测试来找出 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 会变成 faster/comparable，因为它只遍历字符串一次，而不是像 str.count 那样遍历多次。这将弱依赖于字符串的长度（但测试显示只有非常微弱的差异 +/-2%）。
Python 2.7
的结果在 Python-2.7 中，collections.Counter 是使用 python（而不是 C）实现的，速度要慢得多。 str.count 和 Counter 的盈亏平衡点只能通过外推来估计，因为即使有 100 个不同的字符，str.count 仍然快 6 倍。
这里的时差解释起来很简单。这一切都归结为 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 也有同样的问题。它是 implemented in Python，所以尽管它非常高效和灵活，但它也存在同样的问题，即它在速度方面永远无法接近原生。
正如其他人已经指出的，您正在比较相当具体的代码和相当一般的代码。
考虑一下，像在您感兴趣的字符上拼写出循环这样微不足道的事情已经为您买了一个因素 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