Suffix Array で高速な locate を実現する
アルバイトのハッカー Fujita さんに GNU locate が遅くて使えないよほげほげと愚痴ってたら sary (*) と find を使って高速な擬似的 locate を実験的に実装してくれたので、それのちゃんとした実装の紹介をします。
(*) http://sary.sourceforge.net/
動作原理
find でファイル一覧をとってきてデータベース化し sary で高速に検索します。
% find . > locatedb % mksary locatedb % sary hoge locatedb
データベースファイルがでかい上、検索に正規表現を使えないという制限がありますが、検索はめちゃくちゃ速くなります。
インターフェースの統一
mksary や sary をそのまま使用する場合、 Emacs のフロントエンドを独自に書いたりしないといけなくて面倒くさいです。なのでそのあたりを updatedb と locate のインターフェースに統一するラッパースクリプトを作って楽をします。
% # こんな感じになる % updatedb --dbformat=sary # => find . > locatedb; mksary locatedb % locate hoge # => sary hoge locatedb
インストール
本エントリに添付してある locate と updatedb をダウンロードしてきて ~/bin などにインストールしてください。これらのラッパースクリプトは「GNU locate を有効活用する」(*)で紹介したラッパースクリプトの拡張版です。
(*) http://dev.ariel-networks.com/Members/matsuyama/use-gnu-locate
% which locate /home/tomo/bin/locate % which updatedb /home/tomo/bin/updatedb
使い方
基本的な使い方は「GNU locate を有効活用する」(*)を参照してください。今回拡張されたのは updatedb だけなので、ここではそれの紹介のみにとどめます。
(*) http://dev.ariel-networks.com/Members/matsuyama/use-gnu-locate
updatedb
--dbformat=sary を指定することで sary でデータベースが構築されます。
% updatedb --dbformat=sary % ls PATH PATH.ary ...
~/.updatedbrc に updatedb へのオプションを記述しておくことで updatedb の度にオプションを入力する手間を省くことができます。
~/.updatedbrc:
/home/tomo/PATH # ホームディレクトリでのオプション --dbformat=sary --findoptions=-name tmp -prune /home/tomo/src/javaproj/PATH # Java のプロジェクトでのオプション --findoptions=-name .svn -prune -o ! -name '*.class'
上記の ~/.updatedbrc の場合、ホームディレクトリでは sary でデータベースを構築し(遅いから)、 ~/src/javaproj では GNU updatedb でデータベースを構築します(正規表現を使いたいから)。
locate はデータベースの種類に関係なくこれまで通り使えます。
- The URL to Trackback this entry is:
- http://dev.ariel-networks.com/Members/matsuyama/make-locate-fast-with-suffix-array/tbping
Re:Suffix Array で高速な locate を実現する
金曜の夜の就寝時刻: 5時
土曜の夜の就寝時刻: 6時
日曜の夜の就寝時刻: 7時
月曜の朝の起床時刻: 8時
どこでバグっているんだろう。