Objective-C Fastest Way to find Closest NSDate in NSArray

Question

I pass in an NSDate to the following function and want to find the NSDate in the array that is closest in time to the passed in value.

Please note that I do not want to know if the array contains the exact date like this post: Find NSDate in sorted NSArray

I want to know which date in the array is nearest in time to my reference date.

I must do this frequently. The following works but is slow - how can I speed things up?

// Get the XYZ data nearest to the passed time
- (eciXYZ)eciDataForTime:(NSDate*)time {

    // Iterate our list and find the nearest time
    float nearestTime = 86400; // Maximum size of dataset ( 2 days )
    int index = 0; // Track the index
    int smallestDifferenceIndex = index; // Track the index with the smallest index
    NSDate *lastListDate; // Track the closest list date
    for ( index = 0 ; index < [self.time count]-1 ; index++ ) {
        NSDate *listDate = [self.time objectAtIndex:index]; // Get the date - Time is an NSMutableArray of NSDates
        // NSTimeInterval is specified in seconds; it yields sub-millisecond precision over a range of 10,000 years.
        NSTimeInterval timeDifferenceBetweenDates = [listDate timeIntervalSinceDate:time];
        if ( timeDifferenceBetweenDates < nearestTime && timeDifferenceBetweenDates > 0 ) {
            nearestTime = timeDifferenceBetweenDates; // Update the tracker
            smallestDifferenceIndex = index; // Update the smallest difference tracker
            lastListDate = listDate; // Capture the closest date match
            //NSLog(@"Time: %f %@",timeDifferenceBetweenDates,listDate);
        }
    }

Answer 1

Edit: I was under the mistaken impression that NSMutableOrderedSet would automatically maintain order. In the past I probably had used a subclass to achieve this effect. There is no benefit to using it over NSArray unless you want set semantics.

keeping a collection sorted is a good way to keep searches fast. use NSOrderedSet or NSMutableOrderedSet instead of an array object if you can, otherwise you will have to keep the array sorted when you add to it, or if it is only created once then you just sort it then.

Also you can enumerate any collection (that conforms to the protocol) faster by using NSFastEnumeration.

example:

// for an NSOrdered set or NSArray of NSDates
for (NSDate* date in self.times) {
    // do something with date
    // cleaner, shorter code too
}

because your collection is sorted you now will be able to tell what the closest date is without having to iterate the entire collection (most of the time).

// searching for date closest to Tuesday
[Sunday] <- start search here
[Monday] <- one day before
[Thursday] <- two days after, we now know that Monday is closest
[Friday] <- never have to visit
[Saturday] <- never have to visit

As pointed out by @davecom you can search faster using a binary search. Normally you would achieve this using either CFArrayBSearchValues or the indexOfObject:inSortedRange:options:usingComparator: method on NSArray (it assumes the array is sorted so beware) and passing NSBinarySearchingOptions to the options parameter. In your case this won't work because you don't know the exact object or value you are looking for. You would have to roll your own binary search algorithm.

---

If this is not fast enough for your purposes we may need more information on context. It may be the best idea to use a C array/C++ list/NSPointerArray of timestamps instead. I feel like your biggest slowdown here is the Objective-C overhead, especially for the dates. If you don't use these as actual date objects anywhere then surely you would be better off using timestamps.