为什么Collections.counter这么慢？

我正在尝试解决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什么？

MSeifert.. 15

这不是因为collections.Counter速度慢,实际上非常快,但它是一种通用工具,计算字符只是众多应用程序中的一种.

另一方面,str.count只计算字符串中的字符,并对其进行大量优化,因为它是唯一的任务.

这意味着str.count可以在底层C char阵列上工作,同时它可以避免在迭代期间创建新的(或查找现有的)length-1-python-strings(这是什么for和Counter做什么).

---

只是为此声明添加更多上下文.

字符串存储为包含python对象的C数组.该str.count知道的字符串是一个连续的数组,因此转换要合到C-"角色",然后在本地C代码和平等检查阵列上迭代的字符,最后包装并返回找到出现次数的数量.

另一方面for,Counter使用python-iteration-protocol.你的字符串的每个字符都将被包装为python-object,然后它(散列和)在python中对它们进行比较.

所以减速是因为:

每个字符都必须转换为Python对象(这是性能损失的主要原因)

循环在Python中完成(不适用于Counterpython 3.x,因为它在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)实现并且慢得多.对于盈亏平衡点str.count,并Counter只能通过外推法来估计,因为即使有100级不同的人物str.count仍然是快6倍.

1> MSeifert..：

---

这不是因为collections.Counter速度慢,实际上非常快,但它是一种通用工具,计算字符只是众多应用程序中的一种.

另一方面,str.count只计算字符串中的字符,并对其进行大量优化,因为它是唯一的任务.

这意味着str.count可以在底层C char阵列上工作,同时它可以避免在迭代期间创建新的(或查找现有的)length-1-python-strings(这是什么for和Counter做什么).

---

只是为此声明添加更多上下文.

字符串存储为包含python对象的C数组.该str.count知道的字符串是一个连续的数组,因此转换要合到C-"角色",然后在本地C代码和平等检查阵列上迭代的字符,最后包装并返回找到出现次数的数量.

另一方面for,Counter使用python-iteration-protocol.你的字符串的每个字符都将被包装为python-object,然后它(散列和)在python中对它们进行比较.

所以减速是因为:

每个字符都必须转换为Python对象(这是性能损失的主要原因)

循环在Python中完成(不适用于Counterpython 3.x,因为它在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)实现并且慢得多.对于盈亏平衡点str.count,并Counter只能通过外推法来估计,因为即使有100级不同的人物str.count仍然是快6倍.

2> poke..：

---

这里的时差非常简单.这一切都归结为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实现的,所以即使它非常高效和灵活,它也会遇到同样的问题,它在速度方面从不接近本机.