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.

Improve this question
$\endgroup$
1

3 Answers 3

Reset to default
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$
4
  • $\begingroup$ Try sorting the list, then tally... might be surprised, ~40% boost in some short tests. $\endgroup$
    – ciao
    Commented May 1, 2014 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
    Commented May 1, 2014 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
    Commented May 1, 2014 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
    Commented May 2, 2014 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$
3
  • $\begingroup$ Darn, beaten by a function I don't have. ;-p At least my computer is faster than yours. ^_^ $\endgroup$
    – Mr.Wizard
    Commented May 2, 2014 at 0:03
  • $\begingroup$ @Mr.W still on version 7? Re my machine, yet another reminder to install more memory;) $\endgroup$
    – kglr
    Commented May 2, 2014 at 0:38
  • $\begingroup$ Yes, until v10 ships. a takes only 200MB; I doubt it's a memory issue. $\endgroup$
    – Mr.Wizard
    Commented May 2, 2014 at 0:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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