给定一个数组,其元素是以下形式的对象:
{
"description": "foo",
"startTime": 0,
"endTime": 100
}
我需要找到 startTime <= t <= endTime
的所有元素.
-
(endTime - startTime) >= 100
,但时间差没有明确的上限,数组中每个对象的时间差也不一定相同。startTime
可以为负数。 -
arr[i].startTime <= arr[i + 1].startTime
,但对于endTime
来说不一定同样成立。 . -
description
不唯一,甚至不一定在给定的时间范围内。 - 时间相当于视频中的毫秒,很可能是一个小时或更长时间。如果一个 1 小时的视频在其整个长度中有 100 毫秒持续时间的对象,则需要过滤 36,000 个数组元素。根据视频的不同,单个 100 毫秒的时间跨度内很可能会出现十几个对象。
我当前的解决方案很简单 Array.prototype.filter
调用:
video.getCurrentTime((s) => { // library function; s=current time in seconds of the video
const ms = Math.floor(s * 1000);
const itemsAtTime = metadata.filter((o) => { // metadata is array of objects
const start = o.startTime;
const end = o.endTime;
return start <= ms && ms <= end;
});
// ...
for (let obj of itemsAtTime) {
// do stuff
}
});
据我所知,filter
被实现为线性搜索。有没有更好的算法可以实现我的目标?也许是二分搜索的某种变体?
在我正在测试的 2 分钟演示视频/元数据中,大部分 filter
调用大约在 0.7 毫秒内完成。然而,其中许多需要 1-5 毫秒,我跟踪了一些极端异常值,例如 11 毫秒甚至 33 毫秒。我的“do stuff”循环通常在 0.1ms 内完成,重负载需要 4ms,异常值需要 12ms。最糟糕的是getCurrentTime
函数是异步的,通常在调用它和调用回调之间需要 1-5 毫秒,重负载在 50-60 毫秒左右,异常值超过 500 毫秒。考虑到此代码位于传递给 setInterval
的函数中,在视频播放时运行间隔(目前间隔为 250 毫秒,但最终我想我想使用 100 毫秒或更短的间隔),当我开始使用时长超过一小时的视频时,我担心性能.
最佳答案
您可以进行二分搜索来查找第一个项目 startTime <= ms
。然后您可以从该索引开始线性过滤。这是我能想到的最好的了。
所以,类似:
const binaryWhereMin = function(arr, ms) {
// write your function that returns the index of first element start <= ms
};
let index = binaryWhereMin(arr, ms);
let result = arr.splice(index, arr.length).filter(/* your filter */);
我看不出更好的方法,因为末端没有排序。
这里有一个binary search example 。但您需要更改它以不搜索特定元素(它不会那么有效!,但我相信它仍然比您拥有的更好)。
关于javascript - 查找时间 t 的所有数组元素,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42655991/