ニシキヘビってかわいいよね、実際みたことないけど。

いよかん国でプログラミングとかの備忘録を書いてます。 一日一食たまごかけごはん。

Pythonで値の数え上げと速度比較

時間が空いたらやってみたかった自然言語処理100本ノックをしてます。
問83を愚直に実装して、処理速度とメモリ空間の消費に苦しみました()

その時の単語数の数え上げで、処理が早いのはどのような方法か気になったので調べてみました。

まずはおさらい的な何か
  • dict(辞書)型

ビルドインオブジェクトの1つで、 他の言語ではハッシュ型とかマップ型とかとも呼ばれてるものですね。

dをdict型ライクなインスタンス、keyを辞書のキー、valueをkeyに代入する値とするとき、

インスタンス

d = dict()

または

d = {}

最近、空要素をインスタンス化するときはdict()を使うようにしてます。
{}だと,Set型のようにもみえるので。

JavaScriptだと、リテラルで初期化したほうがいいという話をよく聞きますし、
JavaScriptパターンでも利点等が挙げられているので、リテラルによる初期化を使ってますが、
Pythonだとどちらがいいのでしょうか……

値の代入

d[key] = value

keyが存在しない時はKeyError例外が投げられます。
なので、値の追加・更新時には、キーが存在する時としない時で処理を分岐させるために、
下記の確認とセットでよく用いられます。

if key in d:
    # キーが存在するときの処理

さらに、数え上げのように、キーがないときは0を返してもらいたいという時は、
get()メソッドを使うことで、if分岐無しで書くことができます。

d[key] = d.get(key, 0) + 1  # 第1引数にkey、第2引数にkeyがないとき返す値。

キー参照の最速計算量はもちろんO(1)ですので、気兼ねなくつかえます。
一方でメモリをドカ食いします……
が、複数文書の単語数え上げ等をするときは、スパース性より(文書数)×(素性数)のリストを作るよりも軽くすむので、
scipyのsparseパッケージや、scikit-learnのCountVectorizerを使わずにサクッと数え上げたいときに重宝します。

  • defaultdict型

付属してる電池の1つであるcollectionsパッケージにあります。
dict型のサブクラスです。

インスタンス

d = defaultdict(int)

第一引数にオブジェクトやファクトリなど、コール時にインスタンスを返すオブジェクトを渡すと、
存在しないキーをつかったアクセスを行った時に、それで初期化されます。
なので先述の初期化直後のdに対して

d[key] += 1

とすると、例外が出ずにd[key] = int()がされ、その後加算が行われます。

  • Counter型

これもcollectionsパッケージ内にあります。
名の通り、数え上げのためのオブジェクトです。

インスタンス

d = Counter()

インスタンスメソッドのupdate()にイテレータを渡すと、その値をキーとしたカウントを行います。

d.update(['a', 'a', 'b'])

上の例の結果は、d[‘a’] = 2、 d[‘b’] = 1 になります。
初期化時にもイテレータを渡すことができ、内部でself.update()を呼び出しています。

また、コンストラクタにintを渡した時のdefaultdict同様、まだ存在しないキーへのインクリメントも行えます。
あと、いくつかの便利なメソッドが用意されています。
most_common()や四則演算、集合演算ができるのはすごいなと思いました(こなみかん)。

本題

いろいろあるので、いろいろな値の数え上げ方法があります。
試しに以下の6つの方法の速度を比較しました。

下記例のkeysは[‘wakame’, ‘combu’, ] や [3, 8, ]など,
個数を数え上げたい単語や、ボキャブラリリストのインデックスなどが格納されたイテレータを想定しています。

1.dict型とifで普通に

d = dict()

for key in keys:
    if key in d:
        d[key] += 1
    else:
        d[key] = 1

2.dict型とEAFPスタイル

d = dict()

for key in keys
    try:
        d[key] += 1
    except KeyError:
        d[key] = 1

用語集にも書いてる許しを請うスタイルです。
ループ展開した時、辞書内にキーが存在する時の処理が殆どを占める場合は、こちらのほうが早いはずです。

3〜6は、おさらいっぽいところでほとんど解説が終わってるので、コードは略。

3.dict(get()を使用)

4.defaultdict

5.Counter(辞書アクセスで1つづつ)

6.Counter(update()メソッドを使用)

テストに使ったデータは以下の3つです。

1.ランダム

keys = [randint(1, KEY_MAX_VALUE) for _ in range(KEY_NUM)]

2.すべて異なるキー

keys = [i for i in range(KEY_NUM)]

3.すべて同じキー

keys = [1 for _ in range(KEY_NUM)]
結果

パラメータの KEY_MAX_VALUE は 1000、 KEY_NUM は 10e6で、 実行時間はtimeモジュールのtime()を用いて計測しました。

実行環境は primergy-tx100-s3(Intel® Pentium® CPU G640 @ 2.80GHz, Memory 32GB) です。 あたらしいPCかうおかねほしい…… しごとほしい……

時間の単位はミリ秒です。

テストデータ: ランダム

方法 時間 順位
dict 1.8064448833465576 4
dict (EAFPスタイル) 1.4703152179718018 3
dict (dict.get()) 1.891401767730713 5
defaultdict 1.3624546527862549 2
Counter (辞書アクセス) 4.186056852340698 6
Counter (update) 0.9843113422393799 1

テストデータ: すべて異なるキー

方法 時間 順位
dict 0.9861924648284912 2
dict (EAFPスタイル) 3.5730416774749756 5
dict (dict.get()) 1.650207281112671 3
defaultdict 2.7152698040008545 4
Counter (辞書アクセス) 6.0724663734436035 6
Counter (update) 0.6565902233123779 1

テストデータ: すべて同じキー

方法 時間 順位
dict 1.317124605178833 4
dict (EAFPスタイル) 1.0367882251739502 3
dict (dict.get()) 1.4208016395568848 5
defaultdict 0.9261937141418457 2
Counter (辞書アクセス) 4.193308115005493 6
Counter (update) 0.5905847549438477 1
結果と考察

Counterのupdate()でまとめてカウントがかなり早いですね。
内部ではCで書かれたヘルパーメソッドでカウントしているようです。
一方で、インデックス指定でのカウントはかなり遅いです。

dictをつかった3つの方法では、だいたい予想通りの結果になりました。
ただ、重複キーがないときのEAFPスタイルが顕著に遅くなっています。
例外処理は重いとは聞いてましたが、こんなに遅いとは。
in句で調べたほうが安定してますね。

defaultdictについては、どのデータでもdict(EAFP)より早く、
dict/dict.get()との順位の大小は、dict(EAFP)とそれらの関係と同じになりました。
ソースを読んでないので断定できませんが、内部ではEAFPスタイルをとってると思われます。

カウントする以外処理がないなら、Counterのupdate()を、
ループ中にカウントアップ以外の処理を挟む必要があるなら、
明らかにキーが存在する場合が多い時は、defaultdict(int)を、
よくわからない場合は、in句で確認をするdictを使うのがよろしいかとおもいました、まる