如何优化此嵌套for循环？

Question

如何优化此嵌套for循环？

程序应该检查从单词文本文件创建的数组中的每个单词，如果它大于8个字符，则将其添加到goodWords数组中。但需要注意的是，我只希望词根是goodWords数组中，例如：

如果映入眼帘被添加到阵列中，我不想打招呼或问候或迎宾员等

NSString *string = [NSString stringWithContentsOfFile:@"/Users/james/dev/WordParser/word.txt" encoding:NSUTF8StringEncoding error:NULL]; 
    NSArray *words = [string componentsSeparatedByString:@"\r\n"]; 
    NSMutableArray *goodWords = [NSMutableArray array]; 
    BOOL shouldAddToGoodWords = YES; 

    for (NSString *word in words) 
    { 
     NSLog(@"Word: %@", word); 

     if ([word length] > 8) 
     { 
      NSLog(@"Word is greater than 8"); 

      for (NSString *existingWord in [goodWords reverseObjectEnumerator]) 
      { 
       NSLog(@"Existing Word: %@", existingWord); 
       if ([word rangeOfString:existingWord].location != NSNotFound) 
       { 
        NSLog(@"Not adding..."); 
        shouldAddToGoodWords = NO; 
        break; 
       } 
      } 

      if (shouldAddToGoodWords) 
      { 
       NSLog(@"Adding word: %@", word); 
       [goodWords addObject:word]; 
      } 
     } 

     shouldAddToGoodWords = YES; 
    } 

Answer 1

怎么样的东西升这个吗？

//load the words from wherever 
NSString * allWords = [NSString stringWithContentsOfFile:@"/usr/share/dict/words"]; 
//create a mutable array of the words 
NSMutableArray * words = [[allWords componentsSeparatedByCharactersInSet:[NSCharacterSet newlineCharacterSet]] mutableCopy]; 
//remove any words that are shorter than 8 characters 
[words filterUsingPredicate:[NSPredicate predicateWithFormat:@"length >= 8"]]; 
//sort the words in ascending order 
[words sortUsingSelector:@selector(caseInsensitiveCompare:)]; 

//create a set of indexes (these will be the non-root words) 
NSMutableIndexSet * badIndexes = [NSMutableIndexSet indexSet]; 
//remember our current root word 
NSString * currentRoot = nil; 
NSUInteger count = [words count]; 
//loop through the words 
for (NSUInteger i = 0; i < count; ++i) { 
    NSString * word = [words objectAtIndex:i]; 
    if (currentRoot == nil) { 
     //base case 
     currentRoot = word; 
    } else if ([word hasPrefix:currentRoot]) { 
     //word is a non-root word. remember this index to remove it later 
     [badIndexes addIndex:i]; 
    } else { 
     //no match. this word is our new root 
     currentRoot = word; 
    } 
} 
//remove the non-root words 
[words removeObjectsAtIndexes:badIndexes]; 
NSLog(@"%@", words); 
[words release]; 

这在我的机器（2.8GHz MBP）上运行速度非常快。

Answer 2

A Trie似乎适合您的用途。它就像一个散列，对于检测给定的字符串是否是已经看过的字符串的前缀很有用。

Answer 3

我使用了NSSet以确保您一次只添加1个单词。如果NSSet尚未包含它，它将添加一个单词。然后它会检查新单词是否是已添加的任何单词的子字符串，如果为真，则不会添加新单词。它也是不区分大小写的。

我写的是重构你的代码。这可能没有那么快，但如果你想要搜索已经添加到树中的单词时，你确实需要一个树数据结构。

看看RedBlack Trees或B-Trees。

Words.txt

objective 
objectively 
cappucin 
cappucino 
cappucine 
programme 
programmer 
programmatic 
programmatically 

源代码

- (void)addRootWords { 

    NSString  *textFile = [[NSBundle mainBundle] pathForResource:@"words" ofType:@"txt"]; 
    NSString  *string = [NSString stringWithContentsOfFile:textFile encoding:NSUTF8StringEncoding error:NULL]; 
    NSArray   *wordFile = [string componentsSeparatedByString:@"\n"]; 
    NSMutableSet *goodWords = [[NSMutableSet alloc] init]; 

    for (NSString *newWord in wordFile) 
    { 
     NSLog(@"Word: %@", newWord); 
     if ([newWord length] > 8) 
     { 
      NSLog(@"Word '%@' contains 8 or more characters", newWord); 
      BOOL shouldAddWord = NO; 
      if ([goodWords containsObject:newWord] == NO) { 
       shouldAddWord = YES; 
      } 
      for (NSString *existingWord in goodWords) 
      { 
       NSRange textRange = [[newWord lowercaseString] rangeOfString:[existingWord lowercaseString]]; 
       if(textRange.location != NSNotFound) { 
        // newWord contains the a substring of existingWord 
        shouldAddWord = NO; 
        break; 
       } 
       NSLog(@"(word:%@) does not contain (substring:%@)", newWord, existingWord); 
       shouldAddWord = YES; 
      } 
      if (shouldAddWord) { 
       NSLog(@"Adding word: %@", newWord); 
       [goodWords addObject:newWord]; 
      } 
     } 
    } 

    NSLog(@"***Added words***"); 
    int count = 1; 
    for (NSString *word in goodWords) { 
     NSLog(@"%d: %@", count, word); 
     count++; 
    } 

    [goodWords release]; 
} 

输出：

***Added words*** 
1: cappucino 
2: programme 
3: objective 
4: programmatic 
5: cappucine