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

在一組變量中找到最大值的最有效方法是什麼？找到最大雙精度值的最有效算法

我見過的解決方案，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

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

回答

相關問題