iPhone SDKレシピ2：NSURLConnectionを使ってファイルをダウンロードする

CocoaフレームワークにはNSURLDownloadという便利なクラスが用意されているが、iPhone SDK (UIKit) には入っていない。そこで、NSURLConnectionを使ってファイルをダウンロードするための簡単なラッパークラスURLDownloadを用意し、それを用いてファイルをダウンロードする。
Basic認証が必要なURLからのダウンロードにはまだ対応していないが、 didReceiveAuthenticationChallenge のところでUIAlertViewでも出して、いろいろやってやればできるはず。

使用例

このクラスを使うには、 URLDownloadDelegagte プロトコルを実装したクラスを delegate として URLDownload に渡してやればよい。

URLDownload *downloader;
//  ダウンロード開始
- (IBAction) download:(id)sender {
	[urlField resignFirstResponder];
	NSString *tmpPath = [NSHomeDirectory() stringByAppendingPathComponent:@"tmp"];
	NSURLRequest *req = [NSURLRequest requestWithURL:[NSURL URLWithString:[urlField text]]];

	// ここでダウンロード開始
	downloader = [[URLDownload alloc] initWithRequest:req directory:tmpPath delegate:self];
}

///////////////////////////////////////////////////////////////////////
//URLDownloadDelegate implements
// ダウンロード完了
- (void)downloadDidFinish:(URLDownload *)download {
	LOG(download.filePath);
	[self releaseDownloader];
}

// ダウンロードをキャンセルした際に呼ばれる
- (void)download:(URLDownload *)download didCancelBecauseOf:(NSException *)exception {
	UIAlertView *alert = [[[UIAlertView alloc] initWithTitle:@"" message:[exception reason] delegate:self cancelButtonTitle:nil otherButtonTitles:@"OK",nil] autorelease];
	[alert show];
	[self releaseDownloader];
}

// ダウンロードに失敗した際に呼ばれる
- (void)download:(URLDownload *)download didFailWithError:(NSError *)error {
	UIAlertView *alert = [[[UIAlertView alloc] initWithTitle:@"" message:[error localizedDescription] delegate:self cancelButtonTitle:nil otherButtonTitles:@"OK",nil] autorelease];
	[alert show];
	[self releaseDownloader];
}

// ダウンロード進行中に呼ばれる
- (void)download:(URLDownload *)download didReceiveDataOfLength:(NSUInteger)length {
	// プログレスバーの表示でもやる
}

URLDownload.h

#import <Foundation/Foundation.h>

@class URLDownload;

@protocol URLDownloadDeleagte
- (void)downloadDidFinish:(URLDownload *)download;
- (void)download:(URLDownload *)download didCancelBecauseOf:(NSException *)exception;
- (void)download:(URLDownload *)download didFailWithError:(NSError *)error;
@optional
- (void)download:(URLDownload *)download didReceiveDataOfLength:(NSUInteger)length;
- (void)download:(URLDownload *)download didReceiveResponse:(NSURLResponse *)response;

@end

@interface URLDownload : NSObject {
	id <URLDownloadDeleagte, NSObject> delegate;
	NSString *directoryPath;
	NSString *filePath;
	NSURLRequest *request;
	NSFileHandle *file;
	NSURLConnection *con;
}
@property(readonly) NSString *filePath;

- (id)initWithRequest:(NSURLRequest *)req directory:(NSString *)dir delegate:(id<URLDownloadDeleagte, NSObject>)dg;
- (void)dealloc;
- (void)cancel;

