在列表中获得大于x的第一个值的有效方法？

我有两个排序阵列，Haystack和Needles。我需要遍历Needles，并且每次都会找到Haystack中的第一个点，其值大于Needle，以便执行下一步。在列表中获得大于x的第一个值的有效方法？

例如：

double [] dHaystack = { 1.2, 2.6, 7.0, 9.3, 19.4 } 
double [] dNeedles = { 1.4, 6.4, 6.5, 7.0, 10.3 } 

// expected indices  0 1 1 2 3

所以我应该得到的指数比针值等于或低于第一指标。

显而易见的方法是从干草堆开始迭代每个针，或者从最后找到的索引开始迭代（因为Needles也是排序的）。

但我的大脑的一部分正在喊着“平分！”。在这里实际上是否会更快，因为编译器会比简单的块读取和迭代更难以优化？它需要一个令人难以置信的长草垛值得吗？

来源

2011-02-14 Phil H

我的大脑高喊着“榜样”，没有它就没有思考要优化什么。其他然后，从上次找到的接缝搜索良好。我不会试图聪明的编译器。通常这是非常好的 – 2011-02-14 09:34:11

你需要考虑的情况下，

N * LG（M）< N + M，

其中n是针和M的大小是草堆的大小。

因此，这一切都取决于n和m值的各种组合。

来源

2011-02-14 09:41:12

的std :: UPPER_BOUND会给你的迭代器第一个元素严格大于或收集的“结束”，如果没有人申请

UPPER_BOUND花费的开始和结束，最终成为一个过去的结束迭代器集合。如果您正在遍历不断增加的搜索值列表，那么您当然不需要遍历整个集合，但是您的“开始”可以进一步向右移动。

当然，对于只有5个元素的干草堆，使用什么搜索算法并不重要，但是如果它变得非常大，使用线性搜索可能会非常缓慢，特别是如果针数很少的话。

这是一种情况，它确实很重要的两种尺寸。例如，如果您的搜索空间N很大，但搜索的项目数量（M）很小，那么O（M log N）确实小得多。（例如，M = 20，N = 16K，则log N = 15且M log N为300）与O（M + N）相比较，在这种情况下为16K。如果M大小与N大致相同，那么O（M log N）实际上比O（N）差很多。

因此，根据您的集合的大小，您可以选择使用哪种算法。

来源

2011-02-14 09:35:25 CashCow

PO知道这一点。他只是想知道什么时候平分是值得的 – 2011-02-14 09:36:40

显而易见的方法是从最后找到的索引（因为针也被排序）迭代... ...。

是的。

但是我的大脑的一部分正在喊“平分！”。在这里实际上是否会更快，因为编译器会比简单的块读取和迭代更难以优化？它需要一个令人难以置信的长草垛值得吗？

我不认为编译器优化是一个问题（它只是消除了不必要的工作），以至于实际固有的必要工作量。如果两组的尺寸相似，那么我会坚持明显的做法。如果草垛比针的尺寸大得多，则二等分甚至插值可能会产生稍好的性能。除非这对你的应用程序是至关重要的，否则你不太可能注意到它们之间的差异，如果是这样的话，你应该进行基准测试，特别是因为你大概可以快速使用std::set和上限或下限来获得工作实现（我永远不会记得我会需要 - 不要经常使用），也许使用最后一个位置作为启动位置的提示，如果你的库支持。

来源

2011-02-14 09:41:08

使用std :: upper_bound，它是O（log n）用于随机访问迭代器，并提供了您在最短和最简单代码中所需的内容。

在担心分钟性能之前，请测试您当前的代码（也可能是测试选项）instead of making assumptions。尤其要注意，您可以从每次迭代中最后找到的索引开始搜索（第一个参数为upper_bound）。

// Available in Boost, C++0x, and many other places. Implementation copied 
// here for the sake of the example. 
template<class T, int N> 
T* end(T (&a)[N]) { 
    return a + N; 
} 

void example() { 
    double haystack[] = {1.2, 2.6, 7.0, 9.3, 19.4}; 
    double needles[] = {1.4, 6.4, 6.5, 7.0, 10.3}; 
    double *begin = haystack; 
    for (double *n = needles; n != end(needles); ++n) { 
    double *found = std::upper_bound(begin, end(haystack), *n); 
    if (found == end(haystack)) break; 
    std::cout << *n << " at index " << (found - haystack) << '\n'; 
    begin = found; 
    } 
}

来源

2011-02-14 09:57:18

在列表中获得大于x的第一个值的有效方法？

回答

相关问题