Challenge #2 - nested For-Loops vs. containsObject method


#1

Howdy ho!

Like most first-timers, I got seriously stumped by Challenge #2 at first (truth be told, I struggled with it for over an hour!). Eventually, I solved it, but the actual execution of the code took AGES - and it brought my mac mini to its knees. I knew there had to be a better way! And indeed, I found one that brought my run time from 190 seconds to 19 seconds!

I assumed almost immediately that my problem was the nested for-loop. That means I am taking the first object in ‘Array 1’ and scanning through all of ‘Array 2’ to see if it’s there. Then I do that again for the second object in ‘Array 1’. Then the third. Then the fourth. Man… I’m tired already.

So I did some Googling, and found this post on Stack Overflow (an AMAZING resource by the way):

stackoverflow.com/questions/1011 … bjective-c

From here, I noticed the containsObject: method - could this be faster? Let’s implement the code and see…

        // STRING CHALLENGE
        
        NSString *nameString = [NSString stringWithContentsOfFile:@"/usr/share/dict/propernames" 
                                                         encoding:NSUTF8StringEncoding 
                                                            error:NULL];
        
        NSString *wordString = [NSString stringWithContentsOfFile:@"/usr/share/dict/words/" 
                                                         encoding:NSUTF8StringEncoding 
                                                            error:NULL];
        
        NSArray *names = [nameString componentsSeparatedByString:@"\n"];
        NSArray *words = [wordString componentsSeparatedByString:@"\n"];
        
        // Solution #1: using built-in containsObject method (19 seconds)
        for (NSString *n in names) {
            if ([words containsObject:[n lowercaseString]]) {
                NSLog(@"%@", n);
            }
        }
        
        // Solution #2: nested for-loop (190 seconds & fan blasting on mac mini)
        for (NSString *n in names) {
            for (NSString *w in words) {
                if ([[n lowercaseString] compare:w] == NSOrderedSame) {
                    NSLog(@"%@", w);
                }
            }
        }

YES! Holy crap! It’s 10x faster, actually - bringing me from 190 seconds of runtime down to 19 seconds. Now we’re cooking with grease, baby!

Enjoy. :slight_smile:

UPDATE: Looks like the book covers both containsObject: and StackOverflow.com in chapter 16. So…not as revelatory as I thought. :smiley:


#2

Another update: As I got further through the book, the idea of NSSet was introduced. For what it’s worth, using NSSet instead of NSArray, I can complete this computation in <1 second!

new code

        // Solution #3: using NSSet (<1 second!)
        NSSet *nameSet = [NSSet setWithArray:names];
        NSSet *wordSet = [NSSet setWithArray:words];
    
        for (NSString *n in nameSet) {
            if ([wordSet containsObject:[n lowercaseString]]) {
                NSLog(@"Set: %@", n);
            }
        }