Is there a faster way to find the Min and Max values?

Question

Often I wrote: { Min@ #, Max@ #} &

However, this seems inefficient since the expression must be scanned twice, once to find the minimum value, and once to find the maximum value. Is there a faster way to do this? An expression is often a tensor or an array.

Answer 1

It’s a little beating.

 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 

I think this is slightly faster than the Leonid version, because Do slightly faster than For , even in compiled code.

Ultimately, this is an example of what performance you use when using a high-level programming language.

Addition in response to Leonid:

I do not think that the algorithm can take into account all the time difference. Much more often than it seems to me, both tests will be applied in any case. However, the difference between Do and For measurable.

 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

I think it is as fast as using Mathematica programming programs. The only way I tried to make it faster in mma is to use Compile to compile C as follows:

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

However, even this looks a little slower than your code:

 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} 

You can probably completely write a function in C and then compile and load as a dll - you can eliminate some overhead in this way, but I doubt that you will win more than a few percent - it’s not worth the effort of IMO.

EDIT

Interestingly, you can significantly increase the speed of the compiled solution using the manual general exclusion of the subexpression ( lst[[i]] here):

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

slightly faster than { Min@ #, Max@ #} .

Answer 3

For an array, you can do the simplest functional thing and use

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

Unfortunately, this is not a demon of speed. Even for short lists, 5 elements, all answers of Leonid and Mark the answer , at least 7 times faster, are not compiled in v.7. For long lists, 25,000 items, this gets worse when Mark was 19.6 times faster, but even at that length this solution took only about 0.05 seconds to run.

However, I would not consider {Min[#], Max[#]}& as an option. Uncompiled, it was 1.7 times faster than Mark for a short list and almost 15 times faster for long lists (8 times and almost 300 times faster than the Fold solution).

Unfortunately, I could not get good numbers for the compiled versions of the answers {Min[#], Max[#]}& , Leonid or Mark, instead I got a lot of obscure error messages. In fact, {Min[#], Max[#]}& increased at runtime. However, Fold solution improved significantly and took twice as much time as Leonid responded to "endless times."

Edit : for the curious, here are temporary measurements of uncompressed functions -

Each function was used in 100 lists of lengths indicated on the horizontal axis, and the average time in seconds was the vertical axis. In ascending order of time, the curves {Min[#], Max[#]}& , Mark’s answer, Leonid’s second answer, Leonid’s first answer and the Fold method above.

Answer 4

For everyone involved in timing, I would like to warn you that the execution order is extremely important. For example, consider the following two subtle time tests:

(one)

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

The odd man here is the last 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} ] 

Here, the highest timeline is found for the first Max , the second is the highest for the second Max , and two Min approximately the same and the lowest. In fact, I would expect that Max and Min will take about the same time, but they will not. The former, apparently, takes 50% more time than the latter. It seems that the position of the pole has a 50% disadvantage.

Now a comparison with the algorithms given by Mark and 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} ] 

Here we find about 0.3 s for {Max [a], Min [a]} (which includes a checkmark on the pole), level .1 is for the Mark method; all the rest are about the same.