确定非零最小值的最快方法

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'和'n',如果'm'元素中的值为零,则交换它们.

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

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

配对xchg操作可以并行执行,与严格顺序执行相比,可将时间成本降低40%.当我们完成时,数组中的任何非零元素将按升序排序.最小值元素将在[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]
}