Pythonでアイテムの個数を数えるのって結局どれが速いのよ

問題設定

与えられたイテレータ（リストなど）に対して、項目別の頻度（個数）を数えたいときがあります。
例えば

example

>>> print countitems(["a", "b", "a", "c", "a", "c"])
{"a": 3, "b": 1, "c": 2}

みたいなことがしたいのですが。

前提条件

（追記：2018/02/13）
今回は、入ってくる値に対して事前情報がないものとします。もし

• 値の集合があらかじめ決まっている
• 取り得る値の種類が少ない

ということが分かっている場合には、この記事でご紹介する方法よりも速くカウントできる場合があります。
例えば、A, C, G, Tの4種類の文字だけからなるlist, tupleや文字列が与えられると分かっていれば、4種類の文字に対してそれぞれ count() メソッド（list/tupleの場合、文字列の場合）でカウントする方が速いでしょう。
（@sharow様ありがとうございます）

（追記：2018/02/17）
何種類くらいまでだったら速くなりそうか調べてみました。
https://qiita.com/hira_physics/items/9dfdfa4dd2e7b49b7a92

というか普通にあるじゃん

実はcollections.Counter()というぴったりの機能があります。
ですが、遅いらしいです。
ただし「Python 2.7だと遅いけど、Python 3.xだとそんなことない」という話も出ています。
https://stackoverflow.com/questions/41594940/why-is-collections-counter-so-slow

こちらを見ると、defaultdictを使うとCounterより速いとのこと。
おそらくPython 2.7の話と思われます。
http://hateda.hatenadiary.jp/entry/2015/03/19/223638

比べてみよう

というわけで、ここではdefaultdictとCounterの2つに絞って、どちらかを使うのが良いか調べてみます。

測定環境

• Cygwin (Windows 10)
• Python 2.7.14 / 3.6.4
• CPU: Intel Core i7-7500U

コード

さっきのstackoverflowから一部拝借しました。
最後は普通のdictとして結果を返すように揃えています。あとはPython2と3の両方で動くように書いています。（要注意なのはprintのところくらいですが）

counter.py

import collections
import timeit

def count_counter(it):
    counter = collections.Counter(it)
    return dict(counter)

def count_defaultdict(it):
    counter = collections.defaultdict(int)
    for x in it:
        counter[x] += 1
    return dict(counter)

if __name__ == '__main__':
    seq = 'ACAGCATGCA' * 10000000
    print(timeit.timeit("count_counter(seq)", setup='from __main__ import count_counter, seq', number=1))
    print(timeit.timeit("count_defaultdict(seq)", setup='from __main__ import count_defaultdict, seq', number=1))

結果

上がCounterを使った場合、下がdefaultdictを使った場合の所要時間（秒）です。

terminal

$ python2.7 counter.py
27.1584978104
5.29513907433

$ python3.6 counter.py
4.555456822738051
7.105967835057527

確かに、Python 2.7だとdefaultdictの方が速くて、Python 3.6だとCounterの方が速いですね。
2でも3でもdefaultdict使っておけば大きく間違わないとは思いますが、同じ標準モジュールでやるんだったら、なるべく速い方法がいいですよね。

古いPython 3だとどうなる？

Python 3のドキュメントを見ると、Counterは3.1から使えることになっていますが、3.1の時点で既にdefaultdictよりCounterの方が速いんでしょうか？

というわけでPython3の各マイナーバージョンをビルドして検証してみました。
なおCygwinでソースコードからビルドするのはちょっと骨が折れる（いろいろ修正しないとコンパイルが通らない）ので、ここから先はおとなしくLinuxの環境で試してみます。そのため、今までの処理時間とは比較できませんのでご注意を。

• CentOS 7.4
• Python 3.1.5 / 3.2.6 / 3.3.7
• CPU: Intel Celeron 847

terminal

$ Python-3.1.5/python counter.py
81.1171450615
29.1302690506

$ Python-3.2.6/python counter.py
81.19674897193909
23.85732889175415

$ Python-3.3.7/python counter.py
13.443840522319078
23.899318914860487

ご覧の通り、Python 3.1, 3.2のCounterは2.7と同様に遅いです。Python 3.3で逆転しました。defaultdictの時間はどのバージョンでも大きく変わりませんが、3.1はやや遅い感じですかね。（2回測定してみましたが2回とも30秒前後掛かっていました）

いいとこ取りしてみよう

Python 2と3の両方で実行される可能性があるプログラムを書くなら、いいとこ取りしましょう。
Python 3.3以降の場合はCounterベース、2系か3.2以前の場合はdefaultdictベースにしておけば良いと思われるので、こんな感じで書いてみました。

counter.py

import sys
import collections
import timeit

def countitems(it):
    if sys.version_info >= (3, 3):
        counter = collections.Counter(it)
    else:
        counter = collections.defaultdict(int)
        for x in it:
            counter[x] += 1
    return dict(counter)

if __name__ == '__main__':
    seq = 'ACAGCATGCA' * 10000000
    print(timeit.timeit("countitems(seq)", setup='from __main__ import countitems, seq', number=1))

実行結果はこちら。Python 2.7はyumからインストールした標準のPython、それ以外は自分でビルドしたものです。

terminal

$ python2.7 counter.py
23.7536501884

$ Python-3.1.5/python counter.py
30.1335320473

$ Python-3.2.6/python counter.py
24.026453971862793

$ Python-3.3.7/python counter.py
14.286271762102842

Pythonのバージョンに応じて速い方が選ばれているようです。

おまけ

カウント処理をCで書けば、きっと爆速になるはず。
今度は再びCygwin + Core i7-7500Uの環境で。

コードが単一ファイルで完結できるWeaveを使ってみます。
でもPython 3では使えないし、これからはCythonでやれって書いてあるんですよね。とりあえず今回は手軽さ重視で。

（Py_INCREFとかの使い方に自信がないのですが…）

counter.py

import weave
import timeit

def count_weave(it):
    counter = {}
    iter_inner = iter(it)
    code = r"""
    PyObject *item;
    while ((item = PyIter_Next(iter_inner)) != NULL)
    {
        Py_INCREF(item);
        if (PyDict_Contains(counter, item)) {
            PyObject *countold = PyDict_GetItem(counter, item);
            PyDict_SetItem(counter, item, PyInt_FromLong(PyInt_AsLong(countold) + 1));
            Py_DECREF(countold);
        } else {
            PyDict_SetItem(counter, item, PyInt_FromLong(1));
        }
        Py_DECREF(item);
    }
    """
    weave.inline(code, ["iter_inner", "counter"])
    return counter

if __name__ == '__main__':
    seq = 'ACAGCATGCA' * 10000000
    print(timeit.timeit("count_weave(seq)", setup='from __main__ import count_weave, seq', number=1))

terminal

$ python2.7 counter.py
3.3560230732

やっぱり速い。
ちなみに最初のCounter, defaultdictの結果を再掲すると

terminal

$ python2.7 counter.py
27.1584978104
5.29513907433

でした。つまりdefaultdictと比べてさらに40%近く計算時間が減りました。

本来はCythonで書くべきなのでしょうが、あくまでCで実装すれば速くなる見込みがあるということを確認したまで、ということで。