辞書アプリの改良：高速化（２）

対策１：存在しない文字列は検索しない

辞書アプリの改良：高速化（１） - Random Noteの測定結果を見て分かるのは、検索結果が0件の場合でも常に検索キーを2文字ずつに切り出した言葉の欠片（検索片と呼ぶことにする）の数分、必ずメタインデックスを検索している。

しかし、実際には検索キーの一部だけで既に対象が存在しないことが分かる場合があり、その場合それ以後の検索は全て無駄となる。例えば検索キー「ああああああああああ」を見ると、「あああ」の時点で既に検索結果が0になる。つまり実際にメタインデックスを検索するのは最初の「ああ」と次の「ああ」だけでよい。
逆に検索結果が0になった時点で検索を終了しないと、検索キーが長くなればなるほど実行時間が長くなってしまう。

検索結果が0になった時点で終了するためには、各ロジックの実行順序を変えればよい。
これまでは

1. メタインデックス検索
   • 全ての検索片についてメタインデックスを検索
2. 弱い論理積
   • 上の結果取得した各メタインデックス集合の弱い論理積をとる
   • 弱い＝要素の同一判定に辞書インデックスのoffsetだけを利用している
3. 文字位置チェック
   • 上の結果取得したメタインデックス集合の文字位置をチェック

だったのを

1. メタインデックス検索
   • 1回目は1つめのみ、次回は以降は前回の次の検索片についてのみ
2. 弱い論理積
   • 1回目は上記結果のメタインデックス集合をそのまま保存
   • 2回目以降はこれまでの結果できたメタインデックス集合と、上記結果のメタインデックス集合で弱い論理積
3. 文字位置チェック
   • 上記で追加されたメタインデックスについてのみ文字位置チェック
4. 検索結果数確認
   • 検索結果が0件か残りの検索片がなければ終了
   • そうでなければ最初に戻る

とすればよい。

ソース

修正したソースは下記の通り。ちなみにDictionary, MetaDictionary, BaseDictionary, Timerもそれぞれファイルを分割した。
変更のないものは省略。

Dictionary.groovy

class Dictionary extends BaseDictionary {
	def meta
	def file
	def dictFile
	def Dictionary(String fileName) {
		meta = new MetaDictionary(fileName)
		file = new File(fileName + ".idx")
		dictFile = new File(fileName + ".dict")
	}
	
	def search(key) {
		def metaSearchTimer = new Timer("meta search[${file.name}]")
		def intersectionTimer = new Timer("weak intersection[${file.name}]")
		def filterTimer = new Timer("filter[${file.name}]")
		def keyFragments = cut(key)
		def metaIndexList = null
		def baseMap = [:]
		for (fragment in keyFragments) {
			metaSearchTimer.start()
			def newList = meta.search(fragment.word)
			if (newList.empty) {
				metaSearchTimer.stop()
				intersectionTimer.stop()
				filterTimer.stop()
				return []
			}
			metaSearchTimer.pause()

			// 弱い論理積を取る
			intersectionTimer.start()
			if (metaIndexList == null) {
				metaIndexList = newList
				newList.each {baseMap.get(it.offset, []) << it} //検索文字の最初の2文字を基準にする
			} else {
				def mapA = [:]
				def mapB = [:]
				newList.each {metaIndex -> mapA.get(metaIndex.offset, []) << metaIndex}
				metaIndexList.each {metaIndex ->
						if (mapA.containsKey(metaIndex.offset)) mapB.get(metaIndex.offset, []) << metaIndex
				}
				metaIndexList = []
				newList = []
				mapB.each {mapKey, value ->
					newList.addAll(mapA.get(mapKey))
					metaIndexList.addAll(value)
				}
			}
			intersectionTimer.pause()

			// 文字の出現位置をチェック
			filterTimer.start()
			def map = [:]
			newList.each { map.get(it.offset, []) << it }

			def resultMap = [:]
			map.keySet().each {offsetKey ->
					def tmpList = map.get(offsetKey)
					def baseList = baseMap.get(offsetKey)
					// baseMap.put(offsetKey, []) -- バグ修正用
					baseList.each {base ->
						def flag = 	tmpList.any {
										fragment.word == it.word && (it.wordOffset - base.wordOffset) == fragment.wordOffset
									}
						if (flag) resultMap.get(base, base)
						// if (flag) baseMap.get(offsetKey, base) -- バグ修正用
					}
			}
			filterTimer.pause()
			metaIndexList = resultMap.keySet()
			println "tmp count: ${metaIndexList.size()}"
			if (metaIndexList != null && metaIndexList.empty) {
				metaSearchTimer.stop()
				intersectionTimer.stop()
				filterTimer.stop()
				return []
			}
		}
		metaSearchTimer.stop()
		intersectionTimer.stop()
		filterTimer.stop()
		def resultList = metaIndexList.collect {getIndex(it.offset, it.length)}
		resultList.sort {l, r-> l.word <=> r.word}
	}
	
