Finding smallest and biggest value in NSArray of NSNumbers

Question

What's an effective and great way to compare all the values of NSArray that contains NSNumbers from floats to find the biggest one and the smallest one?

Any ideas how to do this nice and quick in Objective-C?

Answer 1

If execution speed (not programming speed) is important, then an explicit loop is the fastest. I made the following tests with an array of 1000000 random numbers:

Version 1: sort the array:

NSArray *sorted1 = [numbers sortedArrayUsingSelector:@selector(compare:)];
// 1.585 seconds

Version 2: Key-value coding, using "doubleValue":

NSNumber *max=[numbers valueForKeyPath:@"@max.doubleValue"];
NSNumber *min=[numbers valueForKeyPath:@"@min.doubleValue"];
// 0.778 seconds

Version 3: Key-value coding, using "self":

NSNumber *max=[numbers valueForKeyPath:@"@max.self"];
NSNumber *min=[numbers valueForKeyPath:@"@min.self"];
// 0.390 seconds

Version 4: Explicit loop:

float xmax = -MAXFLOAT;
float xmin = MAXFLOAT;
for (NSNumber *num in numbers) {
    float x = num.floatValue;
    if (x < xmin) xmin = x;
    if (x > xmax) xmax = x;
}
// 0.019 seconds

Version 5: Block enumeration:

__block float xmax = -MAXFLOAT;
__block float xmin = MAXFLOAT;
[numbers enumerateObjectsUsingBlock:^(NSNumber *num, NSUInteger idx, BOOL *stop) {
    float x = num.floatValue;
    if (x < xmin) xmin = x;
    if (x > xmax) xmax = x;
}];
// 0.024 seconds

The test program creates an array of 1000000 random numbers and then applies all sorting techniques to the same array. The timings above are the output of one run, but I make about 20 runs with very similar results in each run. I also changed the order in which the 5 sorting methods are applied to exclude caching effects.

Update: I have now created a (hopefully) better test program. The full source code is here: https://gist.github.com/anonymous/5356982. The average times for sorting an array of 1000000 random numbers are (in seconds, on an 3.1 GHz Core i5 iMac, release compile):

Sorting      1.404
KVO1         1.087
KVO2         0.367
Fast enum    0.017
Block enum   0.021

Update 2: As one can see, fast enumeration is faster than block enumeration (which is also stated here: http://blog.bignerdranch.com/2337-incremental-arrayification/).

EDIT: The following is completely wrong, because I forgot to initialize the object used as lock, as Hot Licks correctly noticed, so that no synchronization is done at all. And with lock = [[NSObject alloc] init]; the concurrent enumeration is so slow that I dare not to show the result. Perhaps a faster synchronization mechanism might help ...)

This changes dramatically if you add the NSEnumerationConcurrent option to the block enumeration:

__block float xmax = -MAXFLOAT;
__block float xmin = MAXFLOAT;
id lock;
[numbers enumerateObjectsWithOptions:NSEnumerationConcurrent usingBlock:^(NSNumber *num, NSUInteger idx, BOOL *stop) {
    float x = num.floatValue;
    @synchronized(lock) {
        if (x < xmin) xmin = x;
        if (x > xmax) xmax = x;
    }
}];

The timing here is

Concurrent enum  0.009

so it is about twice as fast as fast enumeration. The result is probably not representative because it depends on the number of threads available. But interesting anyway! Note that I have used the "easiest-to-use" synchronization method, which might not be the fastest.