javascript - 查找时间 t 的所有数组元素

Question

给定一个数组，其元素是以下形式的对象:

{
    "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 毫秒或更短的间隔)，当我开始使用时长超过一小时的视频时，我担心性能.

Answer 1

您可以进行二分搜索来查找第一个项目 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 。但您需要更改它以不搜索特定元素(它不会那么有效!，但我相信它仍然比您拥有的更好)。