0

NSStringを他の約200,000個の文字列と最短時間で照合する最も効率的な方法を探しています。基本的に、入力した単語が英語に含まれているかどうかを時々チェックする必要があります。

私がこれを行うことができる方法は何ですか？ハッシュテーブルについて聞いたことがありますが、それが最善の方法ですか？

これが私が決めたコードです：

編集：メモリへの辞書初期化のベンチマーク： 

NSDate *start = [NSDate date];

NSLog(@"initWords");

//temporary 
NSString *_filePath = [[NSBundle mainBundle] pathForResource:kFILE_NAME_FOR_DICTIONARY ofType:@"txt"];

NSLog(@"%@",_filePath);

NSString *_fileContents = [[NSString alloc] init];
NSData *_binary = [NSData dataWithContentsOfFile:_filePath];  

if (_binary) {  
    _fileContents = [[NSString alloc] initWithData:_binary encoding:NSUTF8StringEncoding];
}  else {

    NSLog(@"file parse error: did you forget to add the file? Please add file to:\n\n\n\n%@\n\n\n\n",[[NSBundle mainBundle] resourcePath]);
}

NSArray *_wordList = [_fileContents componentsSeparatedByString:kNEW_LINE_CHAR];

englishDictionary = [[NSMutableSet alloc] init];
[englishDictionary addObjectsFromArray:_wordList];

NSLog(@"Word count:\t%d",englishDictionary.count);
NSLog(@"Time to init dictionary:\t%f",[start timeIntervalSinceNow]*-1.);

iphone 5：1.089725（秒）

ipad 1：3.082753

iphone 4：3.582853

ベンチマーク（単語が辞書にあるかどうかをテストする時間）：

-(BOOL)checkWord:(NSString *)word{

    NSDate *start = [NSDate date];

    BOOL yesNoMaybeSo = [englishDictionary containsObject:word];

    NSLog(@"Time to check word:\t%f",[start timeIntervalSinceNow]*-1.);
    return yesNoMaybeSo;

}

iphone 5：0.000021（秒）

ipad 1：0.000037

iphone 4：0.000043

4

3 に答える 3

2

最も効率的な方法は、おそらく、を使用してNSSet、文字列と比較するすべての単語を格納することです。

次に、次のように単語がセットに属しているかどうかを確認するだけです。

BOOL englishWord = [theEnglishSet containsObject:yourString];

これは、実行するのに一定の時間がかかります。

于 2013-01-11T21:34:14.483 に答える
1

このような要件では、標準のメソッド/クラスはニーズに適合しません。これを正しく実装するには、アルゴリズムに関する本をいくつか学ぶ/読む必要があります。ハッシュテーブルを使用する必要があるように見えますが、200Kの値では、NSDictionary（ハッシュテーブル）はおそらく十分な速度で動作しません。

于 2013-01-11T21:34:36.620 に答える
0

自分でローリングしてもかまわない場合は、辞書からトライ（別名プレフィックスツリー）を作成し、それを使用して単語を検索できます。c文字列と構造体を使用した適度に優れた実装は、NSDictionaryよりも高速でメモリ効率が高いと思います。

于 2013-01-14T15:17:44.693 に答える