「ビットカウントする高速アルゴリズムをPythonで実装しながら詳しく解説してみる」というのを見つけた。
Python の整数は 64 ビット整数,R は 32 ビット整数であることを考慮し,以下のように翻訳した。
bitcount = function(n) {
# nの立っているビット数をカウントする関数(nは64bit整数)
# 2bitごとの組に分け、立っているビット数を2bitで表現する
n = n - bitwAnd(bitwShiftR(n, 1), 0x55555555)
# 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
n = bitwAnd(n, 0x33333333) + bitwAnd(bitwShiftR(n, 2), 0x33333333)
n = bitwAnd((n + bitwShiftR(n, 4)), 0x0f0f0f0f) # 8bitごと
n = n + bitwShiftR(n, 8) # 16bitごと
n = n + bitwShiftR(n, 16) # 32bitごと = 全部の合計
return(bitwAnd(n, 0x0000007f))
}
正しく移植できたか,確認してみる。
> bitcount(7)
[1] 3
> bitcount(127)
[1] 7
> bitcount(2^31-1)
[1] 31
> bitcount(-1)
[1] 32
R の intToBits() は,整数の二進表記を得るものである。これを用いてビット 1 を数えるのは自然である。 intToBits() のクラスは "raw" なので,as.integer() で整数化してから合計する。
bitcount2 = function(n) {
return(sum(as.integer(intToBits(n))))
}
同じ結果になることが確認できる。
> bitcount2(7)
[1] 3
> bitcount2(127)
[1] 7
> bitcount2(2^31-1)
[1] 31
> bitcount2(-1)
[1] 32
では,両者の速度比較をしてみる。intToBits() がベクトルに対応していないので,心ならずも for ループで検証する。
> mx = 1000000000
> n = sample(mx, 1000000) # 100 万個の整数
> a = integer(mx)
> b = integer(mx)
> system.time({for (i in n) a = bitcount(i)})
ユーザ システム 経過
6.915 0.198 7.118
> system.time({for (i in n) b = bitcount2(i)})
ユーザ システム 経過
1.620 0.148 1.769
> all(a == b) # どちらの結果も同じか?
[1] TRUE
結論は,「intToBits() を使う方が 4 倍ほど速い」ということだが,100 万個の整数を処理して 2 〜 7 秒なので,1 個や 100 個なら,どちらの方法でも,ゴミのような差しかない。
======================================
ついでに,Python でも代替関数について調べてみた。
Python には二進表記をするための bin() がある。これは文字列として二進数を返すので,文字列の中に '1' がいくつあるか数える。
大元のビットカウントのプログラム
def bitcount(x):
'''xの立っているビット数をカウントする関数
(xは64bit整数)'''
# 2bitごとの組に分け、立っているビット数を2bitで表現する
x = x - ((x >> 1) & 0x5555555555555555)
# 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
x = x + (x >> 8) # 16bitごと
x = x + (x >> 16) # 32bitごと
x = x + (x >> 32) # 64bitごと = 全部の合計
return x & 0x0000007f
対する,bin() を使う関数。短い。
def bitcount2(x):
return sum([i == '1' for i in bin(x)])
100 万個の整数を対象とする。
import scipy as sp
a = sp.random.randint(-10, 100000000, 1000000)
def func1(): # 4.383 sec.
x = [bitcount(i) for i in a]
def func2(): # 3.416 sec.
y = [bitcount2(i) for i in a]
やはり,bin() を使う方が速い。
sp.all(x == y) は True である。
※コメント投稿者のブログIDはブログ作成者のみに通知されます