Rubyで簡易検索エンジン、Rejuicerをリリースしました。

Rubyでお手軽に検索エンジンを構築できるライブラリ、rejuicerをリリースしました。
http://github.com/tsukasaoishi/rejuicer

インストール

sudo gem install rejuicer  

gemcutterで公開しています。

以下のようなオブジェクトの集合を考えてみます。

work = Struct.new(:id, :odd_flag, :remainder_3, :remainder_5)  
mother = (0...10000).inject([]){|m, i| m << work.new(i, i % 2 == 0, i % 3, i % 5)}  

この集合から、3で割った余りが2で、5で割った余りが4である数の集合を探してみましょう。
まずは検索エンジンのインデックスを構築します。

require 'rejuicer'  

index = Rejuicer.new(:odd_flag, :remainder_3, :remainder_5)  
index.set(mother)  

newメソッドの引数に、インデックス対象となるメソッド名を指定します。
そのあとのsetメソッドでインデックス対象のオブジェクト群を渡すことでインデックスが構築されます。
ここで投入されたオブジェクトそれぞれに対して、newメソッドで渡したメソッドがコールされ、その結果によって内部的に転置インデックスを構築しています。
識別IDは、標準でidメソッドの返り値を使用します。Rejuicer#setメソッドの第二引数で別のものを指定可能です。

では、検索してみましょう。

index.search(:remainder_3 => 2, :remainder_5 => 4) 
                  #=> [14,29,44,59,...,9974,9989]  

検索条件はHashで指定します。work#remainder_3の返り値が2であり、work#remainder_5の返り値が4である集合が返ります。
現在のところ、AND条件での検索しかできません。

■集合演算クラスRejuicerSet
集合演算にはRejuicerSetというライブラリを使用しています。Rubyの標準ライブラリであるSetやArrayでは速度が遅かったので、不満がない程度のパフォーマンスが出せるものを作りました。

先日の記事にも書きましたが、100万までの間の3の倍数と5の倍数の積集合を求める処理をベンチマークにかけてみます。

それぞれの集合の要素数  
     3 : 333334  5: 200000  

Set  
      user     system      total        real  
  0.573000   0.196000   0.769000 (  0.804500)  

Array  
      user     system      total        real  
  0.102000   0.005000   0.107000 (  0.107583)  

RejuicerSet  
      user     system      total        real  
  0.007000   0.000000   0.007000 (  0.006635)  

先日のときから10倍ほど高速化することができました。Setと比較すると100倍以上の差があります。
もともと、内部的には集合をunsigned intの配列で保持していました。しかし、これだと集合の要素数に比例して処理速度が低下してしまいます。
そこでデータ構造を木構造に変更しました。ルートは8つの枝を持ち、それぞれの枝は256の枝を持ちます。階層はルートを入れて5段階です。最後の葉ノードは、unsigned intのデータを持っていて、ひとつのノードで0～31までのIDを管理しています。となりのノードはオフセットが32になり、32～63までのIDを管理します。管理できるID値は0～0xFFFFFFFの範囲になります。
積集合の演算では、同じ位置の葉ノードが存在するかどうかを調べます。同じ位置の葉ノードがあった場合は、お互いのデータでANDのビット演算をかけます。
これによってかなりの速度向上につながりました。実際のところ、純粋に積集合の演算時間はトータルの半分以下です。残りは、内部のデータ構造からArrayオブジェクトを作成する部分にかかっています。
まだまだ改善の余地はありまくりですので、いろいろ手を加えていこうと思います。

おおいしつかさ

Rubyで簡易検索エンジン、Rejuicerをリリースしました。