// NSURLConnection delegate
- (void)connection:(NSURLConnection *)connection didReceiveResponse:(NSURLResponse *)response;
- (void)connection:(NSURLConnection *)connection didFailWithError:(NSError *)error;
- (void)connection:(NSURLConnection *)connection didReceiveData:(NSData *)data;
- (void)connectionDidFinishLoading:(NSURLConnection *)connection;
//- (void)connection:(NSURLConnection *)connection didReceiveAuthenticationChallenge:(NSURLAuthenticationChallenge *)challenge;
//- (void)connection:(NSURLConnection *)connection didCancelAuthenticationChallenge:(NSURLAuthenticationChallenge *)challenge;
//- (NSCachedURLResponse *)connection:(NSURLConnection *)connection willCacheResponse:(NSCachedURLResponse *)cachedResponse;
//- (NSURLRequest *)connection:(NSURLConnection *)connection willSendRequest:(NSURLRequest *)request redirectResponse:(NSURLResponse *)redirectResponse;

@end

URLDownload.m

#import "URLDownload.h"


@implementation URLDownload
@synthesize filePath;

- (id)initWithRequest:(NSURLRequest *)req directory:(NSString *)dir delegate:(id<URLDownloadDeleagte, NSObject>)dg {
	if (self = [super init]) {
		request = [req retain];
		directoryPath = [dir retain];
		delegate = [dg retain];
		
		con = [[NSURLConnection alloc] initWithRequest:request delegate:self];
	}
	return self;
}

- (void)dealloc {
	[request release];
	[directoryPath release];
	[filePath release];
	[file release];
	[delegate release];
	[con release];
	[super dealloc];
}

- (void)cancel {
	[con cancel];
}

// NSURLConnection delegate
- (void)connection:(NSURLConnection *)connection didReceiveResponse:(NSURLResponse *)response {
	filePath = [[response suggestedFilename] retain];
	if ([delegate respondsToSelector:@selector(download: didReceiveResponse:)])
		[delegate download:self didReceiveResponse:response];
}
- (void)connection:(NSURLConnection *)connection didFailWithError:(NSError *)error {
	LOG([error localizedDescription]);
	if ([delegate respondsToSelector:@selector(download: didFailWithError:)])
		[delegate download:self didFailWithError:error];
}

- (void)connection:(NSURLConnection *)connection didReceiveData:(NSData *)data {
	@try {
		if (file == nil) {
			NSFileManager *fm = [NSFileManager defaultManager];
			BOOL isDir;
			if (![fm fileExistsAtPath:directoryPath isDirectory:&isDir]) {
				NSError *error;
				if (![fm createDirectoryAtPath:directoryPath withIntermediateDirectories:YES attributes:nil error:&error]) {
					LOG([error localizedDescription]);
					LOG([error localizedFailureReason]);
					LOG([error localizedRecoverySuggestion]);
					[NSException raise:@"Exception" format:[error localizedDescription]];
				}
			} else if (!isDir) {
				[NSException raise:@"Exception" format:@"Failed to create directory at %@, because there is a file already.", directoryPath];
			}
			NSString *tmpFilePath = [[directoryPath stringByAppendingPathComponent:filePath] stringByStandardizingPath];
			int suffix = 0;
			while ([fm fileExistsAtPath:tmpFilePath]) {
				suffix++;
				tmpFilePath = [[directoryPath stringByAppendingPathComponent:[NSString stringWithFormat:@"%@%d", filePath, suffix]] stringByStandardizingPath];
			}
			[fm createFileAtPath:tmpFilePath contents:[NSData data] attributes:nil];
			[filePath release];
			filePath = [tmpFilePath retain];
			
			file = [[NSFileHandle fileHandleForWritingAtPath:filePath] retain];
		}
		[file writeData:data];
		if ([delegate respondsToSelector:@selector(download: didReceiveDataOfLength:)])
			[delegate download:self didReceiveDataOfLength:[data length]];
	}
	@catch (NSException * e) {
		LOG([e reason]);
		[connection cancel];
		[delegate download:self didCancelBecauseOf:e];
	}
}

