Wie kann ich dies für Schleife verschachtelt optimieren heraus?

Question

Wie kann ich dies für Schleife verschachtelt optimieren aus?

Das Programm sollte von der Wort Textdatei erstellt durch jedes Wort in dem Array gehen, und wenn es mehr als 8 Zeichen ist, fügen Sie es den goodWords Array. Aber der Nachteil ist, dass ich nur das Stammwort in der Reihe Goodwords sein will, zum Beispiel:

Wenn greet dem Array hinzugefügt wird, will ich nicht grüßt oder Grüße oder Abholer, etc.

    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

Wie wäre es so etwas wie das?

//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];

Diese läuft sehr schnell auf meinem Rechner (2,8 GHz MBP).

Answer 2

Trie scheint für Ihren Zweck geeignet. Es ist wie ein Hash, und ist nützlich, zu erkennen, ob eine gegebene Zeichenkette ein Präfix einer bereits gesehen Zeichenfolge.

Answer 3

benutzen ich eine NSSet, um sicherzustellen, dass Sie nur 1 Kopie eines Wortes zu einem Zeitpunkt hinzugefügt haben. Es wird ein Wort hinzufügen, wenn der NSSet nicht bereits enthält. Es prüft dann, ob das neue Wort ein Teilwort für jedes Wort, das bereits hinzugefügt wurde, wenn sie wahr ist, dann wird es nicht das neue Wort hinzufügen. Es ist Groß- und Kleinschreibung als auch.

Was ich geschrieben habe ist ein Refactoring des Codes. Es ist wahrscheinlich nicht so viel schneller, aber Sie wirklich eine Baumdatenstruktur tun wollen, wenn Sie es viel schneller machen wollen, wenn Sie nach Worten suchen, die bereits zu Ihrem Baum hinzugefügt wurden.

Hier finden Sie aktuelle RedBlack Bäume oder B-Trees .

words.txt

objective
objectively
cappucin
cappucino
cappucine
programme
programmer
programmatic
programmatically

Source Code

- (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];
}

Ausgang:

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