Выбор ближайших 3 дат из списка

Question

Я работаю над приложением для телегида и пытаюсь получить ближайшие 3 даты из NSArray с NSDictionary. Пока все хорошо, но я пытался выяснить, как я могу сделать это наилучшим образом, используя как можно меньше памяти и как можно меньше кода (следовательно, уменьшая вероятность ошибок или сбоев). Массив уже отсортирован.

У меня есть словарь со всеми каналами на один день. Словарь удерживает NSDate (называемую датой).
Допустим, на канале 8 передач, а сейчас время 11:45. шоу № 3 начинается в 11:00 и заканчивается в 12:00, шоу № 4 начинается в 12:00 и заканчивается в 13:00, шоу № 5 в 13:00 до 14:00 и т. д.
Как я могу получить показ # 3 (который начался в прошлом!) , # 4 и # 5 самый быстрый (с точки зрения памяти) и самый простой из моего массива словарей?

В настоящее время я выполняю цикл извлечения каждого словаря, а затем сравниваю дату словарей с текущей датой. И вот где я застрял. Или, может быть, у меня просто мозговой педик.

Мой текущий код (после некоторого времени тестирования разных вещей):

- (NSArray*)getCommingProgramsFromDict:(NSArray*)programs amountOfShows:(int)shows
{
    int fetched = 0;
    NSMutableArray *resultArray = [[NSMutableArray alloc] init];
    NSDate *latestDate = [NSDate date];

    for (NSDictionary *program in programs)
    {
        NSDate *startDate = [program objectForKey:@"date"];

        NSLog(@"Program: %@", program);
        switch ([latestDate compare:startDate]) {
            case NSOrderedAscending:
                NSLog(@"latestDate is older, meaning the show starts in the future from latestDate");
                // do something
                break;
            case NSOrderedSame:
                NSLog(@"latestDate is the same as startDate");
                // do something
                break;
            case NSOrderedDescending:
                NSLog(@"latestDate is more recent, meaning show starts in the past");
                // do something
                break;
        }

        // Now what?
    }

    return resultArray;
}

Я пишу это для iOS 5, используя ARC.

Answer 1

Я не уверен, что понял структуру вашей модели, у вас есть NSArray шоу, каждое из которых представляет собой NSDictionary, содержащее NSDate шоу вместе с другой информацией, верно?

ОдинИдея состоит в том, чтобы отсортировать это NSArray шоу в соответствии с расстоянием между временем начала шоу и сейчас.

NSArray* shows = ... // your arraw of NSDictionaries representing each show
NSArray* sortedShows = [shows sortedArrayUsingComparator:^(id show1, id show2) {
    NSTimeInterval ti1 = fabs([[show1 objectForKey:@"startDate"] timeIntervalSinceNow]);
    NSTimeInterval ti2 = fabs([[show2 objectForKey:@"startDate"] timeIntervalSinceNow]);
    return (NSComparisonResult)(ti1-ti2);
}];

Тогда, конечно, в этот момент легко взять только 3 первых шоумассива sortedShows.

Если я неправильно понял структуру вашей модели, пожалуйста, отредактируйте ваш вопрос, чтобы указать его, но я уверен, что вы можете адаптировать мой код, чтобы он соответствовал вашей модели

Answer 2

После вашего РЕДАКТИРОВАНИЯ и объяснения, вот еще один ответ, который, как мы надеемся, лучше подойдет для вашего вопроса.

Идея состоит в том, чтобы найти следующий за ним индекс шоу (startDate после этого).Как только он у вас будет, будет легко получить шоу по предыдущему индексу (в эфире) и 2 шоу после него.

NSUInteger indexOfNextShow = [arrayOfShows indexOfObjectPassingTest:^BOOL(id program, NSUInteger idx, BOOL *stop) {
    NSDate* startDate = [program objectForKey:@"date"];
    return ([startDate timeIntervalSinceNow] > 0); // startDate after now, so we are after the on-air show
}];

На этом этапе indexOfNextShow содержит индекс шоув вашем NSArray, который выйдет в эфир после текущего шоу.Таким образом, что вы хотите в соответствии с вашим вопросом, это объекты с индексами indexOfNextShow-1 (показать в эфире), indexOfNextShow (следующее шоу) и indexOfNextShow+1 (показать после следующего).

// in practice you should check the range validity before doing this
NSIndexSet* indexes = [NSIndexSet indexSetWithIndexesInRange:NSMakeRange(indexOfNextShow-1,3)];
NSArray* onAirShowAnd2Next = [arrayOfShows objectsAtIndexes:indexes];

