検索の高速化（4）

　(3)の結果はあまりよくない予感がするので、別の方法を考えてみた。つまり、SuffixArrayをいくつか（数百か数千ぐらい）に分割して、分割点のみを集めたミニSuffixArrayとでもいうべきものを作ってみる。ミニSuffixArrayのサイズは自由に決められるので、数KB程度を使えばいいだろう。この程度のサイズであれば二分探索どころか線形探索でも問題なく検索できそうだ。ミニSuffixArrayに1000個の点を用意した場合について考える。この場合、探索範囲は1/1000に縮められる。これは二分探索で言うと約10回分の探索回数の削減になる。（2^10=1024）
　探索回数の削減自体は大した事ではないが、これによるディスクへのランダムアクセス回数の削減が重要なところだ。では、ランダムアクセスにかかるコストはどれぐらいか？
　ちょっと古いが、Ultra DMA/66の性能検証の記事によると、ランダムアクセスにかかる時間は15msぐらい。他の記事によると、いまどきのHDDの平均シーク時間は8ms程度であるようだ。実際の読み込みにはディスクの回転待ち時間がかかるので、もうちょっと時間がかかる。回転数として7,200rpmを仮定すると、一回転するのに1/7200min=1/120sec≒8msがかかるので、平均待ち時間はその半分という事で約4ms。やはり、いまどきのHDDでも一回ディスクにランダムアクセスすると、15ms弱程度の時間はかかるようだ。
　一回15msかかるアクセスを10回削減できたとして、150msか。0.15秒の削減。うーむ、微妙だ。頑張って分割点を8000ぐらいに増やしてみたとして、減らせるアクセス回数は13回。15×13=195≒0.2sec。嬉しくないとは言わないが、大して嬉しくないなぁ…。