wolfram-mathematica - 有没有更快的方法来找到最小值和最大值？

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

我认为它比 Leonid 的版本快一点，因为Do它比 快一点For，即使在编译代码中也是如此。

不过，归根结底，这是您在使用高级函数式编程语言时所受到的性能影响的一个示例。

回应 Leonid 的补充：

我不认为该算法可以解释所有的时间差异。很多时候，我认为，无论如何都会应用这两种测试。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 的答案都至少快 7 倍，在 v.7 中未编译。对于长列表，25000 个元素，Mark 的速度提高了 19.6 倍，这变得更糟，但即使在这个长度下，这个解决方案也只需要大约 0.05 秒的时间来运行。

但是，我不会将其{Min[#], Max[#]}&视为一种选择。未编译的它比 Mark 的短列表快 1.7 倍，长列表快近 15 倍（分别比Fold解决方案快 8 倍和近 300 倍）。

不幸的是，对于 Leonid's 或 Mark's 答案的编译版本，我无法获得好的数字{Min[#], Max[#]}&，相反，我收到了许多难以理解的错误消息。事实上，{Min[#], Max[#]}&增加了执行时间。不过，该Fold解决方案得到了显着改进，并且花费了 Leonid 答案未编译时间的两倍。

编辑：出于好奇，这里有一些未编译函数的计时测量 -

每个函数都用于 100 个在水平轴上指定长度的列表，平均时间（以秒为单位）是垂直轴。按时间升序，曲线是{Min[#], Max[#]}&、Mark 的答案、Leonid 的第二个答案、Leonid 的第一个答案以及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两个Mins 大致相同且最低。实际上，我希望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]}（包括杆位让分）大约为 0.3 s，0.1 水平适用于 Mark 方法；其他的都差不多。