Follow up to “Optimize a search in an NSMutableDictionary”

Warp Speed

This is a follow up post to Optimize a search in an NSMutableDictionary. Where that post left off I had only managed to save about 500ms of processing time in a song search. With some help I employed hashKeys and reduced that processing time by much more than half. Depending on the quantity of stored elements in a NSMutableDictionary associated with a hashKey, it could be a lot more than that, say 500ms total.

So employing 2 methods to aid in the creation of a hashKey and in theĀ retrievalĀ of a candidate NSMutableDictionary object is the heart of the speed increase. I present for you the two methods (non-sanitized… if you want to employ yourself, use your own objects).

#pragma mark - hashKey stuff for song titles

- (int) computeHashKeyForString:(NSString *)songName {
    NSUInteger length = [songName length];
    uint hash = length << 24;
    uint sumOfChars = 0;
    for (NSUInteger i = 0; i < length; i ++) {
        sumOfChars += [songName characterAtIndex:i];
    return hash + ( sumOfChars / 8 ) & 0x00ffffff;

- (NSMutableDictionary *) candidatesForString:(NSString *)userString {
    int hash = [self computeHashKeyForString:userString];
    int fuzzyKey = 0;
    for (id key in [testSongsDictionary allKeys]) {
        if (hash == [key intValue])
            return [testSongsDictionary objectForKey:key];

        if (abs (hash - [key intValue]) < (hash - fuzzyKey)) {
            fuzzyKey = [key intValue];
    id realKey = [NSNumber numberWithInt:fuzzyKey];
    return [testSongsDictionary objectForKey:realKey];

Now, in my data generation method this is how I am storing the songs based on hashKey:

testSongsDictionary = [[NSMutableDictionary alloc] init];
    @autoreleasepool {
        MPMediaQuery *allSongsQuery = [MPMediaQuery songsQuery];
        NSArray *mySongsArray = [allSongsQuery items];
        //testSongsDictionary is the master songs NSMutableDictionary
        for(MPMediaItem *song in mySongsArray){
            NSString *songTitle = [[song valueForProperty: MPMediaItemPropertyTitle] lowercaseString];
            //Remove 01 -, 02 - from titles
            NSRegularExpression *regex = [NSRegularExpression regularExpressionWithPattern:@"^\\d+ - "
            songTitle = [regex stringByReplacingMatchesInString:songTitle
                                                          range:NSMakeRange(0,[songTitle length])
            //Remove all (Album Version), etc.
            NSRegularExpression *regex2 = [NSRegularExpression regularExpressionWithPattern:@"(.*?)" options:NSRegularExpressionCaseInsensitive error:NULL];
            songTitle = [regex2 stringByReplacingMatchesInString:songTitle options:0 range:NSMakeRange(0, [songTitle length]) withTemplate:@""];

            NSRegularExpression *regex3 = [NSRegularExpression regularExpressionWithPattern:@" - " options:NSRegularExpressionCaseInsensitive error:NULL];
            songTitle = [regex3 stringByReplacingMatchesInString:songTitle options:0 range:NSMakeRange(0, [songTitle length]) withTemplate:@" "];
            //NSDictionary require object for key
            int hashKey = [self computeHashKeyForString:songTitle];
            id realKey = [NSNumber numberWithInt:hashKey];
            if([testSongsDictionary objectForKey:realKey] != nil){
                NSMutableDictionary *foundDictionary = [testSongsDictionary objectForKey:realKey];
                [foundDictionary setObject:song forKey:songTitle];
            } else {
                NSMutableDictionary *subDictionary = [[NSMutableDictionary alloc] init ];
                [subDictionary setObject:song forKey:songTitle];
                [testSongsDictionary setObject:subDictionary forKey:realKey];

That’s the crux of the entire optimization. To snag a match requires very little code.

NSMutableDictionary *tester = [self candidatesForString:[stringValue lowercaseString]];
        MPMediaItem *song = [tester objectForKey:[stringValue lowercaseString]];
        NSArray *dis;
        MPMediaItemCollection *collection;
        if(song != nil)
            dis = [NSArray arrayWithObject:song];
            collection = [[MPMediaItemCollection alloc] initWithItems:dis];

Have a wonderful day, it’s OS X Lion day afterall!

Related Posts Plugin for WordPress, Blogger...

Leave a Reply

Your email address will not be published. Required fields are marked *

eight − 3 =

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>