Objective-C Самый быстрый способ найти ближайший NSDate в NSArray

Question

Я передаю NSDate следующей функции и хочу найти NSDate в массиве, который ближе всего по времени к переданному значению.

Пожалуйста, обратите внимание, что я не хочу знать, если массив содержит точную дату, как этот пост: Find NSDate in sorted NSArray

Я хочу знать, какую дату в массиве находится ближе во времени к моей базисную дату.

Я должен делать это часто. Следующие работы, но медленные - как я могу ускорить процесс?

// 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: я был под ошибочным впечатлением, что NSMutableOrderedSet будет автоматически поддерживать порядок. Раньше я, вероятно, использовал подкласс для достижения этого эффекта. Нет никакой пользы от использования его над NSArray, если вы не хотите использовать семантику.

Сохранение коллекции, сортированной, является хорошим способом быстрого поиска. используйте NSOrderedSet или NSMutableOrderedSet вместо объекта массива, если вы можете, в противном случае вам придется сохранить массив, отсортированный при его добавлении, или если он создается только один раз, тогда вы просто сортируете его.

Также вы можете перечислить любую коллекцию (которая соответствует протоколу) быстрее, используя NSFastEnumeration.

пример:

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

, потому что ваша коллекция отсортирована теперь вы сможете сказать, что ближайшая дата без перебора всей коллекции (большую часть времени).

// 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 

Как указано @davecom, вы можете искать быстрее, используя двоичный поиск. Обычно вы достигаете этого, используя либо CFArrayBSearchValues, либо метод indexOfObject:inSortedRange:options:usingComparator: на NSArray (он предполагает, что массив отсортирован так, что будьте осторожны) и передайте NSBinarySearchingOptions параметру параметров. В вашем случае это не сработает, потому что вы не знаете точный объект или ценность, которые вы ищете. Вам нужно будет свернуть собственный алгоритм бинарного поиска.

---

Если это не так быстро для ваших целей, нам может понадобиться дополнительная информация о контексте. Возможно, лучше всего использовать список C array/C++/NSPointerArray временных меток. Я чувствую, что ваш самый большой спад здесь - это накладные расходы Objective-C, особенно для дат. Если вы не используете их в качестве реальных объектов даты где-нибудь, тогда вам будет лучше использовать временные метки.