MathGroup Archive 2008

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

Search the Archive

Eliminating intermediate results

  • To: mathgroup at
  • Subject: [mg91515] Eliminating intermediate results
  • From: Mariano Suárez-Alvarez <mariano.suarezalvarez at>
  • Date: Mon, 25 Aug 2008 05:05:24 -0400 (EDT)


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];
     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
which is the effort to eliminate intermediate trees (ie, data
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

  • Prev by Date: Re: NURBS Package Available
  • Next by Date: Re: four dimensional plot
  • Previous by thread: Integration takes more time:
  • Next by thread: Re: Eliminating intermediate results