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

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 *)
  • $\begingroup$ 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. $\endgroup$
    – Mr.Wizard
    Jan 31, 2013 at 13:50
  • $\begingroup$ Regarding your update, try: Do[c[#] += 1 & @ f[], {n}] $\endgroup$
    – Mr.Wizard
    Jan 31, 2013 at 14:23
  • $\begingroup$ @Mr.Wizard That fixes it, why was it wrong? $\endgroup$
    – ssch
    Jan 31, 2013 at 14:30
  • $\begingroup$ Take a look at Trace[c[f[]] +=1 ] -- there's a double evaluation of f[]. $\endgroup$
    – Mr.Wizard
    Jan 31, 2013 at 14:35
  • 1
    $\begingroup$ @Mr.Wizard This is because of Increment which is HoldFirst. $\endgroup$ Jan 31, 2013 at 14:36

2 Answers 2


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:

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

We need to add one generic method for an iterator:

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:

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] := 
    With[{next = getNext[i]}, 
      If[next === None, #, merge[#, Tally@next]]
    ] &,

We can benchmark:



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)

  • 2
    $\begingroup$ That's it, I'm going to bed. You're making my head hurt trying to think this through. :-) $\endgroup$
    – Mr.Wizard
    Jan 31, 2013 at 14:26
  • $\begingroup$ @Mr.Wizard Have a good sleep :) $\endgroup$ Jan 31, 2013 at 14:32
  • $\begingroup$ Great! I like the idea of an iterator to do the chunking $\endgroup$
    – ssch
    Jan 31, 2013 at 14:42
  • $\begingroup$ @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. $\endgroup$ 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


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


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}}
  • $\begingroup$ Since f is defined via rules, it is not likely to be auto-compiled. $\endgroup$ Jan 31, 2013 at 14:49
  • $\begingroup$ @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? $\endgroup$
    – Mr.Wizard
    Jan 31, 2013 at 22:49

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.