ある整数値が与えられたとき、それを二進数表記した時の1の個数(1になっているビットの数)を数えるのをpopcountと呼ぶらしい(population countの略)。これはハミング距離を計算するのに使え、2つの値のXORをとってpopcountを計算すればハミング距離となる。
Pythonには標準で用意されてないので、64ビット整数に対する演算を想定していくつかの実装を比べてみる。
Python 3系は整数に決まった上限がないので、64-bit unsigned int相当のの範囲の整数値を入力として計算する。
TL;DR
- bin(n).count("1")が簡潔でそこそこ速い
- メモリを使ってよければ、事前計算した216要素の配列を引くのが標準機能だけでは最速に近いかもしれない
- gmpy2ライブラリのgmpy2.popcount(n)を使うのが最速
速度の計測
Python 3でいくつかの実装の速さをみてみる。
環境
速度の計測にはrandom.getrandbitsで64ビットの乱数を取得してそれに関数を適用し、1000000回の処理時間をtimeitで測定した。
測定結果
| 関数 | 秒数 |
|---|---|
| dummy | 0.4457 |
| popcnt0 | 9.9395 |
| popcnt1 | 1.4312 |
| popcnt2 | 1.7646 |
| popcnt3 | 1.6916 |
| popcnt4 | 1.6313 |
| popcnt5 | 1.0738 |
| popcnt6 | 0.4762 |
dummyは、何も計算せず定数を返す関数であり、乱数の取得や関数呼び出しにどの程度の時間がかかるかをみる為に用意した。
def dummy(n): return 0
popcnt0: 単純なループによるもの
工夫しないとこの程度の時間になるという、比較用のベースラインとして用意した。
def popcnt0(n): c = 0 for i in range(64): c += (n >> i) & 1 return c
これより遅い実装も可能で、再帰を使ったものは実行時間がこれの2倍程度になった。
2進数の文字列にして“1”の数を数える
標準ライブラリでシンプルに実装できるうえ、桁数の制限がない。
popcnt1: bin()を使うもの
def popcnt1(n): return bin(n).count("1")
標準機能だけでシンプルであり、速度的にもそんなに遅くないので、大抵はこれを使えば十分そうである。
popcnt2: "{:b}".format()を使うもの
def popcnt2(n): return "{:b}".format(n).count("1")
bin()を使った場合より遅かった。
popcnt3: ビット演算を使うもの
def popcnt3(n): c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555) c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333) c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f) c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff) c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff) c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff) return c
ビットマスク・ビットシフトと足し算を使って計算したもの。原理は次を参照。
事前に計算した配列を引くもの
8ビット、16ビット等適当に決めたビット数で表現できる任意の整数に対するpopcountを計算した配列を事前に用意しておき、実際にpopcountを計算する時には64ビット値を事前に決めたビット数ごとに分割し、配列から対応する計算済みの値を取り出して足し合わせる。
popcnt4: 2^8要素の配列を利用
POPCOUNT_TABLE8 = [0] * 2**8 for index in range(len(POPCOUNT_TABLE8)): POPCOUNT_TABLE8[index] = (index & 1) + POPCOUNT_TABLE8[index >> 1] def popcnt4(v): return (POPCOUNT_TABLE8[ v & 0xff] + POPCOUNT_TABLE8[(v >> 8) & 0xff] + POPCOUNT_TABLE8[(v >> 16) & 0xff] + POPCOUNT_TABLE8[(v >> 24) & 0xff] + POPCOUNT_TABLE8[(v >> 32) & 0xff] + POPCOUNT_TABLE8[(v >> 40) & 0xff] + POPCOUNT_TABLE8[(v >> 48) & 0xff] + POPCOUNT_TABLE8[ v >> 56 ])
この環境ではbin(n).count("1")のpopcnt1より遅いのでわざわざ使うものではなさそう。
popcnt5: 2^16要素の配列を利用
POPCOUNT_TABLE16 = [0] * 2**16 for index in range(len(POPCOUNT_TABLE16)): POPCOUNT_TABLE16[index] = (index & 1) + POPCOUNT_TABLE16[index >> 1] def popcnt5(v): return (POPCOUNT_TABLE16[ v & 0xffff] + POPCOUNT_TABLE16[(v >> 16) & 0xffff] + POPCOUNT_TABLE16[(v >> 32) & 0xffff] + POPCOUNT_TABLE16[(v >> 48) ])
この環境では標準機能だけを利用した中では最速となったが、速度は環境に依存しそうではある。あと、2^16個の要素からなる配列をメモリに確保するのはあまりうれしくない。
また、ここではpopcountの計算だけを行っているが、他にもいろいろな処理をする場合には配列がキャッシュに乗りきらず速度は低下するのではないかと書いてる人もいた。
popcnt6: gmpy2ライブラリを使う
Cで実装された多倍長演算Pythonライブラリgmpy2を使うのが速そうである。ライブラリのコンパイル設定にもよるかもしれないが、gmpy2が利用しているライブラリであるGMPやMPIRはSSE4.2で追加されたPOPCNTというCPU命令を内部で使っているようだ。
GMPやMPIR自体が多倍長演算ライブラリなので、桁数の制限もなさそう。
インストール
Windowsではプリコンパイルされたものがあるのでそれを使うか、Anacondaを使用してる場合はAnaconda Promptからcondaコマンドで入れることができる。
conda install -c anaconda gmpy2
Unix/Linuxの人はInstallationを参照。Ubuntuではaptで入るらしい(python3-gmpy)。
コード
import gmpy2
popcnt6 = gmpy2.popcount
最速。定数を返すdummy関数の場合と実行時間が大して変わらず、popcountの計算にほとんど時間がかかっていないことがわかる。ライブラリが使える環境であればこれを利用するのが速い。
まとめ
標準機能だけを利用する場合、bin(n).count("1")が簡潔で速度も悪くなく、大抵はこれを使えば良さそう。桁数の制限もない。
標準機能だけの利用で最速なのは事前計算した2^16要素からなる配列を引くものであった。とはいっても環境によっては遅いかもしれないし、メモリを必要とするのであまりうれしくない。
外部ライブラリを使ってよいのであれば、gmpy2のgmpy2.popcountを使うのが一番速そう。
とはいえそこまで速度追い求める必要があるのならPython使わない気もするが…。
