iPhone SDK Nested For Loop performance

Question

Hi All,

I have a NSArray of string id and a NSDictionary of NSDictionary objects. I am currently looping through the string id array to match the id value in the NSDictionary.

There are around 200 NSDictionary objects and only 5 or so string ID.

My current code is such:

for (NSString *Str in aArr) {
        for (NSDictionary *a in apArr)
        {
            if ([a objectForKey:@"id"] == Str)
            {
            NSLog(@"Found!");
            }
        }
}

The performance of the above code is really slow and I was wondering if there is a better way to do this?

Answer 1

Not sure about the iPhone's cache architecture, but swapping the two loops so that you make as many lookups on the same dictionary before switching to another sounds like it should improve locality. Better locality often leads to (sometimes dramatically) better performance.

Answer 2

I'd implement your code in the following way:

for (NSDictionary *a in apArr)
{
    if ([aArr containsObject:[a objectForKey:@"id"]])
    {
        NSLog(@"Found!");
    }
}

I'm still not sure about containsObject performance, but, I guess there should be SDK optimizations to find objects faster than O(n).

Added:

Another suggestion. I suppose, that "id" field is unique for all NSDictionary objects. If it is so, you can remap your NSArray of NSDictionaries to NSDictionary:

from:

index -> NSDictionary

to:

id -> NSDictionary

And you will find elements for O(1) instead of O(n).

Re remapping. Either you should create NSDictionary with appropriate format (id -> object) or you may remap your array in the following way:

NSMutableDictionary *md = [[NSMutableDictionary alloc] init];
for ( NSDicationary *a in apArr ) {
    [md setObject:a forKey:[a objectForKey:@"id"]];
}