What's the best way to select the maximum one

问题:

In Mathematica, Max[] is the most efficient function to get the maximum number in a list of numbers, but how do I find the list with the maximum last element in a list of lists? e.g. the 2-d coordinate with the biggest x part in a series of coordinates.

My best try is SortBy, but obviously I don't need the program to sort my list, only the maximum one I need.

回答1:

Perhaps:

list = {{4, 3}, {5, 10}, {-2, 1}, {3, 7}}

Reverse /@ Take[#, Ordering[#, -1]] &@(Reverse /@ #) &@ list
(*
-> {{5, 10}}
*)

Exploiting the fact that Ordering[ ] orders lists by their first element

Edit

Or much better (I think):

Take[#, Ordering[Last /@ #, -1]] &@ list

Edit

Also:

#[[Ordering[#, -1, Last@#2 > Last@#1 &]]] &@list

Edit

Perhaps faster:

#[[First@Position[#, Max@#] &@(Last /@ #)]] &@list

回答2:

Here is my approach using Pick

maxBy[list_, n_] := With[{s = list[[All, n]]}, Pick[list, s, Max[s]]]

maxBy[{{4, 3}, {5, 10}, {-2, 1}, {3, 7}}, 2]

(* output: 
  {{5, 10}}  
*)

This version works on any number of elements per sublist provided n is less than or equal to the length of the shortest sublist.

Timings for this version on my machine

list2 = RandomInteger[{-10^7, 10^7}, {10^6, 2}];
list3 = RandomInteger[{-10^7, 10^7}, {10^6, 3}];
list9 = RandomInteger[{-10^7, 10^7}, {10^6, 9}];

maxBy[list2, 2]; // Timing
maxBy[list3, 2]; // Timing
maxBy[list9, 2]; // Timing

(* output: 
  {0.030341, Null}  
  {0.030912, Null}  
  {0.033313, Null}  
*)

Compared to David's code

maxBy[list2, 2]; // Timing
maxBy[list3, 2]; // Timing
maxBy[list9, 2]; // Timing

(* ouput:
  {0.186175, Null}  
  {0.184989, Null}  
  {0.262018, Null}  
*)

Yoda's code

maxBy[list2, 2]; // Timing
maxBy[list3, 2]; // Timing
maxBy[list9, 2]; // Timing

(* ouput:
  {0.944016, Null}
  {0.83094, Null}
  {0.874126, Null}
*)

And belisarius' code

Reverse /@ Take[#, Ordering[#, -1]] &@(Reverse /@ #) &@list2; // Timing
Take[#, Ordering[Last /@ #, -1]] &@list2; // Timing
#[[Ordering[#, -1, Last@#2 > Last@#1 &]]] &@list2; // Timing
#[[First@Position[#, Max@#] &@(Last /@ #)]] &@list2; // Timing 

(* output:
  {0.211016, Null}
  {0.099253, Null}
  {2.03415, Null}
  {0.266934, Null}
*)

回答3:

How about this function (defined here only for 2D lists):

maxBy = Module[{pattern = Reverse@Insert[{Max@#1[[All, #2]]}, _, #2]},
               Cases[#1, pattern]] &

Example:

list = {{4, 3}, {5, 10}, {20, 1}, {3, 7}};

maxBy[list, 1]    
Out[1]= {{20, 1}}

maxBy[list, 2]  
Out[2]= {{5, 10}}

回答4:

Here's an approach that relies on Transpose:

maxBy = #1[[Position[t = Transpose[#1][[#2]], Max[t]][[All, 1]]]] &;

For example: list = {{4, 3}, {5, 10}, {20, 1}, {3, 7}};

maxBy[list, 1]
(* {{20, 1}}   *)

maxBy[list, 2]
(* {{5, 10}} *)

It can handle more than two elements per sublist, provided that the sublists are all the same length.

r:=RandomInteger[{-10^5,10^5}];
list3=Table[{r,r,r},{j,10^2}];             (* 3 numbers in each sublist *)
list9=Table[{r,r,r,r,r,r,r,r,r},{j,10^2}]; (* 9 numbers *)

maxBy[list3, 2]     (* Find max in position 2 of list3 *)
(* {{-93332, 99582, 4324}}  *)

maxBy[list9, 5]     (* Find max in position 5 of list9 *)
(* {{7680, 85508, 51915, -58282, 94679, 50968, -12664, 75246, -82903}} *)

Of course, the results will vary according to the random numbers you have generated.

Edit

Here's some timing data for large lists. SortBy is clearly slower. but doesn't seem as influenced by the number of elements in each sublist. First, my maxBy code followed by SortBy:

Using the same list2, here's some timing data for Yoda's code. Although his routine is also called maxBy, it is his that produced the output that follows:

Again, with the same list2, some data for Belisarius' code:

His second suggestion is the fastest of all tested.

回答5:

Not the most efficient but simpler?

max = Max@list[[All, -1]];
Cases[list, {_, max}]

or

max = Max@list3[[All, -1]];
Cases[list3, {_,_, max}]

Usage

list = {{40, 3}, {5, 10}, {-2, 1}, {3, 10}}

max = Max@list[[All, -1]];
Cases[list, {_, max}]

Output:

{{5, 10}, {3, 10}}

回答6:

After reading some documentations and doing a few experiments, I managed to get a clearer view of this problem.

I actually was wondering why Max[] seemed intentionally avoid providing directives that make it return not only the max element itself, but also its position. After all, providing position doesn't change the O(n) complexity of the algorithm. For example, imagine:

In[1]:= Max[{991, 993, 992}, ReturnPosition -> True]

Out[1]= {2}

If that could be done, you can simply use the code below to solve my problem:

list[[Max[list[[All, -1]], ReturnPosition -> True]]]

But now I realize that the system function Max[] is not designed for finding the max element in lists. You can tell that the Wolfram team obviously made Max[] more like a traditional max function in mathematics ― it does simple symbolic simplifications, it automatically flatten out all lists, it can be in a plotable function, and most importantly, it's Orderless:

In[2]:= Attributes[Max]

Out[2]= {Flat, NumericFunction, OneIdentity, Orderless, Protected}

Which makes positions meaningless. In a word, it treats all the lists inside as mathematical sets.

So philosophically it's not trivial for Mathematica to compute this. All I need to do is to "DIY" a function with the O(n) complexity and can do the job. I think TomD is heading the right direction, although I prefer:

maxLast[l_] := Cases[l, {___, Max[Last/@l]}]

And Heike (黑客?) adopted Pick which may have better techniques especially designed for selecting elements, but there must be no virtual difference in the complexity of the algorithm. And I may rewrite it this way: (fewer names and heads, faster the speed)

maxLast[l_] := Pick[l, #, Max[#]] &[Last /@ l]

They're both good answers.