Re: Eliminating intermediate results
- To: mathgroup at smc.vnet.net
- Subject: [mg91560] Re: Eliminating intermediate results
- From: Ray Koopman <koopman at sfu.ca>
- Date: Wed, 27 Aug 2008 06:43:14 -0400 (EDT)
- References: <g8tsmu$nsc$1@smc.vnet.net>
An approach in which a function generates a list of intermediate
results which is passed to another function that reduces the list to
a scalar, when in theory the second function could have operated on
the individual list items as they were generated and thus avoided
storing the list, can be still surprisingly efficient if the right
functions are used. In the following, I've replaced the !MemberQ in
the original code with the slightly faster (at least in 5.2) FreeQ,
and I give results for both n=25, k=6 and n=30, k=6.
Timing@Length@Select[Compositions[25,6],FreeQ[#,0]&]
Timing@Length@Module[{n = 25, 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[FreeQ[p,0],Sow[p]]
]
][[2,1]]
]
Timing@Tr[Length@Permutations@#&/@P[25-6,6]]
{10.56 Second, 42504}
{6.16 Second, 42504}
{0.02 Second,42504}
Timing@Length@Select[Compositions[30,6],FreeQ[#,0]&]
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[FreeQ[p,0],Sow[p]]
]
][[2,1]]
]
Timing@Tr[Length@Permutations@#&/@P[30-6,6]]
{24.02 Second,118755}
{14.18 Second,118755}
{0.06 Second,118755}
P[n,m] is a routine (given below) that I have posted here
previously [mg57634]. It returns the partitions of n into
m non-negative non-increasing parts. Note that the second
argument is different from the second argument in the
standard add-on function Partitions.
P[0,m_] := {Table[0,{m}]};
P[n_,m_]/;n<m := With[{z=Table[0,{m-n}]},Join[#,z]&/@P[n,n]];
P[n_,1] := {{n}};
P[n_,2] := Table[{n-i,i},{i,0,n/2}];
P[n_,m_] := ToExpression[ "Block[" <>
ToString[Table[SequenceForm["n",k],{k,m-2}]] <>
",Flatten[Table[" <>
ToString[Table[If[k==m,SequenceForm["n",m-2,"-i",m-1],
SequenceForm["i",k]],{k,m,1,-1}]] <> "," <>
StringTake[ToString[Table[Which[
k==1,StringForm["{i1,0,``/``}",n,m],
k==2,StringForm["{i2,i1,(n1=``-i1)/``}",n,m-1],
True,StringForm["{i`3`,i`2`,(n`2`=n`1`-i`2`)/`4`}",
k-2,k-1,k,m+1-k]], {k,m-1}]], {2,-2}] <> "]," <>
ToString[m-2] <> "]]" ]
P[7,3]
{{7,0,0},{6,1,0},{5,2,0},{4,3,0},
{5,1,1},{4,2,1},{3,3,1},{3,2,2}}
On Aug 25, 2:06 am, Mariano Su=E1rez-Alvarez
<mariano.suarezalva... at gmail.com> 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