이 중첩 for 루프를 최적화하려면 어떻게해야합니까?

Question

어떻게이 중첩 된 for 루프를 최적화 할 수 있습니까?

프로그램은 단어 텍스트 파일에서 생성 된 배열의 각 단어를 통과해야하며, 8자를 초과하면 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; 
    } 

을 원하지 않는 :하지만주의해야 할 점은, 예를 들어, 난 단지 루트 단어가 goodWords 배열에 있어야 할 것입니다

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

Trie은 용도에 적합합니다. 이것은 해시와 비슷하며 주어진 문자열이 이미 본 문자열의 접두사인지 확인하는 데 유용합니다.

Answer 3

한 번에 한 단어 씩만 추가되도록 NSSet을 사용했습니다. 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