javascript - 查找给定时间范围内的日期

Question

我想存储一个包含属性 event_timestamp 的对象数组，该属性包含事件时间戳的 Date() 对象。

我想提供一个 from Date 对象和一个 to Date 对象，并收集该范围内的所有对象。

我不想迭代所有数组，我想要更快的东西...例如 O(Log N) 或其他任何东西。

有没有类似的东西在JavaScript中实现？是否有第三方库提供通过 O(Log N) 或任何其他快速方法进行搜索？

任何有关该问题的信息将不胜感激。

谢谢!

更新

感谢您迄今为止的回复。

我的情况是我有一个包含图表的仪表板。现在用户可以搜索例如..给我过去 15 分钟的结果。然后服务器提供具有相关结果的行，并且结果中的每一行都包含一个名为 event_timestamp 的属性，该属性包含一个 Date 对象。

现在，如果5分钟后用户再次搜索最后15分钟，那么这意味着他之前已经查询过前10分钟，所以我想缓存它并只从服务器发送最后一个请求5 分钟。

因此，每当用户查询服务器时，我都会获取响应并使用以下步骤解析它:

1. 获取第一行的 event_time
2. 获取最后一行的 event_time

3. 将以下对象附加到数组:

   { 行: 行， 起始日期:firstRowDate， 截止日期:最后一行日期}

现在..在前面的示例中，用户首先查询了15分钟，5分钟后再次查询了15分钟。这意味着我在对象中拥有 10 分钟宝贵的数据。

这里的主要问题是如何快速迭代行以找到我需要用于图表的相关行。

以一种简单的方式，我可以迭代所有行并找到在 fromDate 到 toDate 范围内的行。但如果我要处理几百万行，这会给客户带来麻烦。

我使用谷歌 FlatBuffers 来传输数据，然后我自己构建行。这样我就可以将它们保存为任何其他格式。

希望这有助于了解我的需求。谢谢!

Answer 1

对于当前的存储方式，没有比迭代整个数组更快的方法了。因此，仅遍历数组，复杂度就是 O(n)。

您需要访问的信息存储在一个对象内，该对象本身存储在数组中。除了查看每个对象之外，您还能如何访问信息。即使在具有不同数组实现的其他语言中，也不会有更快的方法。

加快速度的唯一方法是改变存储数据的方式。

例如，您可以实现 BST以日期为索引。由于这将按日期排序，因此您不必遍历整个树，并且需要更少的操作来查找范围内的节点。但恐怕您必须自己构建它。

更新:

这与您最初的问题有关。您的更新朝着全新的方向发展。

我认为你的方法不是一个好主意。您将无法处理如此大量的数据，至少无法以高性能的方式处理。为什么不根据客户端的真正需要更频繁地查询服务器。您甚至可以调整分辨率，因为您可能不需要所有点，具体取决于所选范围有多大。

尽管如此，如果我们可以假设您获得的数组已经按日期排序，您可以使用 Binary Search Algorithm 更快地找到匹配的值。 .

这基本上是如何工作的:您从数组的中间开始，如果找到的数字高于您要查找的数字，则检查数组的左半部分，如果较低，则检查正确的那一个。现在您检查新部分的中间。您继续这种模式，直到找到自己的值(value)。

二分搜索算法的可视化，其中 4 是目标值。

二分搜索算法的平均性能是O(log n)，所以这肯定会有帮助。

这只是给您一个想法的开始。您需要对其进行一些修改，以适应您的范围。