- (void)connectionDidFinishLoading:(NSURLConnection *)connection {
	[delegate downloadDidFinish:self];
}
/*

 - (void)connection:(NSURLConnection *)connection didReceiveAuthenticationChallenge:(NSURLAuthenticationChallenge *)challenge;
 - (void)connection:(NSURLConnection *)connection didCancelAuthenticationChallenge:(NSURLAuthenticationChallenge *)challenge;
 - (NSURLRequest *)connection:(NSURLConnection *)connection willSendRequest:(NSURLRequest *)request redirectResponse:(NSURLResponse *)redirectResponse;
 - (NSCachedURLResponse *)connection:(NSURLConnection *)connection willCacheResponse:(NSCachedURLResponse *)cachedResponse;
*/
 
@end

iPhone SDKレシピ1：UITableViewで縞模様（ストライプ）

UITableViewで行を縞模様にするためには、UITableViewCellの背景を全てクリアしてから、backgroundViewのbackgroundColorを変更する。

ソースはこんな感じ。

UITableViewDelgate#tableView: cellForRowAtIndexPath:

- (UITableViewCell *)tableView:(UITableView *)tableView cellForRowAtIndexPath:(NSIndexPath *)indexPath {
	NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
    static NSString *CellIdentifier = @"IndexCell";
  
    UITableViewCell *cell = [tableView dequeueReusableCellWithIdentifier:CellIdentifier];
    if (cell == nil) {
        cell = [[[UITableViewCell alloc] initWithFrame:CGRectZero reuseIdentifier:CellIdentifier] autorelease];
		UIView *bgView = [[UILabel alloc] initWithFrame:CGRectZero];
		cell.backgroundView = bgView;
		[bgView release];
		for (UIView *view in cell.contentView.subviews) {
			view.backgroundColor = [UIColor clearColor];
		}
    }
    
    // Set up the cell...
	NSInteger row = [indexPath row];
	
	[cell setText:@"Test"];
	
	if (row % 2 == 1) {
		cell.backgroundView.backgroundColor = [[[UIColor alloc] initWithRed:0.3 green:0.3 blue:0.3 alpha:0.1] autorelease];
	} else {
		cell.backgroundView.backgroundColor = [UIColor whiteColor];
	}
	[cell retain];
	[pool release];

    return [cell autorelease];
}

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

対策５：メタインデックス再び

対策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
	}

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

対策３：メタインデックス形式の変更

現在、1つの検索片でメタインデックスを検索するごとに約40回＋結果数回メタインデックスファイルからの読み込みを行っている。
この読み込み回数を減らすため、メタインデックスの形式を変更する。
現在のメタインデックスは[見出し語（2文字）＋辞書インデックスのoffset＋辞書インデックスのlength＋見出し語の出現位置]という形式になっており、メタインデックスファイル内にはこのメタインデックスが連続して記録されている。同一の見出し語でも他の部分が違うメタインデックスは別物として、それぞれメタインデックス内に記録されている。

検索片によるメタインデックス検索で対象になるのはこのうちの見出し語の部分だが、同一見出し語を持つメタインデックスが複数あるため、メタインデックスファイル内で対象となるメタインデックスが含まれている開始位置と終了位置を探すために2回のバイナリサーチが必要になっている。

そこで、同一見出し語を持つメタインデックスをまとめて

メタインデックス(header)

[見出し語＋メタインデックス(body)のoffset＋メタインデックス(body)のlength]

メタインデックス(body)

[同一見出し語を持つメタインデックスの[辞書インデックスのoffset＋辞書インデックスのlength＋見出し語の出現位置]を連続して接続]

に分け、それぞれメタインデックス(header)ファイルとメタインデックス(body)ファイルに記録する。

これによって、メタインデックス(header)ファイルには同一見出し語を持つメタインデックス(header)は必ず1つだけ持つようにすることができ、メタインデックス検索内のバイナリサーチをメタインデックス(header)の位置を探す1回だけに減らすことができる。

結果

正直、期待していたほど早くならなかった・・・。

ソース

MetaDictionary.groovy

class MetaDictionary extends BaseDictionary {
	def headerFile = null
	def bodyFile = null
	int count = 0
	int readCount = 0
	def MetaDictionary(fileName) {
		headerFile = new File(fileName + ".mh")
		bodyFile = new File(fileName + ".mb")
	}

