Как я могу оптимизировать этот вложенный цикл?

Question

Как я могу оптимизировать этот вложенный цикл?

Программа должна проходить каждое слово в массиве, созданном из текстового файла слова, а если оно больше 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

Как о чем-то л ike это?

//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,8 ГГц MBP).

Answer 2

A Trie кажется подходящим для вашей цели. Это похоже на хэш и полезно для определения того, является ли данная строка префиксом уже увиденной строки.

Answer 3

Я использовал NSSet, чтобы у вас только одна копия слова, добавленного за раз. Он добавит слово, если NSSet его еще не содержит. Затем он проверяет, является ли новое слово подстрокой для любого слова, которое уже было добавлено, если true, то оно не добавит нового слова. Это не чувствительно к регистру.

То, что я написал, является рефакторингом вашего кода. Вероятно, это не так быстро, но вам действительно нужна структура данных дерева, если вы хотите сделать это намного быстрее, если хотите найти слова, которые уже добавлены в ваше дерево.

Посмотрите на 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