競技プログラミングをしていると、ある数を二進数で表したときにいくつ1であるような桁があるか(= popcount)を求めたいときがあります。
PyPyではどのように求めるのが高速なのでしょうか。
bin(X).count("1")
二進数の文字列に変換して、そこに含まれる1の数をカウントします。
bin(X).count("1")
while文
while文で下のbitから1bitずつカウントします。
ans = 0
while X:
ans += X&1
X >>= 1
bit_count
新しいバージョンのpythonにはこのpopcountを求めるメソッドがあります。
X.bit_count()
bit演算
bit演算や足し算引き算を利用することで並列に処理します。
(下記のコードは32bit整数向けであることに注意してください)
def popcount(x):
# from : https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
# for 32-bit integers
c = x - ((x >> 1) & 0x55555555)
c = (c & 0x33333333) + ((c >> 2) & 0x33333333)
c = (c + (c >> 4)) & 0x0F0F0F0F
c = (c + (c >> 8)) & 0x00FF00FF
c = (c + (c >> 16)) & 0x0000FFFF
return c
PyPy3で速度比較
PyPy 7.3.12で速度を比較します。
| $0$ から $ 2^{30}-1 $ まで | |
|---|---|
| bin(x).count('1') | 556.492s |
| while文 | 21.147s |
| bit_count | 8.479s |
| bit演算 | 1.446s |
比較に用いたコード
bin
ans = 0
for i in range(2**30):
ans += bin(i).count('1')
print(ans)
while文
ans = 0
for i in range(2**30):
while i:
ans += i&1
i >>= 1
print(ans)
bit_count
ans = 0
for i in range(2**30):
ans += i.bit_count()
print(ans)
bit演算
ans = 0
def popcount(x):
# from : https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
# for 32-bit integers
c = x - ((x >> 1) & 0x55555555)
c = (c & 0x33333333) + ((c >> 2) & 0x33333333)
c = (c + (c >> 4)) & 0x0F0F0F0F
c = (c + (c >> 8)) & 0x00FF00FF
c = (c + (c >> 16)) & 0x0000FFFF
return c
for i in range(2**30):
ans += popcount(i)
print(ans)
(おまけ) Python3で速度比較
Python 3.10.9で実行してみます。
($ 2^{30} $までだと終了する気がしなかったので範囲を変えています。)
| $0$ から $ 2^{25}-1 $ まで | |
|---|---|
| bin(x).count('1') | 14.747s |
| while文 | 183.771s |
| bit_count | 5.155s |
| bit演算 | 26.325s |
かなりwhile文のプログラムが低速になりました。
PyPyではbit演算のものが高速でしたが、Pythonではbit_countの方が高速なようです。CPythonの場合は内部で__builtin_popcountを呼んでいる1ので、それが効いていそうですね。(PyPyのbit_countでは内部でwhileループを用いて実装が行われています。2)
実際に、非常に大きなサイズの整数のbit_countを行う際は、PyPyよりもPythonの方が高速なこともあるようです。
https://atcoder.jp/contests/abc258/submissions/65727523
https://atcoder.jp/contests/abc258/submissions/66875602