Re: Eliminating intermediate results
- To: mathgroup at smc.vnet.net
- Subject: [mg91533] Re: [mg91515] Eliminating intermediate results
- From: "Eugene Kirpichov" <ekirpichov at gmail.com>
- Date: Mon, 25 Aug 2008 06:56:53 -0400 (EDT)
- References: <200808250905.FAA24382@smc.vnet.net>
To the best of my knowledge, Mathematica is not able to do any of such
optimizations automatically.
It may well turn out that they are extremely hard to be implemented
correctly and even harder to be proved correct, considering
Mathematica's radically different approach to evaluation. In Haskell
these optimizations are possible due to all polymorphic functions
being natural transformations, whereas Mathematica's rewrite engine
and uncontrolled side-effects are very far from providing that.
So I guess you will have to either live with it or use Haskell ;)
Or probably implement a sub-language inside Mathematica and write
these rewriting optimizations yourself for some particular cases, like
Optimizations = Dispatch[{
Select[Range[a_,b_], pred_] :> SelectOptimizedForRange[a,b,pred],
... (several dozen more)
}]
MyEval[expr_] := Evaluate[expr /. Optimizations]
SetAttributes[MyEval, Hold]
MyEval[Select[Range[10,100], EvenQ]]
2008/8/25 Mariano Su¨¢rez-Alvarez <mariano.suarezalvarez at gmail.com>:
> 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
>
>
- References:
- Eliminating intermediate results
- From: Mariano Suárez-Alvarez <mariano.suarezalvarez@gmail.com>
- Eliminating intermediate results