[ トップページ ]

« 地域軸検索からの地図表示機能の追加 | メイン | WASS を工学院大学での講義に使用した »

ハッキング

候補しぼりこみの高速化

WASS の軸づけ検索では最初に文字インデクスを使用して検索対象をしぼりこむ. そのためにこれまで Perl の vec() を使用していたが,unpack() を使用する方法にかえて,この部分だけをとると 5 割ほど高速化された.

文字インデクスは,すべての文字について,その文字 (ひらがな,カタカナのときは 2 グラム単位) が出現する Wikipedia の項目のリストをふくんでいる. 文字インデクスがしめるメモリ量をへらすため,文字インデクスは Perl のデータではなく,1 要素 4 バイトに圧縮された表現をつかっている. この形式にアクセスするために,これまでは vec 関数を使用してきた. すなわち,つぎのようなプログラムをつかってきた.

my $indexVec = $index{$s};
for (my $i = 0; $i < bytes::length($indexVec); $i++) {
    $count{vec($indexVec, $i, 32)}++;
}

しかし,vec 関数は 1 ビットごとのアクセスが可能な汎用の関数であり,そのぶんオーバヘッドがあるとかんがえられる. pack 関数を使用して,あらかじめデータを通常の配列にしておくほうが効率的なのではないかとかんがえて,ためしてみた. つまり,つぎのようなプログラムにする.

my @indexVec = unpack('N*', $index{$s});
foreach my $index (@indexVec) {
    $count{$index}++;
}

このプログラムも配列への変換という,けっしてかるくない操作をふくんでいるのだが,それでもこのほうが 5 割ほどはやいことがわかった. ただし,通常はこのあとの操作のほうがおもいので,全体としての高速化は 3 割,あるいはそれ以下にとどまっている.

なお,unpack するときに 'N' つまり network-byte-order を指定しているのは,vec によってアクセスするときは network-byte-order になるからである. これによって,インデクスに格納されたデータは vec, unpack のどちらでもアクセスできるようになる.

キーワード:

トラックバック

このエントリーのトラックバックURL:
http://www.kanadas.com/mt/mt-tb.cgi/4349

コメントを投稿


メインページアーカイブページも見てください.

Powered by
Movable Type 3.36