找到最大双精度值的最有效算法

在一组变量中找到最大值的最有效方法是什么？找到最大双精度值的最有效算法

我见过的解决方案，such as

private double findMax(double... vals) { 
double max = Double.NEGATIVE_INFINITY; 

for (double d : vals) { 
    if (d > max) max = d; 
} 
    return max; 
}

但是，什么是最有效的算法，这样做呢？

来源

2014-12-07 MarkusWillson

嗯似乎是一个很好的问题。因为我认为你总是需要迭代集合中的所有值，所以我会将它减少到“找到最好的方法”if（d> max）max = d' – rupps 2014-12-07 01:19:37

就运行时和Big-O而言你必须触摸/加载并比较每个元素至少一次，你的算法就是这样做的，所以如果复杂度来自加载或比较，看起来是非常优化的保持语言独立我会说在很多情况下并行化可能会有所帮助，即在GPU上并行简化操作是有效的。其他所有的东西都会依赖于我认为的语言和/或硬件（编译器）。 – Thomas 2014-12-07 01:25:25

保留集合并返回最后一项。 – 2014-12-07 01:27:28

假设列表中没有任何特定顺序的元素，那么您在问题中提到的算法是最优的。它必须查看每个元素一次，因此需要时间与列表的大小成正比，O(n)。

找不到比O(n)更低的上限的算法。

证明：假设存在一个算法可以在小于O(n)时间内找到列表的最大值。那么必须至少有一个它不检查的元素。如果算法选择该元素作为最大值，则对手可以为该元素选择一个值，使其小于被检查元素中的一个。如果该算法选择任何其他元素作为最大值，则攻击者可以为该元素选择一个值，使其大于其他元素。无论哪种情况，该算法都无法找到最大值。

来源

2014-12-07 02:52:36

编辑：这是我尝试回答，但请看看那里@BenVoigt提出了一种更好的方式来优化表达

你需要遍历整个名单至少一次
所以它应该是为if (d>max) max=d找到更有效的表达式的问题，如果有的话。

假设我们需要的一般情况，其中列表是无序（如果我们把它整理我们刚刚采摘的最后一个项目是在评论@IgnacioVazquez点），并研究一些关于分支预测（Why is it faster to process a sorted array than an unsorted array?，见第4个答案），看起来像

if (d>max) max=d;

可以更有效地改写为

max=d>max?d:max;

原因是，第一条语句通常被翻译成分支（尽管它完全依赖于编译器和语言，但至少在C和C++中，甚至在像Java这样的基于VM的语言中发生时发生了），而第二个被翻译成有条件移动。

如果预测出错（执行流水线必须重置），现代处理器会对分支造成严重损失，而条件移动是不影响流水线的原子操作。

列表中元素的随机性质（一个可能大于或小于当前最大值，具有相同的概率）会导致很多分支预测出错。

请参阅链接问题，以及所有这些和基准的良好讨论。

来源

2014-12-07 02:55:08 rupps

......也许如果您关闭了优化。并且不，两个分支都不会以相等的概率被采用，除非您的数据来自布朗流程。 – 2014-12-07 03:07:07

我很好奇，为什么不呢？如果列表完全未排序，那么编译器如何猜测哪种方式可以支持？这不正是我在链接问题中所描述的情况吗？ – rupps 2014-12-07 03:14:56

当你到达中途点的时候，有50％的机会再次出现这种情况。如果最大生活在每个鸽子洞中的机会相等，那么在迭代'i'处获得分支的概率是'1 /（1 + i）'。与子列表（0，i）的最大值位于最后一个槽中的机会相同。获得小而快的速度（尽管速度不够快）。 – 2014-12-07 03:17:25

如果列表未排序，则不能降低O(n)以下的复杂性...但您可以大大提高常数因子。使用SIMD。例如，在SSE中，您可以使用MAXSS指令在单个周期内执行4个比较+选择操作。展开循环一点，以降低循环控制逻辑的成本。然后在循环之外，找到SSE寄存器中捕获的四个值中的最大值。

这给了任何大小列表的好处...也使用多线程是非常大的列表。

来源

2014-12-07 03:29:20

找到最大双精度值的最有效算法

回答

相关问题