ソートを前提に推測して探索してみた

二分探索 - malibu-bulldogの日記
に書いたとおり、二分探索を使ってデータを探索していたんだけど…でも大規模データが対象となるとそれでも遅い！

規模は「探索の対象」となるデータの数が１０００万個ぐらい。

ってことで、さらに高速化にチャレンジした。

データの特性としては一意のIDが連番の場合が多い。

で、それを利用して最初は普通に二分探索して、２度目からは前回の探索結果から対象となるIDがどれぐらい離れているかを考えることに。

推測してあたりをつけるってことです。

で、そのためにソートしました。

結果として、相当速くなりました。

ちょっと感激です。