有沒有更快的方法來找到最小值和最大值？

Question

我經常寫：{Min@#, Max@#} &

然而，這似乎效率低下，因爲表達式必須掃描兩次，一次找到最小值，一次找到最大值。有沒有更快的方法來做到這一點？表達式通常是張量或數組。

Answer 1

這會比較慢。

minMax = Compile[{{list, _Integer, 1}}, 
    Module[{currentMin, currentMax}, 
    currentMin = currentMax = First[list]; 
    Do[ 
    Which[ 
     x < currentMin, currentMin = x, 
     x > currentMax, currentMax = x], 
    {x, list}]; 
    {currentMin, currentMax}], 
    CompilationTarget -> "C", 
    RuntimeOptions -> "Speed"]; 
v = RandomInteger[{0, 1000000000}, {10000000}]; 
minMax[v] // Timing 

我覺得它比獅子座的版本快一點，因爲Do有點比For快，即使是在編譯的代碼。

但是，最終，這是使用高級功能編程語言時所遇到的那種性能打擊的例子。

加成響應獅子座：

我不認爲，該算法可以佔到全部的時間差。 很多往往不是，我認爲，無論如何這兩項測試都會被應用。然而，Do和For之間的差異是可測量的。

cf1 = Compile[{{list, _Real, 1}}, 
    Module[{sum}, 
    sum = 0.0; 
    Do[sum = sum + list[[i]]^2, 
    {i, Length[list]}]; 
    sum]]; 
cf2 = Compile[{{list, _Real, 1}}, 
    Module[{sum, i}, 
    sum = 0.0; 
    For[i = 1, i <= Length[list], 
    i = i + 1, sum = sum + list[[i]]^2]; 
    sum]]; 
v = RandomReal[{0, 1}, {10000000}]; 
First /@{Timing[cf1[v]], Timing[cf2[v]]} 

{0.685562, 0.898232} 

Answer 2

在Mathematica編程實踐中，我認爲這個速度是最快的。我看到試圖使其更快內MMA是使用Compile與C編譯目標，如下的唯一方法：

getMinMax = 
Compile[{{lst, _Real, 1}}, 
    Module[{i = 1, min = 0., max = 0.}, 
     For[i = 1, i <= Length[lst], i++, 
     If[min > lst[[i]], min = lst[[i]]]; 
     If[max < lst[[i]], max = lst[[i]]];]; 
     {min, max}], CompilationTarget -> "C", RuntimeOptions -> "Speed"] 

然而，即使這似乎是比你的代碼有點慢：

In[61]:= tst = RandomReal[{-10^7,10^7},10^6]; 

In[62]:= Do[getMinMax[tst],{100}]//Timing 
Out[62]= {0.547,Null} 

In[63]:= Do[{Min@#,Max@#}&[tst],{100}]//Timing 
Out[63]= {0.484,Null} 

你可能可以完全用C編寫函數，然後編譯並加載爲DLL - 這樣可以消除一些開銷，但我懷疑你會贏得超過百分之幾 - 不值得IMO的努力。

編輯

有趣的是，你可能會顯著增加與手動公共子表達式消除（lst[[i]]這裏）編譯解決方案的速度：

getMinMax = 
Compile[{{lst, _Real, 1}}, 
    Module[{i = 1, min = 0., max = 0., temp}, 
    While[i <= Length[lst], 
     temp = lst[[i++]]; 
     If[min > temp, min = temp]; 
     If[max < temp, max = temp];]; 
     {min, max}], CompilationTarget -> "C", RuntimeOptions -> "Speed"] 

比{Min@#,Max@#}快一點。

Answer 3

對於數組，你可以做最簡單的事情功能和使用

Fold[{Min[##],Max[##]}&, First@#, Rest@#]& @ data 

不幸的是，沒有速度惡魔。即使對於短列表，5個元素，所有Leonid's answers和Mark's answer至少快7倍，在v.7中未編譯。對於長列表，25000個元素，Mark的速度提高了19.6倍，但這個長度只有0.05秒左右。

但是，我不會計算出{Min[#], Max[#]}&作爲選項。未編譯的速度比Mark的短名單快1.7倍，長列表的速度快近15倍（分別比Fold解決方案快8倍和近300倍）。

不幸的是，我無法獲得{Min[#], Max[#]}&，Leonid's或Mark的答案的編譯版本的好數字，而是我得到了無數難以理解的錯誤消息。實際上，{Min[#], Max[#]}&的執行時間增加了。儘管如此，Fold解決方案也有了顯着的改進，並且花費了Leonid答案未編譯時間的兩倍。

編輯：爲好奇，這裏的未編譯的功能的一些定時測量 -

的每個功能是在水平軸上，並且平均時間指定的長度的100列出了用於，以秒爲單位，是垂直軸。按照時間遞增的順序，曲線是{Min[#], Max[#]}&，馬克的答案，列昂尼德的第二個答案，列昂尼德的第一個答案，以及從上面的Fold方法。

Answer 4

對於所有正在進行計時的人，我想警告您，執行順序非常重要。例如，看一下下面的兩個微妙的不同時間測試：

（1）

res = 
Table[ 
    a = RandomReal[{0, 100}, 10^8]; 
    { 
    Min[a] // AbsoluteTiming // First, Max[a] // AbsoluteTiming // First, 
    Max[a] // AbsoluteTiming // First, Min[a] // AbsoluteTiming // First 
    } 
    , {100} 
    ] 

古怪的人在這裏是最後Min

（2）

res = 
Table[ 
    a = RandomReal[{0, 100}, 10^8]; 
    { 
    Max[a] // AbsoluteTiming // First, Min[a] // AbsoluteTiming // First, 
    Min[a] // AbsoluteTiming // First, Max[a] // AbsoluteTiming // First 
    } 
    , {100} 
    ] 

這裏，第一個Max發現最高時機，第二個最高時機爲max，兩個Min s大致相同且最低。實際上，我預計Max和Min需要大約相同的時間，但他們不需要。前者似乎比後者多花50％的時間。杆位也似乎有50％的讓分。

現在與馬克和列昂尼德給出的算法進行比較：

res = 
Table[ 
    a = RandomReal[{0, 100}, 10^8]; 
    { 
    {Max[a], Min[a]} // AbsoluteTiming // First, 
    {Min@#, Max@#} &@a // AbsoluteTiming // First, 
    getMinMax[a] // AbsoluteTiming // First, 
    minMax[a] // AbsoluteTiming // First, 
    {Min[a], Max[a]} // AbsoluteTiming // First 
    } 
    , {100} 
    ] 

在這裏，我們找到0.3 S爲{最大值[A]，閔[A]}（其中包括杆位障礙），.1水平是Mark的方法;其他人都差不多。