0

我正在构建一个拼字游戏，但单词字典有一些问题。它包含约 700,000 个单词，大小约为 18 MB。

现在，我正在将整个 dict 加载到一个数组中，这在 iPhone 4 上需要 12 秒。 

wordList = [NSMutableArray arrayWithContentsOfFile: [[self applicationDocumentsDirectory] stringByAppendingString:@"/wordlist.plist"]];

我有两个问题：

  1. 有没有更好的方法来更快地加载单词表和/或减少内存？

  2. 从一组字母中获取所有可能的单词大约需要 12 秒。有没有可能让它更快？这是代码：

    -(NSMutableArray *)getValidWords:(NSString *)letters{
    NSMutableArray *list = [[NSMutableArray alloc] init];

    for (int i = 0, c = [wordList count]; i < c; i++){
    if ([self isWordValid: [wordList objectAtIndex: i] forLetters:letters]){
        [list addObject:[wordList objectAtIndex: i]];
    }
}

return list;

    }

    - (BOOL)isWordValid:(NSString *)word forLetters:(NSString *)ltrs{
    int i, z;
    NSRange range;
    BOOL found;
    static NSMutableString *letters = nil;

    if ([word length] < 2) return NO;

    if(letters == nil) {
        letters = [[NSMutableString alloc] initWithString:ltrs];
    }
    else {
        [letters setString: ltrs];
    }

    found = NO;
    range.length = 1;
    for(i = 0; i < [word length]; i++){
        for(z = 0; z < [letters length]; z++){
            if([word characterAtIndex:i] == [letters characterAtIndex:z]){
                 range.location = z;
                 [letters deleteCharactersInRange: range];
                 found = YES;
                 break;
            }
       }
       if (found == NO){
            return NO;
       }

       found = NO;
  }

  return YES;
}
4

3 回答 3

3

你需要改变一些东西来加快速度。

  1. 使用快速枚举代替旧的 C 样式循环。

  2. 避免大量的方法调用。

  3. 如果可能，请使用 NSPredicate 和/或 Regex。

每当您编写[letters length]一个方法时，都会调用它，而不是数百万次找到它（这是在嵌套循环的第三级内），而是将其存储在一个变量中并使用它。

快速枚举：代替for(int i=0; i<[someArrays count];i++)使用for(id object in someArrays)。

于 2013-01-15T12:23:16.617 回答
2

用这个
[NSThread detachNewThreadSelector:@selector(fetchWords:) toTarget:self withObject:data];

不要在主线程中这样做

如果您需要搜索单词，请使用此代码修改它

NSMutableArray *subpredicates = [NSMutableArray array];

    for(NSString *term in arryOfWordsToBeSearched) {
        NSPredicate *p = [NSPredicate predicateWithFormat:@"self contains[cd] %@",term];
        [subpredicates addObject:p];
        }

     NSPredicate *filter = [NSCompoundPredicate andPredicateWithSubpredicates:subpredicates];
    result = (NSMutableArray*)[arryOfDummyData filteredArrayUsingPredicate: filter];

//结果是一个数组

于 2013-01-15T12:04:15.017 回答
2

NSCharacterSet只是对于初学者，在调用冗长的函数之前，从你创建一个letters并调用这个函数。这是一种更快的检查，可以减少可能性，它应该会缩短您的计算时间。

NSCharacterSet* lettersSet = [NSCharacterSet characterSetWithCharactersInString:letters];

- (BOOL)isWordValid:(NSString*)word forLettersSet:(NSCharacterSet*)lettersSet {
    if ([word length] < 2) return NO;

    NSCharacterSet* wordLetters = [NSCharacterSet characterSetWithCharactersInString:word];

    return [lettersSet isSupersetOfSet:wordLetters];
}

理想情况下，您的单词数据库应该预先计算每个单词的字母数（例如every = {e=2, r=1, v=1, y=1}，您应该只使用这些结构。请注意，字母的顺序并不重要 - 使用这一事实可以大大提高算法的性能。

你也可以尝试创建一个 Core Data 数据库——每个单词都是一个记录，每个字母都有一个数字字段。然后您可以创建一个请求，该请求将非常快地返回可用的单词。（当然，数据库可能会占用更大的空间）。

编辑：现在我已经找到了NSCountedSet类，所以让我们尝试使用它：

-(NSCountedSet*)lettersSetFromString:(NSString*)string {
    NSCountedSet* letters = [NSCountedSet set];
    [string enumerateSubstringsInRange:NSMakeRange(0, self.length)  
                               options:NSStringEnumerationByComposedCharacterSequences   
                            usingBlock:^(NSString *substring, NSRange substringRange, NSRange enclosingRange, BOOL *stop) {
        [letters addObject:substring];
    }];
} 

-(NSMutableArray *)validWordsForLetters:(NSString*)letters {
    NSCountedSet* lettersSet = [self lettersSetFromString:letters];

    NSMutableArray* results = [NSMutableArray array];

    for (NSString* word in wordList) {
        if ([word length] < 2) {
            continue;
        }

        NSCountedSet* wordLettersSet = [self lettersSetFromString:word];

        if ([wordLettersSet isSubsetOfSet:lettersSet]) {
            [results addObject:word];
        }
    }

    return results;
}

预先为每个单词生成计数集将对性能有很大帮助。对于操作系统内存，使用 Core Data 数据库仍然会更快更好。

于 2013-01-15T12:27:26.800 回答