On Fri, 2007-12-28 at 09:51 -0700, Luke Palmer wrote:
> On Dec 28, 2007 9:35 AM, Jules Bean <[EMAIL PROTECTED]> wrote:
> > In particular, adding sharing can stop something being GCed, which can
> > convert an algorithm which runs in linear time and constant space to one
> > which runs in linear space (and therefore, perhaps, quadratic time).
>
> I've heard of this before, but can you give an example?
I don't know why they were so modest. Run the following two programs in
the Haskell implementation of your choice
1)
powerset [] = [[]]
powerset (x:xs) = powerset xs ++ map (x:) (powerset xs)
2)
powerset [] = [[]]
powerset (x:xs) = xss ++ map (x:) xss
where xss = powerset xs
Compare it on programs such as length (powerset [1..n]) for n in the
range of 20-30.
Make sure you aren't doing anything important when you use the second
version for larger inputs. These two programs are an extreme case of
trading space for time, and an extreme case of why common subexpression
elimination can be a massive pessimization. In this particular case,
there is an exponential increase in the size of the live-set.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