	def append(Map map, MetaIndex idx) {
		if (map.containsKey(idx.offset)) {
			map.get(idx.offset) << idx
		} else {
			map.put(idx.offset, [idx])
		}
	}
	
	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++
		}
		return list
	}
	
	def getIndex(int offset, int length) {
		return new Index(read(file, offset, length), 0, length)
	}
	
	def getDefinition(index) {
		return new String(read(dictFile, index.offset, index.length), "UTF-8")
	}
}

Timer.groovy

class Timer {
	def name
	def total = 0
	def time = new Date()
	def Timer(n) {name = n}

	def start() {
		time = new Date()
	}
	def pause() {
		total += (new Date().getTime() - time.getTime())
		time = null
	}
	def stop() {
		if (time != null) total += (new Date().getTime() - time.getTime())
		println "TIME[${name}]:${total}" 
	}
}

結果

ああああああああああ

ロジック	今回	前回
meta search(日英)	287	490
weak intersection(日英)	113	108
filter(日英)	81	106
meta search(日タイ)	213	577
weak intersection(日タイ)	12	91
filter(日タイ)	46	290
All	891	2185

い

ロジック	今回	前回
meta search(日英)	217	301
weak intersection(日英)	28	52
filter(日英)	90	104
meta search(日タイ)	63	93
weak intersection(日タイ)	1	0
filter(日タイ)	4	24
All	697	882

おた

ロジック	今回	前回
meta search(日英)	214	86
weak intersection(日英)	28	51
filter(日英)	83	13
meta search(日タイ)	57	101
weak intersection(日タイ)	2	0
filter(日タイ)	10	121
All	661	871

あいし

ロジック	今回	前回
meta search(日英)	273	351
weak intersection(日英)	73	143
filter(日英)	93	78
meta search(日タイ)	658	761
weak intersection(日タイ)	35	25
filter(日タイ)	104	73
All	1730	2079

あいして

ロジック	今回	前回
meta search(日英)	271	444
weak intersection(日英)	72	104
filter(日英)	96	52
meta search(日タイ)	1404	1213
weak intersection(日タイ)	105	159
filter(日タイ)	155	112
All	2392	2373

あいしてるとくりかえしていう

ロジック	今回	前回
meta search(日英)	272	855
weak intersection(日英)	72	117
filter(日英)	91	51
meta search(日タイ)	3632	3620
weak intersection(日タイ)	214	247
filter(日タイ)	171	76
All	4731	5119

バグ

書いているうちに気づいたが、多分今のソースだと、文字の出現位置チェックの部分にバグがある。
基準となる検索片に対応する部位が複数あった場合、それ以後の検索片に対応する部位はどれか1つでも出現位置があっていればひっかかってしまうｓ。
例えば「あいたた」という検索キーで検索した場合、「あいたら、あたた」もひっかかると思う（テストデータ用意するのが面倒なので試してない）。
条件が変わるのもなんなので、高速化が終わったら修正する。