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... – An old man in the sea. Dec 2 '14 at 18:30
  • 1
    Take a look at MaxBy here and MaximalBy introduced in version 10. – Szabolcs Dec 2 '14 at 19:21
  • @Szabolcs, thanks ;) – An old man in the sea. Dec 2 '14 at 19:47
up vote 4 down vote accepted
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 Dec 3 '14 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 ;) – An old man in the sea. Dec 2 '14 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}}}

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

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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