	def search(key) {
		readCount = 0
		assert (key.length() <= MetaIndex.KEY_CHAR_LENGTH)
		def result = binarySearch(key, 0, ((int)(headerFile.length() / MetaIndex.HEADER_LENGTH) -1))
/*		println "read count: ${readCount}"*/
		return result
	}

	def getIndexHeader(int i) {
		readCount++
		return new MetaIndexHeader(read(headerFile, i*MetaIndex.HEADER_LENGTH, MetaIndex.HEADER_LENGTH))
	}
	
	def loadIndex(header) {
		byte[] buf = read(bodyFile, header.offset, header.length)
		int indexCount = header.length / MetaIndex.BODY_LENGTH
		def indexes = (0..<indexCount).collect {
			new MetaIndex(header, buf, it * MetaIndex.BODY_LENGTH)
		}
		return indexes
	}
	def binarySearch(key, int start, int end) {
		if (end < 0) return []
		int i = (int)Math.floor((start+end)/2)
		def idx = getIndexHeader(i)
		def c = idx.compareTo(key)
/*		println "start:${start}, end:${end}, i:${i}, c:${c}, idx:${idx}, key:${key}, key:${key.getBytes()}"*/
		if (c == 0) {
			return loadIndex(idx)
		} else if (start == end) {
			return []
		} else if (c > 0) {
			return binarySearch(key, start, i)
		} else {
			if ((end-start)==1) i = end
			return binarySearch(key, i, end)
		}
	}
}

MetaIndexHeader.groovy

class MetaIndexHeader extends BaseIndex implements Comparable {
	public static final int KEY_LENGTH = 12
	public static final int KEY_CHAR_LENGTH = 2
	public static final int HEADER_LENGTH = 20
	
	def MetaIndexHeader() {}
	def MetaIndexHeader(String w, int o=0, int l=0) {
		word = w
		offset = o
		length = l
	}
	def MetaIndexHeader(byte[] buf) {
		word = new String(buf, 0, KEY_LENGTH, "UTF-8").trim()	// 余計なバイト(0)をtrimで削除
		offset = byte2int(buf, KEY_LENGTH, 4)
		length = byte2int(buf, KEY_LENGTH+4, 4)
	}
	
	int compareTo(MetaIndex target) {
		if (word != target.word) return word.compareTo(target.word)
		if (offset != target.offset) return offset <=> target.offset
		return 0
	}
	int compareTo(Object target) {
		if (target instanceof MetaIndexHeader) return compareTo((MetaIndexHeader)target)
		if (target instanceof String) return word.compareTo(target)
		return -1
	}
	
	byte[] toBytes() {
		ByteArrayOutputStream byteStream = new ByteArrayOutputStream()
		dumpWord(byteStream)
		dumpOffsetLength(byteStream)
		return byteStream.toByteArray()
	}
	def dumpWord(byteStream) {
		byte[] w = word.getBytes("UTF-8")
		byteStream.write(w, 0, w.length)
		(w.length..<KEY_LENGTH).each {byteStream.write(0)}
	}
	def dumpOffsetLength(byteStream) {
		byte[] o = int2byte(offset)
		byte[] l = int2byte(length)
		byteStream.write(o, 0, o.length)
		byteStream.write(l, 0, l.length)
	}
}

MetaIndex.groovy

class MetaIndex extends MetaIndexHeader implements Comparable {
	public static final int LENGTH = 24
	public static final int BODY_LENGTH = 12
	
