Mathematica 9 is now available
Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2008

[Date Index] [Thread Index] [Author Index]

Search the Archive

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