ios - 如何创建分段的时间线数据集(使用Objective-C)

我正在寻找一个可以表示为时间间隔的数据集。我需要快速查找一个值，因此希望在检查值是否在范围内时避免循环。

总体思路:我有一个视频，在该视频中，我会在一定时间间隔内在视图上显示对象(TimedObject对象)。 TimedObject具有由NSRange结构(frameRange)指定的间隔，该间隔保留该间隔的开始帧和结束帧。 TimedObject还具有有关要显示的内容(文本，颜色，位置等)的数据。

的具体想法:我想建立一个包含一组范围的数据集，如时间轴所示。

其中A，B，C，D是TimedObject，其范围代表其开始和结束帧。

对该数据集的调用如下所示:

NSArray *timeObjectsOnFrame = [timeObjectsModel getTimedObjectsOnFrame:15];  // Returns array containing TimedObject A
NSArray *timeObjectsOnFrame = [timeObjectsModel getTimedObjectsOnFrame:75];  // Returns array containing TimedObject C and D
NSArray *timeObjectsOnFrame = [timeObjectsModel getTimedObjectsOnFrame:30];  // Returns a nil array

所以getTimedObjectsOnFrame:将有两个任务...
1)检查该帧(在NSRange frameRange属性中)是否存在一个TimedObject(可以多个)。
2)如果该帧上至少存在一个TimedObject，则返回在该间隔内具有该帧的所有TimedObject。

我目前的设置方式:每次对getTimedObjectsOnFrame:的调用都会循环遍历所有TimedObject(存储在数组中)。如果frameNumber在当前timedObject的范围内，则将该TimedObject添加到数组以在循环完成后返回。

- (NSArray *)getTimedObjectsOnFrame:(NSInteger)frameNumber
{
    NSMutableArray *tempArray = [NSMutableArray array];
    for (TimedObject *timedObject in _timedObjectsArray) {
        if (NSLocationInRange(frameNumber, timedObject.frameRange)) {
            // This object is in the range, save it to return later.
            [tempArray addObject:timedObject];
        }
    }
    if (tempArray.count == 0) {
        return nil;
    } else {
        return [NSArray arrayWithArray:tempArray];
    }
}

此处要进行的明确优化是按开始帧对TimedObjects进行排序，如果到达TimedObject的开始帧大于frameNumber的TimedObject，则可以提早终止循环。但是，这仍将是最差的O(n)。

需要什么:如何创建一个数据集，该数据集可以使我快速查找所需的数据，并且仍然能够返回多个值？我希望我可以创建一个轻量级的东西，并代表一个像上面的时间表。我在Objective-C中构建它，但是伪代码也会有所帮助。

任何建议或想法表示赞赏!让我知道是否需要进行任何澄清，或者是否应该提供更多信息。谢谢!

最佳答案

您要搜索的内容的答案称为Interval tree，在Wikipedia中有解释。

关于ios - 如何创建分段的时间线数据集(使用Objective-C)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25729793/