Am Mittwoch 06 Januar 2010 19:13:01 schrieb Will Ness:
Daniel Fischer
writes: Am Mittwoch 06 Januar 2010 00:09:07 schrieb Will Ness:
Daniel Fischer
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.