読者です 読者をやめる 読者になる 読者になる

Javaで簡潔ビットベクトル(6)

Java

さて、LBとSBを使って、高速なrank実装を行っていくわけですが、SBで特定したビットベクトルの範囲は、相変わらず、ビットベクトル内の線形探索になっているので、この部分を解決したいと思います。

問題をもう少し説明します。

まず、今回は、LBとSBの管理するビットサイズを以下のように設定します。

LB=256bit
SB=32bit

これにより、LBとSBを使って、ビットベクトルの範囲を絞り込めますが、0-31bit分は必ず線形探索になってしまいます。

f:id:ryokkie:20120226183219p:plain

範囲が0-31と少ないので十分高速ですが、より高速にする方法があります。
それは、rankの値を覚えてしまうという方法です。
覚えてしまうというのは、一見、うまい手法ではなさそうですが、日常生活にも溢れています。

例えば、九九なんかもそれに該当します。
小学校の時に九九を覚えたと思いますが、あれには理由があります。
つまり、大きな数の掛け算をする時に、九九を使うことで効率的に計算できるということです。
例えば、「5136 × 315」という掛け算を行う時、普通は、以下のような筆算で求めると思います。

 5136
× 315
------

この時、一つ一つの掛け算は、九九で求められる範囲の掛け算です。
九九で求めた掛け算の値を足していくことで最終的な答えを得ることができます。
つまり、9×9の範囲の掛け算(九九)をすべて覚えておくことで、筆算によってどんな大きな数の掛け算も計算できるということです。

今回の場合は、0-31bitの範囲の1の数を覚えてしまうことで、LBとSBで0-31bitの範囲を特定すれば、その範囲の1の数を高速に返すことができます。
ただし、0-31bitの範囲の1の数をすべて覚えると、2^32パターンも覚えないといけないので、メモリを使いすぎます。
なので、0-31bitの範囲は、32個なので、8個ずつに分割して覚えて、それぞれを合計して、0-31bitの範囲の1の数を計算しようと思います。

つまり、以下のような感じです。

+------24-31------+------16-23------+-------8-15------+-------0-7-------+
| 0 1 0 1 0 1 0 1 | 0 1 0 1 0 1 0 1 | 0 1 0 1 0 1 0 1 | 0 1 0 1 0 1 0 1 |
+-----------------+-----------------+-----------------+-----------------+

やりたいこととしては、8bitで表現できる任意の数値を入力した時に、その数値を2進数で表現した時の1の数を返してくれれば良いわけです。
例えば、01010101=85と指定した場合に、1の数は4個というのを返してくれれば良いわけです。

では、8bitで表現できる任意の数値を入力した時に1の数を返してくれる機能を実装してみましょう。
8bitで表現できる数は、0-255の256種類です。
これを、256個の要素を持つTABLEという配列で表現し、添え字が入力する数値に対応させ、添え字を2進数で表現した時の1の数を値に対応させます。
以下のようなイメージです。

TABLE[0] = 00000000 = 0
TABLE[1] = 00000001 = 1
TABLE[2] = 00000010 = 1
TABLE[3] = 00000011 = 2
...
TABLE[255] = 11111111 = 8

このようなTABLE配列によって、0-7bitの範囲(8bit)の1の数は、高速に計算することができます。

目的は、0-31bitの範囲(32bit)の1の数を高速に計算することです。
8bitの1の数を高速に求められるTABLE配列を使って、32bitの1の数を高速に計算してみます。
32bitの数値をWORDとして、以下のようにして計算します。

int rank32 = TABLE[ (WORD >> 24) & 0xff )
           + TABLE[ (WORD >> 16) & 0xff )
           + TABLE[ (WORD >>  8) & 0xff )
           + TABLE[  WORD        & 0xff );

どうでしょうか?簡単ですよね。8bitの1の数の組み合わせで、32bitの1の数を計算することができます。
例えば、WORDが以下のような2進数だったとしましょう。

+------24-31------+------16-23------+-------8-15------+-------0-7-------+
| 0 1 0 1 0 1 0 1 | 0 1 0 1 0 1 0 1 | 0 1 0 1 0 1 0 1 | 0 1 0 1 0 1 0 1 |
+-----------------+-----------------+-----------------+-----------------+

このとき、

TABLE[ (WORD >> 24) & 0xff )

という操作で、24-31bitの8bitの範囲の1の数を取得することができます。

また、

TABLE[ (WORD >> 16) & 0xff )

という操作で、16-23bitの8bitの範囲の1の数を取得することができます。

また、

TABLE[ (WORD >>  8) & 0xff )

という操作で、8-15bitの8bitの範囲の1の数を取得することができます。

また、

TABLE[  WORD        & 0xff )

という操作で、0-7bitの8bitの範囲の1の数を取得することができます。

では、実際に、

TABLE[ (WORD >> 16) & 0xff )

という操作を例にして、動きを見てみましょう。

まず、16bit分右にシフトすると、以下のようになります。

+------24-31------+------16-23------+-------8-15------+-------0-7-------+
| 0 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0 0 | 0 1 0 1 0 1 0 1 | 0 1 0 1 0 1 0 1 |
+-----------------+-----------------+-----------------+-----------------+

つまり、16-23bitの範囲にあった8bitの範囲を最も右側の0-7bitの8bitの範囲に移動させることができます。
また、24-31bitの範囲にあった8bitの範囲を8-15bitの8bitの範囲に移動させることができます。
そして、欲しいのは、0-7bitの8bitの範囲の1の数ですが、8-15bitの範囲にも値が存在するので、この部分が余分です。
最も右側の8bitが得られるように、0xffという以下のようなビットパターンでマスク処理を行います。

+------24-31------+------16-23------+-------8-15------+-------0-7-------+
| 0 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0 0 | 1 1 1 1 1 1 1 1 |
+-----------------+-----------------+-----------------+-----------------+

最も右側の8bitの値だけを残すように0xffのビットパターンでAND処理を行います(マスク処理)。
そうすると、以下のようになります。

+------24-31------+------16-23------+-------8-15------+-------0-7-------+
| 0 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0 0 | 0 1 0 1 0 1 0 1 |
+-----------------+-----------------+-----------------+-----------------+

マスク処理によって、8-15bitの範囲の値を取り除き、0-7bitの範囲のみを残すことができました。
マスク処理は、作業の対象にしたい部分だけを残すことができます。
これは、ミニ四駆で色塗りをする時のマスキングテープと同じような役割です。

ここまでくれば、求めたい8bitの範囲の値を取り出せているので、後は、8bitのテーブルを使って、1の数を数えるだけです。

このような操作をSBで特定した32bitの領域を8bit単位で分割して行えば、32bitのすべての値の1の数を覚えるということをしなくても、十分高速に求めることができます。

さて、ここまでですべて問題ないように感じますが、まだ問題が残っています。
例えば、SBで32bitの範囲を特定し、残り、32bitの値を求めたい場合は、今まで説明した8bit単位での表引きで求めることができます。
しかし、SBで32bitの範囲を特定し、残り、10bitの値を求めたい場合は、どうすればいいのでしょうか?

次回は、任意のbit数の1の数を高速に求める方法を検討してみます。