2

这是我的基本问题：我得到了一个currentTime. 例如，750 秒。我还有一个包含 1000 到 2000 个对象的数组，每个对象都有一个startTime、endTime和一个_id属性。鉴于currentTime，我需要找到具有 astartTime并且endTime在该范围内的对象——例如startTime : 740, endTime : 755。

在 Javascript 中执行此操作的最有效方法是什么？

对于初学者，我只是在做这样的事情：

var arrayLength = array.length; 
var x = 0;
while (x < arrayLength) {
 if (currentTime >= array[x].startTime && currentTime <= array[x].endTime) {
  // then I've found my object
 }
x++;
};

但我怀疑循环不是这里的最佳选择。有什么建议么？

编辑：为清楚起见，currentTime必须属于startTimeandendTime

我的解决方案：我的数据结构为我提供了一些好处，使我能够稍微简化一些事情。正如建议的那样，我已经完成了基本的二进制搜索，因为数组已经按 startTime 排序。我还没有完全测试过这个东西的速度，但我怀疑它会快一点，尤其是对于更大的阵列。

var binarySearch = function(array, currentTime) {

  var low = 0;
  var high = array.length - 1;
  var i; 

  while (low <= high) {
    i = Math.floor((low + high) / 2);

    if (array[i].startTime <= currentTime) {

      if (array[i].endTime >= currentTime ){
        // this is the one
        return array[i]._id; 

      } else {
        low = i + 1;
      }
    }

    else {
      high = i - 1;
    }
  } 

  return null;
}
4

6 回答 6

5

解决此问题的最佳方法取决于您必须调用搜索功能的次数。

如果你只调用你的函数几次，比如说m几次，去线性搜索。此函数调用的总体复杂度为O(mn).

如果你多次调用你的函数，而且我的意思是多次log(n)，你应该：

  • 排序你的数组O(nlogn)by startTime，然后endTime如果你有几个项目的值相等startTime
  • 进行二分搜索startTime <= x以查找带有的元素的范围。这意味着进行两次二进制搜索：一次用于start范围的，另一次用于end范围的。这是在O(logn)
  • 在里面做线性搜索[start, end]。您必须进行线性搜索，因为 的顺序startTimes不会告诉您有关endTimes. 这可以介于O(1)和之间O(n)，这取决于您的细分市场分布和x.

平均情况： O(nlogn)用于初始化和O(logn)每次搜索。

最坏情况：包含许多相等段或具有公共区间的段的数组，并在此区间中搜索。在这种情况下，您将O(nlogn)进行初始化和O(n + logn) = O(n)搜索。

于 2012-10-25T07:38:44.390 回答
2

听起来像是二分搜索的问题。

于 2012-10-25T07:22:07.863 回答
2

假设您的搜索数组是长期存在且相对恒定的，第一次迭代将按开始时间对所有数组元素进行排序（或者如果您不希望它们排序，则创建指向数组元素的排序开始时间的索引） .

然后，您可以有效地（使用二进制印章）打折那些开始得太晚的产品。然后对其他人进行顺序搜索会更快。

要获得更高的速度，请为开始时间和结束时间维护单独的排序索引。然后做前面提到的同样的操作，把那些开始太晚的都扔掉。

然后，对于剩下的，用结束时间索引把结束太早的都扔掉，剩下的就是你的候选名单。

但是，请确保这确实是需要的。两千个元素似乎不是一个巨大的数量，因此您应该为当前方法计时，并且仅在确实存在问题时才尝试优化。

于 2012-10-25T07:26:50.367 回答
1

从给出的信息中，无法判断最佳解决方案是什么。如果数组没有排序，循环是单个查询的最佳方式。沿着数组的单次扫描只需要 O(N)（其中 N 是数组的长度），而对其进行排序然后进行二分查找需要 O(N log(N) + log(N))，因此它在这种情况下会花费更多时间。

如果您在同一个大数组上有大量不同的查询，则分析看起来会大不相同。如果您对同一个数组有大约 N 个查询，排序实际上可能会提高性能，因为每个查询将花费 O(log(N))。因此，对于 N 个查询，它将需要 O(N log(N))（剩余的 log(N) 现在被删除），而未排序的搜索也将需要 O(N^2)，这显然更大。排序何时开始产生影响也取决于数组的大小。

当您相当频繁地更新数组时，情况也有所不同。更新一个未排序的数组可以在 O(1) 摊销中完成，而更新一个排序的数组需要 O(N)。因此，如果您有相当频繁的更新排序可能会受到伤害。

范围查询也有一些非常有效的数据结构，但同样取决于实际使用情况是否有意义。

于 2012-10-25T07:38:28.777 回答
1

如果数组未排序，则您的方法是正确的。

不要陷入先对数组排序，然后再应用搜索的思维陷阱。

使用您尝试的代码，您的复杂度为O(n)，其中n是元素的数量。

如果先对数组进行排序，则首先会陷入O(n log(n))的复杂度（与排序算法相比），在average case.

然后你必须应用二进制搜索，它以O(log_ 2(n) - 1)的平均复杂度执行。

因此，在平均情况下，您最终会花费：

O(n log(n) + (log_2(n) - 1))

而不仅仅是O(n)。

于 2012-10-25T07:40:50.767 回答
1

区间树是一种数据结构，如果总共有 n 个区间，则允许在 O(lg n) 时间（平均和最坏情况）内回答此类查询。构造数据结构的预处理时间是O(n lg n)；空间是 O(n)。增广区间树的插入和删除时间为 O(lg n) 。如果 m 个区间覆盖一个点，则回答所有区间查询的时间是 O(m + lg n)。 维基百科描述了几种区间树；例如，居中的区间树是一棵三叉树，每个节点存储：

• 一个中心点
• 指向另一个节点的指针，该节点包含完全位于中心点左侧的所有区间
• 指向另一个节点的指针，该节点包含完全位于中心点右侧的
所有区间 • 与中心点重叠的所有区间按其起点排序
• 与中心点重叠的所有区间按其终点排序

请注意，对于找到一个区间来覆盖一个点的平均查询和最坏情况查询，区间树的复杂度为 O(lg n)。先前的答案具有相同的 O(n) 最坏情况查询性能。之前的几个答案声称他们有 O(lg n) 平均时间。但他们都没有提供证据；相反，他们只是断言平均性能是 O(lg n)。这些先前答案的主要特征是使用二进制搜索开始时间。然后有人说使用线性搜索，而另一些人说使用二分搜索，用于结束时间，但没有明确说明后一种搜索结束的间隔集。他们声称有 O(lg n) 的平均性能，但这只是一厢情愿。正如在标题Naive Approach下的维基百科文章中指出的那样，

一种天真的方法可能是构建两棵平行树，一棵按起点排序，一棵按每个区间的终点排序。这允许在 O(log n) 时间内丢弃每棵树的一半，但结果必须合并，需要 O(n) 时间。这给了我们 O(n + log n) = O(n) 的查询，这并不比暴力破解好。

于 2012-10-25T17:37:46.683 回答