2
$\begingroup$

Sometimes I need to find the Min of a list, whose elements are lists (say of two elements, a pair). Given that Min does not have the option to indicate a sorting function like Sort, I elaborated the following approaches:

Cases[list, {_, Min[#[[2]] & /@ list]}]
Cases[list, {_, Min[list[[All]]]}]

First of all, I would like to see from you if there are other, better, methods, and the question is: testing the timing with the following code

n = 2000000;
list = Table[{RandomReal[], RandomReal[]}, {n}];
Timing[Cases[list, {_, Min[#[[2]] & /@ list]}]]
Timing[Cases[list, {_, Min[list[[All]]]}]]

the second method, that seems to be more efficient, sometimes gives no answer, like in the following:

0.262798

{1.0473, {{0.631835, 8.48582*10^-7}}}

{0.98226, {}}

why?

$\endgroup$
2
$\begingroup$

The fastest I can come up with is (by separating finding the minimum second value in each pair):

AbsoluteTiming@With[{min = Min@list[[All, 2]]}, Cases[list, {_, min}]]
(* {1.288129, {{0.555911, 1.05947*10^-6}}} *)

while MinimalBy takes much longer:

AbsoluteTiming@MinimalBy[list, #[[2]]&]
(* {2.074207, {{0.555911, 1.05947*10^-6}}} *)

Your second line is not giving any result, since you are searching for the smallest value in the whole list (even the first elements), which are just not matching the second element of a pair: Cases therefore returns empty.

Further explorations of timings

AbsoluteTiming@SortBy[list, #[[2]] &][[1]]
AbsoluteTiming@With[{min = Min@list[[All, 2]]}, Cases[list, {_, min}]]
AbsoluteTiming@MinimalBy[list, #[[2]] &]
AbsoluteTiming@Sort[list, #1[[2]] < #2[[2]] &][[1]]

gives:

(* SortBy:    {0.539054, {0.592838, 2.90821*10^-7}}   *)
(* Cases:     {1.298130, {{0.592838, 2.90821*10^-7}}} *)
(* MinimalBy: {2.084208, {{0.592838, 2.90821*10^-7}}} *)
(* Sort:      {73.714371, {0.592838, 2.90821*10^-7}}  *)

Note the abysmal performance of Sort vs. the fastest "built-in" solution in Mathematica v10, SortBy.

However: Mr. Wizard has found a much faster method! See here for his method, which can be adapted to your case as follows:

AbsoluteTiming@list[[Ordering[#[[2]] & /@ list, 1]]] (* {0.119012, {{0.592838, 2.90821*10^-7}}} *)

$\endgroup$
  • $\begingroup$ Isn't it stupid that Sort is faster than MinimalBy? SortBy[list, Last][[1]] $\endgroup$ – Kuba Mar 5 '15 at 9:05
  • $\begingroup$ @Kuba: Definitely! Also, SortBy is at least twice as fast as the Cases-approach (and much faster than Sort). Alas, the questioner only has v8. :( $\endgroup$ – Jinxed Mar 5 '15 at 9:17
  • $\begingroup$ Isn't SortBy here since V6? $\endgroup$ – Kuba Mar 5 '15 at 9:26
  • $\begingroup$ Thanks, I understood my error, but I cannot understand, from docs, the difference between Timing and AbsoluteTiming. $\endgroup$ – enzotib Mar 6 '15 at 9:18
2
$\begingroup$

The reason why the second method is failing is because you are looking for a pair whose second element is the minimum over the whole list (including all the first elements). This of course will fail whenever the global minimum is in the first position. The proper syntax is

Cases[list, {_, Min[list[[All, 2]]]}]

The speed improvement, on the other hand, is due to the absence of Map (/@)

AbsoluteTiming[Min[list[[All, 2]]]]

{0.023865, 5.98481*10^-7}

AbsoluteTiming[Min[#[[2]] & /@ list]]

{0.151333, 5.98481*10^-7}
$\endgroup$
2
$\begingroup$

Adapting listMaxArg from linked topic seems to be the fastest.

list = RandomReal[1, {10^6, 2}];

list[[Ordering[list[[All, 2]], 1]]] // AbsoluteTiming
{0.010000, {{0.817248, 6.71112*10^-7}}}
$\endgroup$
  • $\begingroup$ Yeah, the fastest, I wonder why? $\endgroup$ – enzotib Mar 6 '15 at 9:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.