c++ - 确定非零最小值的最快方法

Question

拥有一个由例如 4 个整数组成的数组，如何以最快的方式确定它是非零最小值？

Answer 1

除非您在将元素添加到数组时保持最小值，或者将数组保持在排序顺序 - 我看不到其他解决方案，只能迭代每个成员以确定最小值。

没有“快速”的方法来测试每个成员。

一般来说，我建议不要优化某些东西，除非它实际上被证明很慢。程序的旧规则将 90% 的时间花在 10% 的代码上，通常是正确的。程序员有 99.99% 的可能性优化代码而不是那 10% 的规则也是如此。

分析您的代码 - 分析您的代码 - 分析您的代码

Answer 2

这个问题有一个并行的解决方案，但它可能不值得付出努力。

首先，我们xchg(m, n)在数组a上定义一个操作：

xchg(m, n) => ((a[m] > a[n] && a[n] != 0) || a[m] == 0) ? swap(a[m],a[n])

如果两个元素“m”和“n”都包含非零值，则此操作按升序对它们进行排序，或者如果“m”元素中的值为零，则交换它们。

接下来我们执行一组五个这样的操作，如下所示：

xchg(0,2) xchg(1,3)
xchg(0,1) xchg(2,3)
xchg(1,2)

成对的xchg操作可以并行执行，与严格的顺序执行相比，时间成本降低了 40%。完成后，数组中的任何非零元素都将按升序排序。最小值元素将在 a[0] 中。如果该值为零，则数组中没有非零值。

该解决方案利用了排序网络 ( http://en.wikipedia.org/wiki/Sorting_network ) 提供的固有并行性，但是对 4 个元素的顺序扫描也使用不超过三个比较操作，并且关键需要一半平均存储写入：

顺序扫描

int v = a[0]
for (n = 1; n < 4; n++) {
   if ((a[n] < v && a[n] != 0 ) || v == 0) v = a[n]
} 

Answer 3

取决于输入。如果数组未排序，那么您将不得不遍历整个数组。如果数组已排序，那么您只需要循环直到找到不为零的东西 - 它要短得多。

Answer 4

如果我们正在考虑微优化，那么计算速度可能会比min(min(a,b),min(c,d))在min(min(min(a,b),c),d)现代乱序处理器上更快，因为顺序依赖性较小：在前者中，处理器可以并行独立计算，如果min(a,b)它min(c,d)有足够的可用执行单元。这是假设处理器具有条件移动指令，因此计算min不需要分支。

Answer 5

那么最快的编码方式是std::min({a,b,c,d}).

更严肃的一点是：如果您的应用程序在诸如取大量值中的最小值之类的事情上遇到瓶颈，更好的解决方案可能是找到一种方法将最小查找任务分成多个部分并发送到 GPU（或多个线程） ，然后可以同时进行许多最小查找计算。

并行性可能比尝试在汇编中编写最小函数更有帮助。