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

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

Java

rankの高速化の前に、getNaiveRankメソッドの何が問題となっているかについて整理します。

まずは、復習としてrankの定義から始めます。

rankの定義は以下でした。

rank( B, pos, b )

また、rank操作とは、以下のような内容でした。

ビットベクトルBとして、b=(0 or 1)がposまでに出現する数を求める操作

さて、getNaiveRankメソッドの性能問題はとてもシンプルで、エンタープライズレベルのプログラミングをしたことがある人ならわざわざ説明するほどでもないことです。
ただ、そうではない人もいるので、イメージ化してみます。
自分へのメモでもあります。

getNaiveRankメソッドの問題をイメージ化したもの*1を以下に示します。

f:id:ryokkie:20120221234720p:plain

要は、常に、ビットベクトルの0番目の要素からpos番目の要素までのビットを調べて、数えているため、posの値に依存した時間がかかってしまうことが問題だということです。
つまり、pos=10の時とpos=1000の時では、性能が100倍違うということです。
まぁ、当たり前と言えば当たり前ですが、問題の出発点を明確にしておくためにわざわざ説明してみました。

なので、getNaiveRankメソッドを高速化するためには、

posの値に依存しないような実装

が重要になります。

さて、次回は、getNaiveRankメソッドを、参考にしている本に基づいて、高速化する方法を検討してみます。

*1:ブログ全体の図については、たいしたことない図なので、使う人はいないと思いますが、一応、私の著作物なので、利用する場合は、一声おかけください。