# Tally repeated evaluation of function

How can I tally the result of repeated evaluation of a function?

n=100000;
f[]:=RandomInteger[{1, 4}]
Tally@Table[f[], {n}]


When n is really big this needs an unnecessary amount of memory, how do I get rid of the Table without slowing it down significantly?

fTally[f_, n_] := Module[{ c },
c[_] = 0;
Do[c[#] += 1 & @ f[], {n}];
Most[DownValues[c] /. HoldPattern[_@c[y_] :> m_] :> {y, m}]
]
AbsoluteTiming[fTally[f, n];]              (* 0.6s   *)
AbsoluteTiming[Tally@Table[f[], {n}];]     (* 0.009s *)

• I suspect you will not be able to approach the speed of Tally with a user-defined function (outside of compilation, which restricts type). Nevertheless I'll try. Jan 31, 2013 at 13:50
• Regarding your update, try: Do[c[#] += 1 & @ f[], {n}] Jan 31, 2013 at 14:23
• @Mr.Wizard That fixes it, why was it wrong?
– ssch
Jan 31, 2013 at 14:30
• Take a look at Trace[c[f[]] +=1 ] -- there's a double evaluation of f[]. Jan 31, 2013 at 14:35
• @Mr.Wizard This is because of Increment which is HoldFirst. Jan 31, 2013 at 14:36

A systematic approach seems to be in using iterators. An iterator is a data structure which returns a given part of a list on demand. Here is a possible implementation for the case at hand:

ClearAll[makeIterator];
makeIterator[f_, chunkSize_, n_] :=
Module[{ctr = 0},
iterator[
Function[
If[ctr >= n,
None,
With[{result = Table[f[], {Min[chunkSize, n - ctr]}]},
ctr += Length[result];
result
]]]]];


We need to add one generic method for an iterator:

ClearAll[getNext];
getNext[iterator[f_]] := f[]


To test, you can define e.g.

iter = makeIterator[f, 10, 105]


and then call getNext[iter] a few times.

The next ingredient is an auxiliary function which I will call merge:

ClearAll[merge];
merge[tally1_, tally2_] :=
Transpose[{#[[All, 1, 1]], Total[#[[All, All, 2]], {2}]}] &@
GatherBy[tally1~Join~tally2, First]


this merges the counts of two different tallied lists. Finally:

lazyTally[i_iterator] :=
FixedPoint[
With[{next = getNext[i]},
If[next === None, #, merge[#, Tally@next]]
] &,
{}]


We can benchmark:

AbsoluteTiming[fTally[f,n];]
AbsoluteTiming[Tally@Table[f[],{n}];]
lazyTally[makeIterator[f,1000,n]]//AbsoluteTiming

(*
{0.3583984,Null}
{0.0058593,Null}
{0.0156250,{{4,24811},{1,24963},{3,25233},{2,24993}}}
*)


You get a 100-fold efficiency gain in memory for about 3-fold loss in runtime efficiency, for this size of the chunk of entire list (which you can play with)

• That's it, I'm going to bed. You're making my head hurt trying to think this through. :-) Jan 31, 2013 at 14:26
• @Mr.Wizard Have a good sleep :) Jan 31, 2013 at 14:32
• Great! I like the idea of an iterator to do the chunking
– ssch
Jan 31, 2013 at 14:42
• @ssch Iterators represent a very simple for of inversion of control. They allow one to still give the control to actual higher-level functions which do the computations, and which can demand new elements as they need them. They help making the code more modular, since there is then no direct coupling between the computing routines and specific functions which produce list's elements. Jan 31, 2013 at 14:44

It is still far slower than Tally but Sum appears to be faster than your fTally:

n = 1000000;
f[] := RandomInteger[{1, 4}]

fTally[f, n]; // AbsoluteTiming // First


2.0300028

Sum[inert[f[]], {n}]; // AbsoluteTiming // First


0.8900012

The output is in this form:

249831 inert[1] + 250045 inert[2] + 250386 inert[3] + 249738 inert[4]


I am still exploring options but if I find none better I shall package this into a function that produces output of the form used by Tally.

Below this point are some rambling observations as I make them.

Table is faster than Do with your test function:

n = 1000000;
Table[f[], {n}]; // AbsoluteTiming
Do[f[], {n}];    // AbsoluteTiming


{0.0410001, Null}

{0.2300003, Null}

This is probably due to compilation:

SystemOptions["CompileOptions" -> "TableCompileLength"]

{"CompileOptions" -> {"TableCompileLength" -> 250}}

• Since f is defined via rules, it is not likely to be auto-compiled. Jan 31, 2013 at 14:49
• @Leonid well, it's auto-somethinged as setting "TableCompileLength" -> Infinity causes the Table evaluation to slow down to match Do. What's your alternative explanation for that? Jan 31, 2013 at 22:49