wolfram-mathematica - 最小値と最大値の両方を見つけるより速い方法はありますか?

Question

多くの場合、私は次のように書いています。{Min@#, Max@#} &

しかし、最小値を見つけるために 1 回、最大値を見つけるために 1 回、式を 2 回スキャンする必要があるため、これは非効率的です。これを行うより速い方法はありますか？多くの場合、式はテンソルまたは配列です。

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よりも少し速いため、Leonid のバージョンよりも少し速いと思います。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 のすべての回答とMark の回答は、v.7 でコンパイルされていない場合でも、少なくとも 7 倍高速です。25000 要素の長いリストの場合、Mark のほうが 19.6 倍高速であるため、これはさらに悪化しますが、この長さでも、このソリューションの実行には約 0.05 秒しかかかりませんでした。

{Min[#], Max[#]}&ただし、オプションとして数えません。コンパイルされていない場合、短いリストではマークの 1.7 倍、長いリストでは 15 倍近く高速でした (Foldソリューションよりもそれぞれ 8 倍と 300 倍近く高速です)。

残念ながら、{Min[#], Max[#]}&Leonid の回答、または Mark の回答のコンパイル済みバージョンの適切な数値を取得できませんでした。代わりに、理解できないエラー メッセージが多数表示されました。実際、{Min[#], Max[#]}&実行時間は増加しました。ただし、Foldソリューションは劇的に改善され、Leonid の回答の未コンパイル時間の 2 倍の時間がかかりました。

編集：好奇心のために、コンパイルされていない関数のタイミング測定値を次に示します-

各関数は、横軸に指定された長さの 100 個のリストで使用され、平均時間 (秒単位) が縦軸です。時間の昇順で、曲線は{Min[#], Max[#]}&、マークの答え、しし座の 2 番目の答え、しし座の最初の答え、Fold上から方法です。

Answer 4

タイミングを行っているすべての人に、実行の順序が非常に重要であることを警告したいと思います。たとえば、次の 2 つの微妙に異なるタイミング テストを見てください。

(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、2 番目が 2 番目に高いタイミングmax、および 2 つMinの がほぼ同じで最も低いタイミングが見つかります。実際、私は とがほぼ同じ時間かかると思っていましたが、そうではありませんでしMaxた。Min前者は後者よりも 50% 長い時間がかかるようです。ポールポジションも50%のハンディキャップがあるようです。

Mark と Leonid によって与えられたアルゴリズムとの比較:

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}
  ]

ここで、{Max[a], Min[a]} (ポール ポジションのハンディキャップを含む) の約 .3 秒を見つけます。.1 レベルはマークの方法です。他はほぼ同じです。