Services & ResourcesWolfram ForumsMathGroup Archive

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

Eliminating intermediate results

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

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

• Follow-Ups:
  • Re: Eliminating intermediate results
    • From: Daniel Lichtblau <danl@wolfram.com>
  • Re: Eliminating intermediate results
    • From: Daniel Lichtblau <danl@wolfram.com>
  • Re: Eliminating intermediate results
    • From: "Eugene Kirpichov" <ekirpichov@gmail.com>