Turbo for challenge 2 (20 times faster)


#1

Hello all,

after reviewing the chapters of the book, I wanted to come up with a faster routine for this challenge. This approach is about 20 times faster than before. The key idea is:

As the names and words are in alphabetical order, we know for sure that if a word does not match a name it can be deleted immediately as it will not match anything else. If a word matches a name it can be deleted as well because it’s not relevant if it matches another word.

[code]#import <Foundation/Foundation.h>

int main (int argc, const char * argv[])
{
@autoreleasepool {

	// Like shown in the listing introducing the challenge
	// we get the names and make a nice little array of single names out of it
	NSString *properNames = [NSString stringWithContentsOfFile:@"/usr/share/dict/propernames" encoding:NSUTF8StringEncoding error:NULL];
	NSArray *firstNames =[properNames componentsSeparatedByString:@"\n"];

	// Then we do the same with the words in the dictionary
	NSString *dictionary = [NSString stringWithContentsOfFile:@"/usr/share/dict/words" encoding:NSUTF8StringEncoding error:NULL];
	NSArray *words2 =[dictionary componentsSeparatedByString:@"\n"];

	// We need a mutuable copy of the array as we want to remove
	// words that are not needed to be faster with every loop later on
	NSMutableArray *words = [words2 mutableCopy];

	// The outer will take and first name after the other 
	// and the inner loop will compare the name to every word

	for( NSString *firstName in firstNames ) {
		for ( int i = 0; i < [words count]; i++ ) {
			if ( [firstName caseInsensitiveCompare:[words objectAtIndex:i]] == NSOrderedSame ) {
				NSLog(@"'%@' found in both names and words", firstName );

				// If a word is found we can delete it from the array as we already got it!
				// Also we need to decrease "i" because now there is one item less in the array.
				[words removeObjectAtIndex:i--];

				// If a match is  found, there is no need to continue searching the same word in the rest of the dict
				// Therefor we break out of this loop
				break;
			}
			else {
				// Now this makes the HUGE difference regarding speed. As we know that the words and names are in 
				// alphabetical order we can delete EVERY word not matching name UNTIL we found a match
				// If we found it, the loop will be exited through break, so no further deletion is made until the next loop.
				// So with every new loop there are less and less words to compare to each other.

				// Like above, we need to decrease "i" because now there is one item less in the array.
				[words removeObjectAtIndex:i--];
			}
		}
	}
}
return 0;

}
[/code]

Happy coding

Armin


#2

I like the out of the box thinking, but deleting objects from an array as you scan it is rarely a safe operation; you’re right, it makes sense in this case, but I doubt I’d ever use it in real-world applications.

You might consider a safer option: since both lists are sorted, once you find a match, start the next for loop without resetting i to 0.

Haven’t tested it, but this seems logical:

      int i = 0;
      for( NSString *firstName in firstNames ) {
         for ( /* no init */; i < [words count]; i++ ) {
            if ( [firstName caseInsensitiveCompare:[words objectAtIndex:i]] == NSOrderedSame ) {
               NSLog(@"'%@' found in both names and words", firstName );
            }
        }
      }

#3

It occurs to me that my version won’t work if any of the names aren’t in the word list, and the loop never halts when an item is found. Oops.

So adding the logic to restart the loop wherever it last started adds a bit to the complexity, and the two solutions aren’t quite so differentiated from that standpoint.


#4

Hi,
Im reading this book now :slight_smile:

I liked this approach, and resolved the issue this way:

NSUInteger k = 0;
        for (NSString *i in nomes) {
            for (NSUInteger j = k; j < [palavras count]; j++){            //NSLog(@"Palavras: %@", j);
                if ([i caseInsensitiveCompare:[palavras objectAtIndex:j]] == NSOrderedSame){
                    [result addObject:[palavras objectAtIndex:j]];
          
                    k = j+1;
                    break;
                } 
                
            }
        }

#5

Ah, very clever way to address the logic issue, thanks.

The only minor gripe I have with your code (and this is quite picky) is that typically a variable named i will be a counter variable, not a string. If you’re going to go for a one-character name for a string, I’d go with s.