	int wordOffset = 0
	def MetaIndex(String w, int o=0, int l=0, int wo=0) {
		word = w
		offset = o
		length = l
		wordOffset = wo
	}
	def MetaIndex(MetaIndexHeader header, byte[] buf, int o) {
		word = header.word
		offset = byte2int(buf, o, 4)
		length = byte2int(buf, o+4, 4)
		wordOffset = byte2int(buf, o+8, 4)
	}
	def MetaIndex(byte[] buf) {
		parse(buf, 0)
	}
	def MetaIndex(byte[] buf, int o) {
		parse(buf, o)
	}
	def parse(byte[] buf, int o) {
		word = new String(buf, o, KEY_LENGTH, "UTF-8").trim()	// 余計なバイト(0)をtrimで削除
		offset = byte2int(buf, o+KEY_LENGTH, 4)
		length = byte2int(buf, o+KEY_LENGTH+4, 4)
		wordOffset = byte2int(buf, o+KEY_LENGTH+8, 4)
	}
	
	int compareTo(MetaIndex target) {
		if (word != target.word) return word.compareTo(target.word)
		if (offset != target.offset) return offset <=> target.offset
		if (wordOffset != target.wordOffset) return wordOffset <=> target.wordOffset
		return 0
	}
	int compareTo(Object target) {
		if (target instanceof MetaIndex) return compareTo((MetaIndex)target)
		if (target instanceof String) return word.compareTo(target)
		return -1
	}
	
	byte[] toBytes() {
		ByteArrayOutputStream byteStream = new ByteArrayOutputStream(LENGTH)
		dumpWord(byteStream)
		dumpOffsetLength(byteStream)
		dumpWordOffset(byteStream)
		return byteStream.toByteArray()
	}
	byte[] toBodyBytes() {
		ByteArrayOutputStream byteStream = new ByteArrayOutputStream(LENGTH)
		dumpOffsetLength(byteStream)
		dumpWordOffset(byteStream)
		return byteStream.toByteArray()
	}
	def dumpWordOffset(byteStream) {
		byte[] wo = int2byte(wordOffset)
		byteStream.write(wo, 0, wo.length)
	}
	String toString() {
		return "{word: ${word},\toffset:${offset},\tlength:${length},\twordOffset:${wordOffset}}"
	}
}

Indexer.groovyもね。

fileName = args[0]
workDir = new File("work")
deleteTmpFile()
workDir.mkdirs()

def indexes = loadCompleteIndex()

List metaList = []
int i=0
for (idx in indexes) {
	metaList.addAll(idx.toMetaIndexList())
	
	i++
	if (i%5000 == 0) {
		makeTmpFile(metaList)
		metaList = []
		println ("parsing:" + (i*100/indexes.size()) + "%")
	}
}
makeTmpFile(metaList)
makeMetaFile()

def makeMetaFile() {
	File headerFile = new File(fileName + ".mh")
	File bodyFile = new File(fileName + ".mb")
	headerFile.delete()
	bodyFile.delete()
	headerFile.createNewFile()
	bodyFile.createNewFile()
	def headerStream = new BufferedOutputStream(new FileOutputStream(headerFile))
	def bodyStream = new BufferedOutputStream(new FileOutputStream(bodyFile))
	def offset = 0
	listTmpFiles().each {f ->
			println ("writing: " + hex2str(f.name) + ":" + f.length() + ":" + (f.length() / MetaIndex.LENGTH))
			def buf = f.readBytes()
			def map = [:]
			def i = 0
			while ((i*MetaIndex.LENGTH) < buf.length) {
				def metaIndex = new MetaIndex(buf, i*MetaIndex.LENGTH)
				map.get(metaIndex.word, []) << metaIndex
				i++
			}
			map.keySet().sort().each {
				def header = new MetaIndexHeader(it)
				header.offset = offset
				
				map.get(it).sort().each {
					def bodyBuf = it.toBodyBytes()
					bodyStream.write(bodyBuf)
					offset += bodyBuf.length
				}
				header.length = offset - header.offset
				headerStream.write(header.toBytes())
			}
		}
	headerStream.close()
	bodyStream.close()
}

def listTmpFiles() {
	def list = workDir.listFiles().toList()
	return list.sort {l,r ->
			return hex2str(l.name).compareTo(hex2str(r.name))
		}
}

