Re: Speed challenge: Improve on integer frequencies from Count?
- To: mathgroup at smc.vnet.net
- Subject: [mg67779] Re: Speed challenge: Improve on integer frequencies from Count?
- From: "Ray Koopman" <koopman at sfu.ca>
- Date: Fri, 7 Jul 2006 07:13:00 -0400 (EDT)
- References: <e8ir3t$s8o$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
If maxInt is small then myFrequencies is best.
But if maxInt is large then something like myFreqs
(an adaptation of Carl Woll's runs3) will be better.
In[1]:=
myFrequencies = Compile[{{myList,_Integer,1},{maxInt,_Integer}},
Table[Count[myList,i],{i,0,maxInt}]];
In[2]:=
myFreqs = Compile[{{myList,_Integer,1},{maxInt,_Integer}},
Module[{bins = Table[0,{maxInt+1}]},
Scan[bins[[#]]++&,myList+1]; bins]];
In[3]:=
try[maxInt_] := {maxInt,
testList = Table[Random[Integer,{0,maxInt}],{1000}];
myFrequencies[testList,maxInt] === myFreqs[testList,maxInt],
First@Timing@Do[myFrequencies[testList,maxInt],{1000}],
First@Timing@Do[myFreqs[ testList,maxInt],{1000}]}
In[4]:= try[500]
Out[4]= {500,True,4.76 Second,0.51 Second}
In[5]:= try[50]
Out[5]= {50,True,0.53 Second,0.45 Second}
In[6]:= try[5]
Out[6]= {5,True,0.11 Second,0.45 Second}
Gareth Russell wrote:
> Hi,
>
> A challenge for the efficiency gurus:
>
> Given a list of integers whose possible values lie in the range 0 to
> maxInt, with any given integer represented 0, 1 or multiple times,
> e.g., what you would get from
>
> Table[Random[Integer, {0, maxInt}], {1000}]
>
> create a list of frequencies of values including ALL possible values
> (i.e., not the basic output of Frequencies[], because that only
> includes values present in the list.
>
> The fastest I have been able to come up with is the obvious use of Count[]...
>
> In[256]:=
> myFrequencies=Compile[{{myList,_Integer,1},{
> maxInt,_Integer}},Table[Count[myList,i],{i,0,maxInt}]]
>
> Out[256]=
> CompiledFunction[{myList,maxInt},Table[Count[myList,i],{i,0,maxInt}],-\
> CompiledCode-]
>
> In[278]:=
> testList=Table[Random[Integer,{0,500}],{1000}];
>
> In[281]:=
> Timing[Do[myFrequencies[testList,500];,{1000}]]
>
> Out[281]=
> {2.3103 Second,Null}
>
> However, it seems to me that this should be able to be improved upon,
> because it scans the whole list maxInt times. One should be able to
> scan the list once, and increment a frequency list in the right places,
> perhaps with a For[] loop. But try as I might, I can't come up with a
> version that is faster than the compiled Count[] version above.
>
> Can anyone do it?
>
> Gareth
>
> --
> Gareth Russell
> NJIT