文字の出現回数を数える/辞書型キー初期化
文字の出現回数といっても、ASCIIの文字だけで、また文字列の中で数えられるくらいならs.count('a')で十分でしょう。
でもサイズの大きいテキストファイルを読み出しながら、漢字などの要素数の多い集合であらかじめ出現するどの文字が出現するかは分からないという状況では、あらかじめすべての文字のカウントを初期化しておくことが難しいので、初めて文字が出てきた時に初期化を行う、という事が多いと思います。
Perlであれば初期化なんか考えず「++$HASH{$key}」とか書けてしまうので、辞書型キー初期化はPython使いとして悩ましいところなのですが…
さて、どうすればスマートで速いコードが書けるでしょうか。
A ... if else statement
素直にif else文を使った書き方です。0をセットしてから1加算するよりは速いだろうってことで、1をセットしています。
count = {} for k in s: if k in count: count[k] += 1 else: count[k] = 1
B ... d[k]=d[k]+1 if k in d else 1
count = {} for k in s: count[k] = count[k]+1 if k in count else 1
C ... d[k]=d.get(k,0)+1
getのデフォルト値オプションを使います。
count = {} for k in s: count[k] = count.get(k,0)+1
D ... defaultdict(lambda:0)
Python 2.5から導入されたdefaultdictを使います。マニュアルとは違った初期値呼び出しをしていますが…
count = defaultdict(lambda:0) for k in s: count[k] += 1
E ... defaultdict(int)
同じくdefaultdictで、こちらはマニュアルに書かれたとおりの使用方法。
count = defaultdict(int) for k in s: count[k] += 1
F ... d.setdefault(k,0); d[k]+=1
setdefaultを使います。「d.setdefault(k,0)+=1」と書くとSyntaxErrorになるので仕方なく2行に分けることに。
count = {} for k in s: count.setdefault(k,0) count[k] += 1
G ... d.setdefault(k,[0])[0]+=1
setdefaultを使いますが、2行に分けずに済ませたいため変なことをやっています。
count = {} for k in s: count.setdefault(k,[0])[0] += 1
手元のPython 2.5.4でtimeit 100000回平均で測定したら、結果が次のようになりました。
QBF ABC ─── ─── 40.39 46.09 A ... if else statement 40.14 47.45 B ... d[k]=d[k]+1 if k in d else 1 69.52 75.67 C ... d[k]=get(k,0)+1 92.29 47.97 D ... defaultdict(lambda:0) 94.83 49.29 E ... defaultdict(int) 83.24 87.70 F ... d.setdefault(k,0); d[k]+=1 113.87 129.70 G ... d.setdefault(k,[0])[0]+=1 (マイクロ秒) QBF ... "THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG" (※初期化の回数が多い) ABC ... "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBCCCCDD" (※初期化の回数が少ない)
結局のところ、変に凝った書き方をするより「if else文」で素直に書くのが総じて速いという結果でした。
で、そのif else文を除くと、Python2.5以降は「if else演算子」を使うのが一番速く、Python2.4までだとgetを使うのが一番速いようです。
setdefaultは少し遅いので、単純な初期化で使うのは避けた方がいいかもしれません。ただsetdefaultは「d.setdefault(k,[]).append(x)」「d.setdefault(k1,{})[k2] = x」のような場合スマートに書けるので捨て難いのですが…
defaultdictはどうも初期化呼び出しのコストが大きいようです。Python 2.5以降であればスマートに書けるし、if else演算子と同じくらいの速度も出るのですが、初期化が頻繁に呼び出されるパターンになるとsetdefaultにさえ負けてしまいます。
…取りあえず今はここまで。後で時間が取れたら、Python 2.6や3.0でsetdefaultやdefaultdictが改善されているか、別の書き方(and orとかtry except KeyErrorとか)で速度が出せないか、調べてみます。
(2009-12-26) 単なる文字数カウントと思われそうなので、タイトルと冒頭部分を修正しました。それから、やはりdefaultdictはパフォーマンス問題が指摘されていたようです。もし改善されているようであれば、これまで書いてきたsetdefaultハックをdefaultdictに置き換えるようかもしれません。