[Haskell-cafe] Re: FASTER primes
will_n48 at yahoo.com
Wed Jan 6 13:13:01 EST 2010
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
compos ps = fst $ tfold mergeSP $ nwise 1 mergeSP $ map pmults ps
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.
More information about the Haskell-Cafe