How to pick the maximum of a list? Improving efficiency

Question

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...

Answer 1

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.}} *)

Answer 2

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} *)

Answer 3

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