1

このネストされた for ループを最適化するにはどうすればよいですか?

プログラムは、単語テキスト ファイルから作成された配列内の各単語を調べ、それが 8 文字を超える場合はgoodWords配列に追加します。ただし、注意点として、ルート ワードのみを goodWords 配列に含める必要があります。次に例を示します。

配列にgreetが追加された場合、greetsやgreetings、greeterなどは必要ありません。

    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;
    }
4

3 に答える 3

3

このようなものはどうですか？

//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) で非常に高速に実行されます。

于 2010-08-06T20:32:06.350 に答える
2

Trieはあなたの目的に適しているようです。これはハッシュのようなもので、指定された文字列が既に見られた文字列のプレフィックスであるかどうかを検出するのに役立ちます。

于 2010-08-06T18:59:28.130 に答える
1

を使用しNSSetて、一度に追加される単語のコピーが 1 つだけであることを確認しました。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
于 2010-08-06T20:03:49.517 に答える