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

最有效的方法可能是使用 aNSSet来存储要与字符串进行比较的所有单词。

然后您只需检查您的单词是否属于如下集合

BOOL englishWord = [theEnglishSet containsObject:yourString];

这将需要固定的时间来执行。

于 2013-01-11T21:34:14.483 回答
1

有了这样的要求，标准方法/类将不适合您的需求。您应该学习/阅读一些有关算法的书籍以正确实现这一点。看起来您应该使用哈希表，但是，同样，对于 200K 值 NSDictionary（它是哈希表）可能无法足够快地工作。

于 2013-01-11T21:34:36.620 回答
0

如果您不介意自己滚动，您可以从字典中构建一个trie（又名前缀树）并使用它来查找单词。我敢打赌，使用 c 字符串和结构的相当好的实现会比 NSDictionary 更快、更节省内存。

于 2013-01-14T15:17:44.693 回答