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

Question

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

总体思路:我有一个视频，在某些时间间隔内，我在 View 上显示对象(TimedObject 对象)。 TimedObjects 具有由 NSRange 结构 (frameRange) 指定的间隔，它包含间隔的起始帧和结束帧。 TimedObjects 也有关于要显示的内容的数据(文本、颜色、位置等...)。

具体思路:我想构建一个包含一组范围的数据集，如该时间线所示...

其中 A、B、C、D 是 TimedObjects，范围代表它们的开始和结束帧。

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

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) 检查该帧上是否存在 TimedObject(可以是多个)(在 NSRange frameRange 属性中)。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];
    }
}

此处要进行的明确优化是通过起始帧对 TimedObject 进行排序，如果我们到达 TimedObject 的起始帧大于 frameNumber 的 TimedObject，我们可以提前终止循环。然而，这仍然是最坏的 O(n)。

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

如有任何建议或想法，我们将不胜感激!让我知道是否需要进行任何澄清，或者我是否应该提供更多信息。谢谢!

Answer 1

您要搜索的内容的答案称为 Interval tree ，维基百科上有解释。