# 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]] >= #2[[2]]) &];

initialvls = tabsort[[1]];


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... Commented Dec 2, 2014 at 18:30
• Take a look at MaxBy here and MaximalBy introduced in version 10. Commented Dec 2, 2014 at 19:21
• @Szabolcs, thanks ;) Commented 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]]][[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
Commented 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 ;) Commented 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[1];
tabint = Table[{i,
Round[RandomReal[{1, RandomReal[{2, 3}]}], .005]}, {i, 1, n}];

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


{0.184576, {506, 2.98}}

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


{0.005880, {9033, 2.98}}

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


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

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


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

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