Personal tools
You are here: Home ブログ matsuyama Suffix Array で高速な locate を実現する
Document Actions

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 はデータベースの種類に関係なくこれまで通り使えます。

updatedb updatedb
Size 1.0 kB - File type application/octet-stream
locate locate
Size 1 kB - File type text/x-sh
Category(s)
linux
emacs
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 を実現する

Posted by inoue at 2008-02-02 04:32
こうやって夜遅くまで起きているから朝起きられない

金曜の夜の就寝時刻: 5時
土曜の夜の就寝時刻: 6時
日曜の夜の就寝時刻: 7時
月曜の朝の起床時刻: 8時

どこでバグっているんだろう。

Add comment

You can add a comment by filling out the form below. Plain text formatting.

(Required)
(Required)
(Required)
(Required)
(Required)
This helps us prevent automated spamming.
Captcha Image


Copyright(C) 2001 - 2006 Ariel Networks, Inc. All rights reserved.