def makeTmpFile(metaList) {
	metaList.sort()
	def prev = str2Hex("a")
	def tmpFile = new BufferedOutputStream(new FileOutputStream(new File(workDir, prev), true))
	for (m in metaList) {
		def first = str2Hex(m.word.substring(0,1))
		if (prev != first) {
			prev = first
			tmpFile.close()
			tmpFile = new BufferedOutputStream(new FileOutputStream(new File(workDir, prev), true))
		}
		tmpFile.write(m.toBytes())
	}
	tmpFile.close()
}

def str2Hex(String val) {
	byte[]  bytes = val.getBytes()
	def result = ""
	bytes.each {
		result += Integer.toHexString(it & 0xff)
	}
	return result
}
def hex2str(val) {
	byte[] buf = new byte[(val.length() / 2)]
	int i=0
	while (val.length() > 0) {
		buf[i] = Byte.parseByte(val.substring(0, 1), 16) * 16 + Byte.parseByte(val.substring(1, 2), 16)
		val = val.substring(2)
		i++
	}
	return new String(buf, "UTF-8")
}

def deleteTmpFile() {
	workDir.listFiles().each {
		it.delete()
	}
	workDir.delete()
}

def loadCompleteIndex(indexOffset = 0, indexLength = -1) {
	if (indexOffset < 0) indexOffset = 0
	RandomAccessFile randomFile = new RandomAccessFile(fileName + ".idx", "r")
	if (indexLength == -1) indexLength = randomFile.length()
	def buf = new byte[indexLength]
	randomFile.seek(indexOffset)
	randomFile.read(buf)
	randomFile.close()

	def i=0
	int offset = 0
	int count = 0
	def indexes = new ArrayList();
	while (i<buf.length) {
		if (buf[i] == 0) {
			def idx = new Index(buf, offset, i-offset+9)
			if (idx.word.length() > 0) indexes.add(idx)
			offset = i+9
			i = i+8
			count++
		}
		i++
		if (i%200000 == 0) println ("loading:" + (i*100/(indexLength)) + "%")
	}
	return indexes
}

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

対策４：メタインデックスである程度絞り込んだら、あとはメモリ上で

メタインデックス検索＋弱い論理積＋出現位置チェックで1000件未満まで絞り込めたら、あとは直接辞書インデックス取得し、メモリ上で絞り込んでみた。

変更点はこんな感じ。
Dictionary#searchの最後の部分を

if (metaIndexList != null && metaIndexList.empty) {
	break
} else if (metaIndexList != null && metaIndexList.size() < 1000) {
	def resultList = metaIndexList.collect {getIndex(it.offset, it.length)}
	resultList = resultList.findAll {it.word.indexOf(key) >= 0}
	stopTimer()
	return resultList.sort {l, r-> l.word <=> r.word}
}

としただけ。

また、弱い論理性、出現位置チェックの計測部分が不正確だったのでそこも修正。
Timer.groovy

class Timer {
	def name = ""
	def total = 0
	def time = null
	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}" 
	}
}

結果

だいぶ高速化された。
だけど、どれも最初の検索片についてのメタインデックス検索＋出現位置チェックをしているだけ。
1つの検索片でしかメタインデックス検索をしていないので、弱い論理積はしていない。
ちょっと切ない（´・ω・｀）

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

関連エントリ

StarDictの辞書アプリ - Random Note
辞書アプリの改良 - Random Note
辞書アプリの改良：初期化処理の高速化(1) - Random Note
http://d.hatena.ne.jp/hisaboh/20081022/p1
辞書アプリの改良：コマンド化 - Random Note
辞書アプリの改良：部分一致（１） - Random Note
辞書アプリの改良：部分一致（２） - Random Note
辞書アプリの改良：部分一致（３） - Random Note
http://d.hatena.ne.jp/hisaboh/20081026/p1
辞書アプリの改良：部分一致（５） - Random Note
辞書アプリの改良：複数辞書対応＋α - Random Note
辞書アプリの改良：これから - Random Note

