12
$\begingroup$

Having millions of numbers in a list, I want to take top K occurrences. MMA Commonest is very slow so I write my own versions:

a=RandomInteger[{1,1000000},50000000];

MyCommonest1[a_,n_]:=Take[SortBy[Tally[a],Last],-n]

MyCommonest2[a_,n_]:=(b=Tally[a];Take[b[[Reverse[Ordering[b[[All,2]]]]]],n])

MyCommonest3[a_,n_]:=(b=Tally[a];b[[Take[Ordering[b[[All,2]]],-n]]])

MyCommonest4[a_,n_]:=Take[SortBy[Tally[a],-#[[2]]&],n]

Timings:

1.68
1.12
1.15
1.70

Can it be any faster?

Edit

The C# counterpart of this problem in SO is here.

$\endgroup$
11
$\begingroup$

The only improvement I can think of:

comm[a_, n_] := #[[ Ordering[#[[All, 2]], -n] ]] & @ Tally[a]

Or if you don't want the counts:

comm2[a_, n_] := #[[ Ordering[#2, -n] ]] & @@ (Tally[a]\[Transpose])

Test:

MyCommonest2[a, 15] // Timing // First
comm[a, 15]         // Timing // First
comm2[a, 15]        // Timing // First
0.3276

0.3056

0.2932
| improve this answer | |
$\endgroup$
  • $\begingroup$ Try sorting the list, then tally... might be surprised, ~40% boost in some short tests. $\endgroup$ – ciao May 1 '14 at 21:17
  • $\begingroup$ @rasher Sort is much slower than Tally on the OP's input list, at least in v7. What data are you using? $\endgroup$ – Mr.Wizard May 1 '14 at 21:43
  • $\begingroup$ e.g., RandomInteger[2000000,2000000]. On the loungebook, might be a cache locality effect, but it's consistent, and even larger with unpacked target since sort packs it... interesting. $\endgroup$ – ciao May 1 '14 at 21:45
  • $\begingroup$ Fiddled with the above some more: Same on WS, but in both cases, only when duplication is low does this happen, otherwise sort slows things dramatically. Probably useless effect, but interesting nonetheless. $\endgroup$ – ciao May 2 '14 at 3:47
7
$\begingroup$

Another one, seems roughly on par with Mr Wizard's comm2 on my machine.

comm3[a_, n_] := Pick[#1, UnitStep[#2 - RankedMax[#2, n]], 1]& @@ Transpose[Tally @ a]
| improve this answer | |
$\endgroup$
7
$\begingroup$
jsat = #1[[Join @@ SparseArray[
  Threshold[#2,{"LargestValues",15}]]["NonzeroPositions"]]]& @@ (Tally[#]\[Transpose])&;

This returns more than k elements because of the ties.

SeedRandom[1];
a = RandomInteger[{1, 1000000}, 50000000];
jsat[a, 15] // Timing // First
comm[a, 15] // Timing // First
comm2[a, 15] // Timing // First
comm3[a, 15] // Timing // First
MyCommonest2[a, 15] // Timing // First

0.64062
0.75000
0.75000
0.71875
0.78125
| improve this answer | |
$\endgroup$
  • $\begingroup$ Darn, beaten by a function I don't have. ;-p At least my computer is faster than yours. ^_^ $\endgroup$ – Mr.Wizard May 2 '14 at 0:03
  • $\begingroup$ @Mr.W still on version 7? Re my machine, yet another reminder to install more memory;) $\endgroup$ – kglr May 2 '14 at 0:38
  • $\begingroup$ Yes, until v10 ships. a takes only 200MB; I doubt it's a memory issue. $\endgroup$ – Mr.Wizard May 2 '14 at 0:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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