Очевидно, вНа практике вам следует добавить некоторые проверки (например, indexOfNextShow будучи> 0, прежде чем пытаться получить доступ к объекту по индексу indexOfNextShow-1 и indexOfNextShow+1, не превышающему общее количество показов в вашем массиве).

Преимуществоэто потому, что ваш массив шоу уже отсортирован по startDate, indexOfObjectPassingTest: возвращает первый объект, прошедший тест, и прекращает итерацию, как только он найдет нужный объект.Так что это и лаконичный, легко читаемый код и относительно эффективный.

.

Answer 3

Вопрос задает «самый быстрый (по памяти)».Вы ищете самый быстрый или самый сознательный след памяти?При использовании алгоритмов часто существует компромисс между временем и пространством, поэтому, когда вы делаете это быстрее, вы обычно делаете это путем добавления индексов и других структур данных поиска, которые увеличивают объем памяти.

Для этой проблемы прямая реализация будетперебирать каждый канал и каждый элемент, сравнивая каждый из них с 3 верхними, хранящимися в памяти.Но это может быть медленным.

С дополнительным хранилищем у вас может быть дополнительный массив, который индексирует во временные интервалы (достаточно ли хорош один раз в 15 минут?), А затем в последовательных цепочках отображаются эти временные интервалы.Учитывая текущее время, вы можете индексировать прямо в текущий временной интервал, а затем искать следующий набор шоу.Массив будет иметь указатели на те же объекты, на которые указывают словари.Это дополнительная структура данных для оптимизации одного конкретного шаблона доступа, но она делает это по цене - больше памяти.

Это увеличило бы ваш отпечаток, но было бы очень быстрым, поскольку это всего лишь смещение индекса массива.

Наконец, вы можете сохранить все свои шоу в базе данных sqlite или CoreData и решить вашу проблему одним запросом.Пусть движок SQL делает тяжелую работу.этот мир также сохранит ваш отпечаток памяти разумным.

Надежда, которая вызывает некоторые идеи.

РЕДАКТИРОВАТЬ:

Грубый пример, показывающий, как вы можете построитьтаблица просмотра - массив со слотами на каждые 15 минут.Это мгновенный переход к текущему временному интервалу, так как это просто смещение массива.Затем вы идете по абсолютному количеству прогулок - следующие три и вы выходите.Таким образом, это смещение массива с 3 итерациями.

Большая часть кода является датой построения - таблица поиска, находящая временной интервал и цикл, является тривиальной.

NSInteger slotFromTime(NSDate *date)
{
    NSLog(@"date: %@", date);

    NSDateComponents *dateComponents = [[NSCalendar currentCalendar] components:(NSHourCalendarUnit | NSMinuteCalendarUnit) fromDate:date];
    NSInteger hour = [dateComponents hour];
    NSInteger minute = [dateComponents minute];
    NSInteger slot = (hour * 60 + minute)/15;
    NSLog(@"slot: %d", (int)slot);

    return slot;
}

int main (int argc, const char * argv[])
{
    // An array of arrays - the outer array is an index of 15 min time slots.
    NSArray *slots[96];
    NSDate *currentTime = [NSDate date];
    NSInteger currentSlot = slotFromTime(currentTime);

    // populate with shows into the next few slots for demo purpose
    NSInteger index = currentSlot;
    NSArray *shows1 = [NSArray arrayWithObjects:@"Seinfeld", @"Tonight Show", nil];
    slots[++index] = shows1;
    NSArray *shows2 = [NSArray arrayWithObjects:@"Friends", @"Jurassic Park", nil];
    slots[++index] = shows2; 

    // find next three -jump directly to the current slot and only iterate till we find three.
    // we don't have to iterate over the full data set of shows
    NSMutableArray *nextShow = [[NSMutableArray alloc] init];
    for (NSInteger currIndex = currentSlot; currIndex < 96; currIndex++)
    {
        NSArray *shows = slots[currIndex];
        if (shows)
        {
            for (NSString *show in shows)
            {
                NSLog(@"found show: %@", show);
                [nextShow addObject:show];
                if ([nextShow count] == 3) 
                    break;
            }
        }

        if ([nextShow count] == 3) 
            break;        
    }

    return 0;
}

Это приводит к:

2011-10-01 17:48:10.526 Craplet[946:707] date: 2011-10-01 21:48:10 +0000
2011-10-01 17:48:10.527 Craplet[946:707] slot: 71
2011-10-01 17:48:14.335 Craplet[946:707] found show: Seinfeld
2011-10-01 17:48:14.336 Craplet[946:707] found show: Tonight Show
2011-10-01 17:48:21.335 Craplet[946:707] found show: Friends