測定

% ./dict.sh ああああああああああ
search: ああああああああああ
TIME[meta search each]:212
TIME[meta search each]:54
TIME[meta search each]:34
TIME[meta search each]:30
TIME[meta search each]:26
TIME[meta search each]:26
TIME[meta search each]:21
TIME[meta search each]:25
TIME[meta search each]:21
TIME[meta search]:490
TIME[weak intersection]:108
TIME[filter]:106
TIME[meta search each]:77
TIME[meta search each]:59
TIME[meta search each]:64
TIME[meta search each]:62
TIME[meta search each]:59
TIME[meta search each]:58
TIME[meta search each]:74
TIME[meta search each]:60
TIME[meta search each]:61
TIME[meta search]:577
TIME[weak intersection]:91
TIME[filter]:290
count:0
TIME[All]:1809

/Users/hisaboh/Downloads/test% ./dict.sh い
search: い
TIME[meta search each]:266
TIME[meta search]:301
TIME[weak intersection]:52
TIME[filter]:104
TIME[meta search each]:93
TIME[meta search]:93
TIME[weak intersection]:0
TIME[filter]:24
count:11
TIME[All]:882

/Users/hisaboh/Downloads/test% ./dict.sh おた
search: おた
TIME[meta search each]:223
TIME[meta search]:259
TIME[weak intersection]:51
TIME[filter]:121
TIME[meta search each]:93
TIME[meta search]:101
TIME[weak intersection]:0
TIME[filter]:13
count:21
TIME[All]:871

/Users/hisaboh/Downloads/test% ./dict.sh あいし
search: あいし
TIME[meta search each]:227
TIME[meta search each]:86
TIME[meta search]:351
TIME[weak intersection]:143
TIME[filter]:78
TIME[meta search each]:274
TIME[meta search each]:485
TIME[meta search]:761
TIME[weak intersection]:25
TIME[filter]:73
count:43
TIME[All]:2079

/Users/hisaboh/Downloads/test% ./dict.sh あいして 
search: あいして
TIME[meta search each]:208
TIME[meta search each]:57
TIME[meta search each]:144
TIME[meta search]:444
TIME[weak intersection]:104
TIME[filter]:52
TIME[meta search each]:221
TIME[meta search each]:403
TIME[meta search each]:588
TIME[meta search]:1213
TIME[weak intersection]:159
TIME[filter]:112
count:12
TIME[All]:2373

/Users/hisaboh/Downloads/test% ./dict.sh あいしてるとくりかえしていう
search: あいしてるとくりかえしていう
TIME[meta search each]:216
TIME[meta search each]:48
TIME[meta search each]:84
TIME[meta search each]:84
TIME[meta search each]:74
TIME[meta search each]:42
TIME[meta search each]:50
TIME[meta search each]:28
TIME[meta search each]:23
TIME[meta search each]:25
TIME[meta search each]:64
TIME[meta search each]:40
TIME[meta search each]:22
TIME[meta search]:855
TIME[weak intersection]:117
TIME[filter]:51
TIME[meta search each]:208
TIME[meta search each]:374
TIME[meta search each]:690
TIME[meta search each]:137
TIME[meta search each]:145
TIME[meta search each]:120
TIME[meta search each]:163
TIME[meta search each]:102
TIME[meta search each]:138
TIME[meta search each]:57
TIME[meta search each]:546
TIME[meta search each]:753
TIME[meta search each]:156
TIME[meta search]:3620
TIME[weak intersection]:247
TIME[filter]:76
count:1
TIME[All]:5119

目標

これらの検索実行時間を全て1秒以内にする。

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

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

辞書アプリの改良：高速化（１） - 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つでも出現位置があっていればひっかかってしまうｓ。
例えば「あいたた」という検索キーで検索した場合、「あいたら、あたた」もひっかかると思う（テストデータ用意するのが面倒なので試してない）。
条件が変わるのもなんなので、高速化が終わったら修正する。