Re: Eliminating intermediate results
- To: mathgroup at smc.vnet.net
- Subject: [mg91543] Re: [mg91515] Eliminating intermediate results
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Tue, 26 Aug 2008 03:29:47 -0400 (EDT)
- References: <200808250905.FAA24382@smc.vnet.net>
Mariano Suárez-Alvarez wrote:
> Hi,
>
> Suppose you have a function 'generate' which given a parameter p
> produces a list of expressions, and you have a predicate predQ which
> looks at those expressions and does some test. To get the list of
> elements in the list which satisfy the predicate, one says:
>
> Select[generate[p], predQ]
>
> Now, if the list generated by 'generate[p]' is big with respect to the
> resulting filtered list, this tends to become impracticable soon.
>
> For a concrete example: suppose you want to compute the length of
> the list of compositions of a number n in k parts with no zeros. One
> simpleminded way to do that is:
>
> Timing@ Length@ Select[Compositions[25, 6], (! MemberQ[#, 0]) &]
>
> which returns
>
> {10.1025, 118755}
>
> An alternative, considerably more clumsy way is to eliminate the
> intermediate list, and count. For example, using the very cool
> Sow/Reap pair of functions, one can do:
>
> Timing@ Length@ Module[{n = 30, k = 6, bound},
> bound = NumberOfCompositions[n, k];
> Reap[
> For[i = 0; p = Append[Table[0, {k - 1}], n], i < bound, i++;
> p = NextComposition[p],
> If[! MemberQ[p, 0], Sow[p]]
> ]
> ][[2, 1]]
> ]
>
> which in turns gives
>
> {5.9171, 118755}
>
> The difference here might very well be due to the different ways
> in which NextComposition and Compositions are impemented
> in Combinatorica (I haven't looked). But code like
>
> Length@ Select[Compositions[25, 6], (! MemberQ[#, 0]) &]
>
> which constructs huge intermediate data structures seems to
> be quite inefficient in Mathematica.
>
> Is there a standard approach to aleviate this issue? (preferably
> which does not involved ugly code as the one above,
> preserving the nice compositional style)
>
> In the context of functional languages, one speaks of
> 'deforestation',
> which is the effort to eliminate intermediate trees (ie, data
> structures)
> which appear frequently when programming in a compositional
> style. The Haskell compiler, for example, iirc, is smart enough
> to *not* construct an intermediate list in the Haskell
> analogue of
>
> Select[Range[1000], EvenQ]
>
> Coming from Haskell, it be nice to be able to rely on
> Mathematica to be smart, so I don't have to ;)
>
> -- m
Several times faster than what I last wrote is a recursive sort of
approach that only generates subcases of positive contribution.
countCompositionsNoZeros[n_,1] := 1
countCompositionsNoZeros[n_,k_] := Module[{j=0},
Do [j+=countCompositionsNoZeros[m,k-1], {m,k-1,n-1}]; j]
In[4]:= Timing[countCompositionsNoZeros2[30,6]]
Out[4]= {0.880055, 118755}
This approach can be combined with use of Compile to give another factor
of nearly 4.
countCompositionsNoZeros3 = Compile[{{n,_Integer},{k,_Integer}},
Module[{j=0},
If[k==1,1,
Do [j+=countCompositionsNoZeros3[m,k-1], {m,k-1,n-1}]; j]],
{{countCompositionsNoZeros3[_],_Integer}}]
In[17]:= Timing[countCompositionsNoZeros3[30,6]]
Out[17]= {0.236014, 118755}
Memory usage should be modest in both cases.
Daniel Lichtblau
Wolfram Research
- References:
- Eliminating intermediate results
- From: Mariano Suárez-Alvarez <mariano.suarezalvarez@gmail.com>
- Eliminating intermediate results