从列表中选择最近的 3 个日期

Question

我正在开发一个电视指南应用程序，并尝试使用 NSDictionary 从 NSArray 中获取最近的 3 个日期。到目前为止一切顺利，但我一直在尝试找出如何使用尽可能少的内存和尽可能少的代码以最佳方式做到这一点（从而减少错误或崩溃的可能性）。数组已经排序了。

我有一本字典，其中包含一天所有频道的节目。字典保留了一个 NSDate（称为日期）。
假设某个频道有 8 个节目，现在时间为 11:45。节目 #3 于 11:00 开始并于 12:00 结束，节目 #4 于 12:00 开始于 13:00 结束，节目 #5 于 13:00 至 14:00 等
我怎样才能从我的字典数组中获取最快（内存方面）和最简单的节目＃3（从过去开始！），#4和#5？

目前我正在做一个 for 循环来获取每个字典，然后将字典日期与当前日期进行比较。这就是我被困的地方。或者也许我只是脑子有问题。

我当前的代码（经过一段时间的测试不同的东西）：

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

在您的编辑和解释之后，这是另一个答案，希望能更好地适合您的问题。

这个想法是找到下一个节目的索引（现在之后的开始日期）。一旦您拥有它，就可以轻松观看前一个索引处的节目（正在播出）以及其后的 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-1 和 indexOfNextShow+1 处的对象之前，indexOfNextShow >0不超过阵列中的节目总数）。

这样做的优点是，由于您的节目数组已按 startDate 排序，因此 indexOfObjectPassingTest: 返回第一个通过测试的对象，并在找到正确的对象后立即停止迭代。所以这是一种简洁、易于阅读的代码并且相对高效。

。

Answer 2

我不确定我是否理解你的模型结构，你有一个 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);
}];

当然，此时很容易只获取 sortedShows 数组的前 3 个显示。

如果我误解了您的模型结构，请编辑您的问题以指定它，但我确信您可以调整我的代码以适合您的模型

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