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

```

• Prev by Date: Re: Partial differential equation with evolving boundary conditions
• Next by Date: Re: Re: Help to remove equivalent (redundant) solutions
• Previous by thread: Re: Eliminating intermediate results
• Next by thread: Re: Eliminating intermediate results