Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Finding smallest and biggest value in NSArray of NSNumbers

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?

like image 468
Sergey Grischyov Avatar asked Apr 10 '13 16:04

Sergey Grischyov


2 Answers

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.

like image 151
Martin R Avatar answered Sep 22 '22 17:09

Martin R


Save float by wrapping under NSNumber then

NSNumber *max=[numberArray valueForKeyPath:@"@max.doubleValue"]; NSNumber *min=[numberArray valueForKeyPath:@"@min.doubleValue"]; 

*Not compiled and checked, already checked with intValue, not sure about double or float

like image 35
Anoop Vaidya Avatar answered Sep 19 '22 17:09

Anoop Vaidya