用于查找基于时间的事件的最佳Javascript算法

Optimal Javascript algorithm for finding time-based events

本文关键字：事件 最佳 Javascript 算法 时间 查找 于时间 用于      更新时间：2023-09-26

我在Javascript中有一个对象数组，其中包含以毫秒为单位的事件开始和结束时刻。我们的代码库目前使用一种简单的搜索算法，该算法在数组中迭代，直到我们找到包含某个时刻的事件：

// time contains the moment of time we're looking to find an event for
profile.tempbasaltreatments.forEach( function eachTreatment (t) {
    if (time <= t.endmills && time >= t.mills) {
      return t;
    }
});

这与较大数据集的性能不符。什么是一个好的算法/数据模型，可以有效地遍历对象数组，找到封装某个时刻的事件？您可以假设，在事件重叠的情况下，第一次匹配总是足够的。

我建议这些预处理步骤（在搜索之前）：

  1. 如果出于其他目的需要，可以选择复制原始阵列
  2. 按事件开始时间对数组进行排序。如果可能的话，这实际上应该由数据库来完成，数据库可以为此维护索引
  3. 从数组中删除结束时间早于上一个事件结束时间的事件。当某个时间与此删除的事件匹配时，它也可以与上一个事件匹配。由于匹配任何事件都足够好，我们可以删除此事件

然后搜索将是二进制的，如下所示：

  1. 将搜索范围设置为整个数组。范围表示为数组中的起始索引和结束索引（而不是两次）
  2. 取该范围的中间元素
  3. 如果此事件与给定时间匹配，则成功退出
  4. 如果此事件的开始时间大于给定时间，则从步骤2开始，用所选元素之后的一半范围重复
  5. 否则，取范围的另一半（在选定元素之前），从2开始重复
  6. 如果范围中没有更多事件，请停止重复，并失败退出

预处理应该只进行一次，如果您仍然需要排序，则时间复杂度为O（n log n），否则为O（n）。完成后，您可以在O（logn）时间内重复查找事件。

以下是上面的一些JavaScript代码：

// Create a copy of the original array and sort it by event start date
var events = profile.tempbasaltreatments.slice(0).sort(function (a, b) { 
    return a.mills - b.mills;
});
// Remove events that fall completely within the limits of another event.
// They are not needed to find an event for a given time.
for (var i = 0; i < events.length-1;) {
    if (i && events[i].endmills < events[i-1].endmills) {
         events.splice(i, 1);
    } else {
         i++;
    };
}
// Now also the remaining events' end dates are sorted
// function for fast search in events:    
function findEvent(events, time) {
    // Binary search for event
    var first = 0, last = events.length - 1;
    while (first <= last) { 
        var i = first + Math.floor((last - first) / 2);
        var t = events[i];
        if (time >= t.mills && time <= t.endmills) return t;
        if (time < t.mills) {
            last = i - 1;
        } else { // time > t.endmills
            first = i + 1;
        }
    }
    // returns undefined
}
// Example call: find a currently running event:
var foundEvent = findEvent(events, new Date().getTime());

附录

以下是最后一个预处理步骤中的过滤过程。首先是事件在开始时间排序后的排序时间表：

a: ---------------
b:     -------
c:      ------------------
d:         --
e:            --  
f:                -----

可以消除的事件是b:

a: ---------------
c:      ------------------
d:         --
e:            --  
f:                -----

则d:

a: ---------------
c:      ------------------
e:            --  
f:                -----

则e:

a: ---------------
c:      ------------------
f:                -----

和f:

a: ---------------
c:      ------------------

很明显，在过滤之前，总覆盖期与原始覆盖期相同。

如果事件按开始时间、"中间时间"或结束时间排序，则可以使用二进制搜索来查找附近的事件，然后进行局部线性搜索，以找到包含时间戳的事件（局部搜索方向取决于排序顺序：如果事件是按开始时间排序的，则需要从最近的开始时间开始，按开始时间递减的方向进行搜索）。

这种方法的主要问题是，当没有最长事件持续时间时，它会很慢，因为这意味着除了到达列表的末尾之外，本地搜索没有停止标准。

更好的方法可能是将事件存储在适合高效访问的数据结构中，例如间隔树。

相关文章：