なぜCollections.counterが遅いのですか？

Question

私は与えられた配列のヌクレオチドを数え、結果をリストに返すという、Rosalindの基本的な問題を解決しようとしています。バイオインフォマティクスに精通していない人にとっては、文字列内の4つの異なる文字（ 'A'、 'C​​'、 'G'、 'T'）の出現回数を数えるだけです。

私はcollections.Counterが最も高速な方法であると予想していました（最初は高性能であると主張していたため、2番目はこの特定の問題で使用していました）。

しかし、私の驚きにはこの方法は最も遅いです！短い配列に多くの時間を実行している長いシーケンスを数回

を実行

• ：
  私はtimeitを使用し、2つの実験の種類を実行している、3つの異なる方法を比較しました。ここで

が私のコードです：

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が遅いので

Answer 1

そうではありません、それは実際には非常に高速だが、それは汎用のツールですが、文字をカウントすることはただ一つ、多くのアプリケーションのです。一方

str.countはただの文字列内の文字をカウントし、それが唯一のタスクだために多額のは、最適化されました。それは新しい（または既存の見上げ）（何をすべきかforとCounterである）の繰り返しの間の長さ-1-のpython-文字列の作成を避けることができますがstr.countが基本となるC- charアレイ上で動作することができることを意味し

。

---

この文にもう少しコンテキストを追加してください。

文字列は、PythonオブジェクトとしてラップされたC配列として格納されます。str.countは、文字列が連続した配列であることを認識しているため、coにする文字をC-文字に変換した後、ネイティブCコードで配列を反復処理し、等価性をチェックして最終的に折り返し、 。

一方、forとCounterは、python-iteration-protocolを使用します。あなたの文字列の各文字は、python-objectとしてラップされ、次に（ハッシュと）それらをPython内で比較します。

ので、だから、減速は次のとおりです。各文字は、ループはには適用されません（Pythonで行われ

（これはパフォーマンスの低下の主な理由である）Pythonオブジェクトに変換する必要があり

• Pythonの3.xではCounterそれはCで書き直されたため）
• 各比較ではなく、単にCの数値を比較する（Pythonで行われなければならない - 文字が数字で表されている）
• カウンタ値をハッシュする必要があるとあなたのループは私に必要ですあなたのリストをndexしてください。

---

注低迷の理由は、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の場合は非常によく似ているので、明示的にリストしませんでした。

だからあなたはそれがstr.countのように一度だけではなく複数回の文字列を横断するので、同等Counterが速くなる80種類の文字を/カウントしたい場合。これは文字列の長さに弱く依存します（しかし、テストでは非常に弱い差+/- 2％しか示されませんでした）。パイソン-2.7 collections.CounterでのPython 2.7

ため

結果は、（代わりにCの）Pythonとはるかに遅いを用いて実施されました。 str.countとCounterの損益分岐点は、100種類の異なる文字であっても、str.countがまだ6倍速いため、外挿によってのみ見積もることができます。

Answer 2

ここの時差は説明するのがかなり簡単です。それはすべてPython内で実行されるものと、ネイティブコードとして実行されるものに分かれています。後者は、評価オーバーヘッドが多くないので、常に高速になります。

これで、str.count()を4回呼び出すことが他のどの方法よりも速いのは、すでにこれが理由です。これは文字列を4回繰り返しますが、これらのループはネイティブコードで実行されます。 str.countはC言語で実装されているため、オーバーヘッドはほとんどなく、非常に高速です。これを打つのは本当に困難です。特にタスクがシンプルなもの（単純な文字の平等のみを探している）の場合は特にそうです。

配列でカウントを収集するあなたの第2の方法は、実際には次の少ないパフォーマンスバージョンである：ここで

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] 

、すべての4つの値が個々の変数なので、それらを更新することは非常に高速です。実際には、リスト項目を変更するよりも少し速いです。

ここでパフォーマンス全体の「問題」は、という文字列をPython内で繰り返し実行することです。このため、文字列イテレータが作成され、実際の文字列オブジェクトとしてすべての文字が個別に生成されます。これは多くのオーバーヘッドであり、の文字列をPythonで繰り返し処理するすべてのソリューションが遅くなる主な理由です。

同じ問題はcollection.Counterです。それはimplemented in Pythonなので、非常に効率的で柔軟性はありますが、スピードの面で決してネイティブに近いことはないという同じ問題を抱えています。