辞書アプリの改良:高速化(6)
対策5:メタインデックス再び
対策4時点での実行時間は下記の通り。
word1:ああああああああああ、word2:い、word3:おた、word4:あいし、word5:あいして、word6:あいしてるとくりかえしていう。
目標の1秒までもう少しだが、まだいくつか1秒以上かかってしまう検索語が残っている。上のグラフを見ると、実行時間のほとんどはメタインデックス検索とその他が閉めていることが分かる。メタインデックス検索はまだ4割程度の時間を占めており、まだまだ高速化する価値がある。
対策4により、上記の検索語ではどれも1回しかメタインデックス検索は実行されていない。これ以上メタインデックス検索を高速化するためには、1回のメタインデックス検索での絞り込み結果がより少なくするようにする必要がある。
そこで、メタインデックスをバイグラム(2文字)からトリグラム(3文字)に変更してみる。また、検索語が3文字未満の場合は完全一致検索に変更する(これまでは1文字の場合に完全一致だった)。
結果
ようやく目標としていた1秒切り。
これで高速化はとりあえず終わりとしよう。
ソース
修正部分だけ。
MetaIndexHeader.groovy
public static final int KEY_LENGTH = 18 public static final int KEY_CHAR_LENGTH = 3 public static final int HEADER_LENGTH = 26
MetaIndex.groovy
public static final int LENGTH = 30
Index.groovy
def toMetaIndexList() { List list = [] def val = normalize(word) int i=0 while (i <val.length()-MetaIndex.KEY_CHAR_LENGTH +1) { list << new MetaIndex(val.substring(i, i+MetaIndex.KEY_CHAR_LENGTH), indexOffset, indexLength, i) i++ } if (val.length() < MetaIndex.KEY_CHAR_LENGTH) list << new MetaIndex(val, indexOffset, indexLength, 0) return list }
Dictionary.groovy
def cut(string) { if (string.length() < MetaIndex.KEY_CHAR_LENGTH) return [new MetaIndex(string, 0, 0, 0)] def list = [] int i=0 while (i <string.length()-MetaIndex.KEY_CHAR_LENGTH +1) { list << new MetaIndex(string.substring(i, i+MetaIndex.KEY_CHAR_LENGTH), 0, 0, i) i += MetaIndex.KEY_CHAR_LENGTH } if (string.length() % MetaIndex.KEY_CHAR_LENGTH != 0 && string.length() > 0) list << new MetaIndex( string.substring(string.length()-MetaIndex.KEY_CHAR_LENGTH, string.length()), 0, 0, string.length()-MetaIndex.KEY_CHAR_LENGTH) return list }