Finding max integer value in NSArray consisting of NSDictionary objects

Question

Is there any quick and efficient way of finding max int value in NSArray that consists of NSDictionary objects? I mean sure, I can implement for cycle going through, but I am looking for some API function that's already tweaked to maximum speed since it's operating with fairly large amount of data.

[(int, string, string), (int, string, string), (int, string, string)]

I tried working with valueForKeyPath but that really didn't help me so far, since it works with "ordinary" NSArray objects.

Answer 1

Out of curiosity, I did a little comparison of valueForKeyPath: vs simple iteration. On my iMac core i7 running OS X 10.8.2, the simple iteration is about twice as fast for an array of 10M elements.

Here's the test program I made:

#import <Foundation/Foundation.h>
#undef NDEBUG
#import <assert.h>
#import <limits.h>
#import <stdio.h>
#import <stdlib.h>

#define ELEMENTS_IN_ARRAY 10000000

NSArray *newArrayWithDictionaryElementCount(int count) {
    NSMutableArray *arr = [[NSMutableArray alloc] initWithCapacity:count];
    for (int i = 0; i < count; ++i) {
        [arr addObject:[NSDictionary dictionaryWithObjectsAndKeys:
                        [NSString stringWithFormat:@"value%d", i], @"string",
                        [NSNumber numberWithInt:rand()], @"int",
                        nil]];
    }
    return arr;
}

int maxIntValueByKeyPathInArray(NSArray *arr) {
    return [(NSNumber *)[arr valueForKeyPath:@"@max.int"] intValue];
}

int maxIntValueByIterationInArray(NSArray *arr) {
    int max = INT_MIN;
    for (NSDictionary *dict in arr) {
        int val = [(NSNumber *)[dict valueForKey:@"int"] intValue];
        if (val > max) {
            max = val;
        }
    }
    return max;
}

NSTimeInterval timeExecutionOf(void(^blockToTime)(void)) {
    NSDate *start = [NSDate date];
    blockToTime();
    return -[start timeIntervalSinceNow];
}

int main (int argc, const char *argv[]) {
    srand(time(NULL));
    @autoreleasepool {
        NSArray *arr = newArrayWithDictionaryElementCount(ELEMENTS_IN_ARRAY);
        assert(maxIntValueByIterationInArray(arr) == maxIntValueByKeyPathInArray(arr));
        (void) printf("Time by key path: %f s\n", timeExecutionOf(^{ maxIntValueByKeyPathInArray(arr); }));
        (void) printf("Time by iteration: %f s\n", timeExecutionOf(^{ maxIntValueByIterationInArray(arr); }));
    }
    return 0;
}

The results on my machine:

$ clang -fobjc-arc -framework Foundation -O4 -march=corei7 -o arraytest arraytest.m
$ ./arraytest
Time by key path: 1.809646 s
Time by iteration: 0.886023 s

My hypothesis is that the iterative solution is already about as fast as can be for these data structures; there is no getting around having to do the dictionary look-up for each array element. Furthermore, this custom-made iterative solution benefits from knowing that all the NSNumber objects have int values; using isGreaterThan: for comparison slows things down somewhat (but it's still faster than valueForKeyPath:). Any general-purpose library method would almost certainly incur that penalty internally…