Am Mittwoch 06 Januar 2010 19:13:01 schrieb Will Ness:
> Daniel Fischer <daniel.is.fischer <at> web.de> writes:
> > Am Mittwoch 06 Januar 2010 00:09:07 schrieb Will Ness:
> > > Daniel Fischer <daniel.is.fischer <at> web.de> writes:
> > > > Am Montag 04 Januar 2010 22:25:28 schrieb Daniel Fischer:
> > > > Fix rfold:
> > > >
> > > > rfold f [x] = x
> > > > rfold f xs = rfold f (pairwise f xs)
> > > >
> > > > and it's faster also for those.
> >
> > The memory is almost completely due to the tree-merging of the multiples
> > for the fastest runner. While it produces faster than flat merging, the
> > exponential growth of the trees makes a bad memory citizen.
>
> Isn't the number of nodes the same in any two trees with the same number of
> leafs?
Sure. And I don't know why it takes *that much* memory, but since a flat merge
doesn't consume much memory, it must be the trees.
>
> BTW using
>
> compos ps = fst $ tfold mergeSP $ nwise 1 mergeSP $ map pmults ps
>
> instead of
>
> compos ps = fst $ tfold mergeSP $ nwise 1 mergeSP
> $ pairwise mergeSP $ map pmults ps
>
> brings down memory consumption further by 25%..45% on 1..8 mln primes
> produced, while slowing it down by about 0%..2% (that's after eliminating
> the lazy pattern in tfold as per your advice).
>
So much? Wow. I forgot the numbers, but I had tried that too, I thought the
memory gain
wasn't worth the speed loss. Another thing that reduces memory usage is
compos :: [a] -> [a]
compos ps = case pairwise mergeSP (multip ps) of
((a,b):cs) -> a ++ funMerge b (nwise 1 mergeSP $ pairwise
mergeSP cs)
funMerge b (x:y:zs) = let (c,d) = mergeSP x y
in mfun b c d zs
mfun u@(x:xs) w@(y:ys) d l = case compare x y of
LT -> x:mfun xs w d l
EQ -> x:mfun xs ys d l
GT -> y:mfun u ys d l
mfun u [] d l = funMerge (merge u d) l
That's about the same speed as the latter of the above here and uses about 25%
less
memory. Removing one or two 'pairwise's brings memory down further, but makes
it slower.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
