如何优化此嵌套for循环?
如何优化此嵌套for循环?如何优化此嵌套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;
}
怎么样的东西升这个吗?
//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)上运行速度非常快。
我使用了NSSet
以确保您一次只添加1个单词。如果NSSet
尚未包含它,它将添加一个单词。然后它会检查新单词是否是已添加的任何单词的子字符串,如果为真,则不会添加新单词。它也是不区分大小写的。
我写的是重构你的代码。这可能没有那么快,但如果你想要搜索已经添加到树中的单词时,你确实需要一个树数据结构。
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
当你说“make it work”时,你能解释一下它有什么问题吗?它适用于我,处理170,000个单词大约需要4分钟的时间......并且,不要担心,这不是作业。 – Jasarien 2010-08-06 20:13:03
@Jasarien:当然不用担心,试试这个。 – 2010-08-06 20:27:31
这比我的版本快了50倍,做得很好;) – Jasarien 2010-08-06 20:37:57
@Jasarien你可能想做的不仅仅是'hasPrefix:',因为'hasPrefix:'是区分大小写的...... – 2010-08-06 20:54:02
它很好用。整个文件由小写字母组成,所以它不是问题。 – Jasarien 2010-08-06 23:47:10