# How to pick the maximum of a list? Improving efficiency

I need to find the element of a list, with the highest weight.

Example:

  {{1, 3.80737}, {2, 4.48538}, {3, 2.64947}, {4, 1.06387}, {5,
5.07804}, {6, 1.33265}, {7, 9.11426}, {8, 6.90628}, {9,
5.34919}, {10, 3.90156}}


the program should pick {7, 9.11426}.

I've done the following working example:

n=50;
tabint = Table[{i, RandomReal[{1, n}]}, {i, 1, n}] (*to generate a random table. This command does not matter for the efficiency of my programme. It's only for this example*)

tabsort = Sort[tabint, (#1[] >= #2[]) &];

initialvls = tabsort[];


The thing that bothers me with my code is the sort. It seems that I lose time in sorting the whole list than those I would need to if just looking for the maximum weight. I bet there is a faster way to do this.

Any help would be appreciated.

P.S.: I've tried to find other questions similar to this one, but the answers don't seems to be applicable to my problem. May be wrong though...

• @MathLind, thanks for the interest. Unfortunately it does not help. tabint in this example has this shape, but in my programme the first elements are unknown... Dec 2, 2014 at 18:30
• Take a look at MaxBy here and MaximalBy introduced in version 10. Dec 2, 2014 at 19:21
• @Szabolcs, thanks ;) Dec 2, 2014 at 19:47

lst = {{1, 3.80737}, {2, 4.48538}, {3, 2.64947}, {4, 1.06387}, {5, 5.07804},
{6, 1.33265}, {7, 9.11426}, {8, 6.90628}, {9, 5.34919}, {10, 3.90156}};

f = #[[Ordering[#[[All, 2]], -1]]][] &;
f@lst
(* {7, 9.11426} *)


Timing:

n = 500000;
tabint = Table[{i, RandomReal[{1, n}]}, {i, 1, n}];

f@tabint // AbsoluteTiming
(* {0.017019,{378308,499999.}} *)

First@Cases[#, {_, Max@#[[All, 2]]}] &@tabint // AbsoluteTiming
(* {0.130194,{378308,499999.}} *)

• In my computer this is 10x faster than (what to me seems) the canonical way MaximalBy[tabint, Last] // AbsoluteTiming - very impressive! (+1)
– gpap
Dec 3, 2014 at 23:54

Without sorting:

list = {{1, 3.80737}, {2, 4.48538}, {3, 2.64947}, {4, 1.06387}, {5, 5.07804}, {6, 1.33265}, {7, 9.11426}, {8, 6.90628}, {9, 5.34919}, {10, 3.90156}}

First@Cases[#, {_, Max@#[[All, 2]]}]& @ list
(* {7, 9.11426} *)

• +1 Seems pretty nice. I'll just wait for the chance that there are better answers. If not, yours will be accepted ;) Dec 2, 2014 at 18:33

In general, there could be one or more elements with the highest weight so the result would be a list of elements. If you don't care about finding all such cases, your method can be made more efficient by using SortBy. However, the index returned may be different--but the maximun weight will be the same.

n = 10000;
SeedRandom;
tabint = Table[{i,
Round[RandomReal[{1, RandomReal[{2, 3}]}], .005]}, {i, 1, n}];

Sort[tabint, (#1[] >= #2[]) &][] // Timing


{0.184576, {506, 2.98}}

SortBy[tabint, Last][[-1]] // Timing


{0.005880, {9033, 2.98}}

(max = Max[tabint[[All, 2]]];
Select[tabint, #[] == max &]) // Timing


{0.010959, {{506, 2.98}, {9033, 2.98}}}

(max = Max[tabint[[All, 2]]];
Cases[tabint, _?(#[] == max &)]) // Timing


{0.012999, {{506, 2.98}, {9033, 2.98}}}

• Why does SortBy[tabint, Last][[-1]] beat Sort[tabint, (#1[] >= #2[]) &][] so much? After all, they all need to do sorting. Dec 3, 2014 at 3:45
• @hengxin - Don't know, someone from WRI would have to answer. Dec 3, 2014 at 4:31