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? 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). > > 'pairwise' puts odd leafs higher on the right. It might be better if it was > > so on the left, for the frequency of production is higher. > > Maybe. But how would you do it? I tried passing the length to rfold, so when > there was an odd numberof trees in the list, it would move the first out of > the recursion. Any possible gains in production have been more than eaten up > by the control code (not a big difference, but it was there). yes I've seen this too now. BTW, at a price of further slowing down, memory can be lowered yet more with compos ps = fst $ tfold mergeSP $ nwise 1 0.4 mergeSP $ map pmults ps nwise k d f xs = let (ys,zs) = splitAt (round k) xs in rfold f ys : nwise (k+d) d f zs It really looks like the nearer the structure is to linear list, the lower the memory consumption becomes. Of course using 0.0 in place of 0.4 would make it into a plain list. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe