データ検索

データ検索に於いて実用的な検索時間は５万件のデータを２秒くらいらしい。
と言うことで、実験をやってみました。
うちのシステムは元々その手の使用用途で使われるものじゃないので、技術研究としてはなかなか面白かろうと。
大抵この手の作業はサーバー側でやってもらって、結果だけもらうという使われ方をするのですが、自己完結出来るならそれに超したことはないですし。


実験とはいえ、ある程度現実に即した形で実装しようということで、検索用データの持ち方をまずは考えてみました。
レコードには「一意のID（検索用ワード）＋紐付いたデータ数個」と言う形にしました。
さすがにデータを生のまま持つわけにはいかないので、IDはMD5ハッシュ値に変換、紐付いたデータは何らかの形で暗号化することに。
それを１０万件リスト化されたファイルを検索用データとして作成（データ部は結局平文にしちゃったけど）。
その１０万件のリストから任意の項目を検索します。


最初は、「直接データファイルを開いて上から順に調べる」という真っ直ぐすぎるのを作成。
２分かかりました。
もちろん最大値でなので、期待値は６０秒くらいでしょうか。
さすがにディスクアクセスは遅いし、検索のたびにファイルにアクセスするのは馬鹿らしいので、最初にメモリにロードしてからそれを検索データに使用することに。


メモリにロードしたデータを検索してみたところ、２０秒くらいに短縮しました。
でも、まだ１０倍かかってます。


やっぱり１０万件を実直に順番に検索しているのが良くないみたいで（あたりまえか）、検索前である程度ふるいにかける必要がありそうです。
真っ先に思いつくのが……というか、それしか思いつかなかったんですが、IDはハッシュ値（16進数）になっているので、頭文字を元にしてデータを１６のグループに分ければ、検索の回数が１６分の１になります。
実際には、ハッシュ値が均等に１６等分されるわけじゃないですが、これはなかなか効果がありそうです。
最終的に、頭の２文字まででグループ分けすることにして、グループは２５６、各グループのレコード総数を５００、最大１２万８千レコードを検索できるようにしました。
この方式で検索したところ、１０万件からのランダム検索が、大体0.3秒で終了するようになりました。
おお、最初から比べると４００倍速い。


さすがに最初は絶望的かと思ったけど、リッチな環境じゃなくてもやりようがあるんですね。
結果としては大満足です。


データ構造とか、アルゴリズムとかって重要なのね。
魔法学校時代にもっとまじめに取り組んでれば良かった……。