Como posso otimizar isso aninhado para o loop?
-
26-09-2019 - |
Pergunta
Como posso otimizar isso aninhado para o loop?
O programa deve passar por cada palavra na matriz criada a partir do arquivo de texto do Word e, se for superior a 8 caracteres, adicione -a ao goodWords
variedade. Mas a ressalva é que eu só quero que a palavra raiz esteja na matriz GoodWords, por exemplo:
Se a saudação for adicionada à matriz, não quero cumprimentos, cumprimentos ou saudações, 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;
}
Solução
Que tal algo como isso?
//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];
Isso funciona muito rapidamente na minha máquina (MBP de 2,8 GHz).
Outras dicas
UMA Trie parece adequado para o seu propósito. É como um hash e é útil para detectar se uma determinada string for um prefixo de uma string já vista.
Eu usei um NSSet
Para garantir que você tenha apenas 1 cópia de uma palavra adicionada por vez. Vai adicionar uma palavra se o NSSet
ainda não o contém. Em seguida, ele verifica se a nova palavra é uma substring para qualquer palavra que já tenha sido adicionada, se verdadeira, não adicionará a nova palavra. É insensível ao caso também.
O que escrevi é uma refatoração do seu código. Provavelmente não é muito mais rápido, mas você realmente deseja uma estrutura de dados de árvore, se quiser torná -la muito mais rápida quando deseja procurar palavras que já foram adicionadas à sua árvore.
Dar uma olhada em Árvores Redblack ou B-árvores.
Words.txt
objective
objectively
cappucin
cappucino
cappucine
programme
programmer
programmatic
programmatically
Código fonte
- (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];
}
Resultado:
***Added words***
1: cappucino
2: programme
3: objective
4: programmatic
5: cappucine