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>