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?

Solution 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.

Solution 2

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

Solution 3

sort it. take the first and the last element.

btw: you cant store floats in an NSArray, you will need to wrap them in NSNumber objects.

NSArray *numbers = @[@2.1, @8.1, @5.0, @.3];
numbers = [numbers sortedArrayUsingSelector:@selector(compare:)];

float min = [numbers[0] floatValue];
float max = [[numbers lastObject] floatValue];

Comments

[vikingosegundo]

often block enumeration is faster than fast enumeration. did u try that? how often did u execute your examples?

[vikingosegundo]

note that my solution will also work for non numeric objects.

[Martin R]

@vikingosegundo: I have updated the answer. Block enumeration is slower than fast enumeration here.

[vikingosegundo]

How often did u execute the codes? one or few runs wont give you a good result.

[Martin R]

@vikingosegundo: I will improve the test program to determine the average execution time for each method, and then report the result later.

[vikingosegundo]

@MartinR, I tested it with sorting a randomized array of 1000000 100 times. fast enum: 2.309 sec, block enum: 2.266

[vikingosegundo]

@MartinR, I repeated that test 30 times, block enumeration was faster each time.

[Martin R]

@vikingosegundo: I don't understand your code. Where is the block enumeration? I see 2 (identical) fast enumerations.

[vikingosegundo]

damn, i wrote it into another project and that factored it out to a new one. I guess it was a c&p error. give me a second to recreate it.

[vikingosegundo]

@MartinR: i fixed my program. and now fast is idead faster, contrary to bbum's explanations here: stackoverflow.com/a/4487012/106435

[Martin R]

@vikingosegundo: Yes, that is also my result. See also blog.bignerdranch.com/2337-incremental-arrayification: "In general, fast enumeration is the winner in both performance and readability".

[vikingosegundo]

@MartinR: one of the comments over there suggests that it is the usage of the __block qualifier, that slows the block enumeration dramatically. So with changing properties on the enumerated object it could still be as fast (faster ??) as fast enumeration, and my faith in bbum is restored.

[Martin R]

@vikingosegundo: I tried this (pointers) and noticed almost no difference (0.020 instead of 0.021). But concurrent enumeration is (of course) faster, see "Update 2" above.

[vikingosegundo]

to clarify: the compare: method is not limited to "numeric objects", it is the duty of the objects themselves to implement it. So although you gave a impressive answer, it is not correct.

[vikingosegundo]

I have a downvote in the very same moment. and @ate50eggs did down vote two times today. so the reason is: Revenge. He must assume one of us downvoted him.

[Grady Player]

caching would be faster still ... would have to mark as dirty if min or max were removed... and be very type careful with floats and doubles etc.

[JonahGabriel]

I am confused. Did I say compare is only limited to numeric objects? Is there actually an error in the code I posted, if so, please point it out.

[vikingosegundo]

you find your solution more elegant, as it works with non numeric objects as-well. this implies, the other doesn't.

[JonahGabriel]

Nope, I like it because it uses blocks and I love me some blocks.

[Hot Licks]

I confess to being a little surprised that concurrent really is about twice as fast as single threaded, even with the synchronization. However, is there really synchronization, since you're apparently passing a nil pointer rather than an object to @synchronized?

[Martin R]

@HotLicks: Oops!!! That seems to be a very stupid error on my side :-( ! I will try if I find the project again, fix that and update the results.

[Martin R]

@HotLicks: How embarrassing! But thank you for the feedback, I have updated the answer.

[Hot Licks]

There may well be a way to do multi-threading where you accumulate the "local" mimima/maxima within each thread and then synchronize once at the end. But it would be considerably more complex. (Always be suspicious when "parallel" is faster than single-threaded.)

[aryaxt]

Not performant. Enumerating through each object is a much better solution

[vikingosegundo]

we cannot assume performance here as the actual sorting algorithm and also the datastore of an array is hidden from the user. but if yu want to provide test data I am happy to incorporate it into my answer.

[aryaxt]

What is the Big-O notation for enumerating through items in an array once? it's n. Find me a sort algorithm that can have an O notation of n in a case where it's not sorted. The only way it can perform as well is if all items in array are already sorted, which in that case this question wouldn't exist en.wikipedia.org/wiki/Sorting_algorithm

[vikingosegundo]

what is the point of micro-optimizing code in GUI apps? your neurons will always be slower. and actually you are assuming that NSArrays are lists. they are not. ridiculousfish.com/blog/posts/array.html

[Martin R]

Where is the difference to stackoverflow.com/a/15931145/1187415?