Daniel Fischer <daniel.is.fischer <at> web.de> writes: > > > The below code is now a well-behaved memory citizen (3MB for the 100 millionth prime, about the same as the PQ code). It still is considerably slower than the PQ code. > In terms of MUT times as reported by +RTS -sstderr - as well as (MUT+GC) times - (measured once for prime No. 5*10^5, 10^6, 2*10^6, 4*10^6, 10^7 to get a rough tendency), it seems to scale a wee bit better than any of the other tfold versions I created, but a little worse than the PQ versions. > The relation of MUT times isn't too bad, but the GC times are rather abysmal (30-40%). > > ---------------------------------------------------------------------- > data People a = P { vips :: [a], dorks :: [a] } > > celebrate :: a -> People a -> People a > celebrate x p = P (x:vips p) (dorks p) > > primes :: forall a. Integral a => () -> [a] > primes () = 2:3:5:7:11:13:primes' > where > primes' = roll 17 wheel13 `minus` compos primes''' primes'' = 17:19:23:29:31:rollFrom 37 `minus` compos primes'' > primes''' = 17:19:23:29:31:37:rollFrom 41 `minus` compos primes'' > > pmults :: a -> People a > pmults p = case map (*p) (rollFrom p) of > (x:xs) -> P [x] xs > > multip :: [a] -> [People a] > multip ps = map pmults ps > > compos :: [a] -> [a] compos = vips . smartfold mergeSP . multip > > > smartfold f = tfold f . pairwise f > > tfold f (a:b:c:xs) = (a `f` (b `f` c)) `f` smartfold f xs > > pairwise f (x:y:ys) = f x y : pairwise f ys > > mergeSP :: Integral a => People a -> People a -> People a > mergeSP p1@(P a _) p2 = P (a ++ vips mrgd) (dorks mrgd) > where > mrgd = spMerge (dorks p1) (vips p2) (dorks p2) > spMerge l1 [] l3 = P [] (merge l1 l3) > spMerge ~l1@(x:xs) l2@(y:ys) l3 = case compare x y of > LT -> celebrate x (spMerge xs l2 l3) > EQ -> celebrate x (spMerge xs ys l3) > GT -> celebrate y (spMerge l1 ys l3) > > ---------------------------------------------------------------------- >
Hi Daniel, Is it so that you went back to my fold structure? Was it better for really big numbers of primes? I had the following for ages (well, at least two weeks) but I thought it was slower and took more memory (that was _before_ the 'no-share' and 'feeder' stuff). I can see the only difference in that you've re-written spMerge in a tail-recursive style with explicitly deconstructed parts; mine was relying on the compiler (8-L) to de-couple the two pipes and recognize that the second just passes along the final result, unchanged. The two versions seem to me to be _exactly_ operationally equivalent. All this searching for the code better understood by the compiler is _*very*_ frustrating, as it doesn't reflect on the semantics of the code, or even the operational semantics of the code. :-[ Weren't the P's supposed to disappear completely in the compiled code? Aren't types just a _behavioral_ definitions??? Aren't we supposed to be able to substitute equals for equals dammit?? Is this the state of our _best_ Haskell compiler???? module Primes8 where import Data.Monoid data (Ord a) => SplitList a = P [a] [a] instance (Ord a) => Monoid (SplitList a) where mempty = P [] [] -- {x | x::SplitList a} form a monoid under mappend mappend (P a b) ~(P c d) = let P bc b' = spMerge b c in P (a ++ bc) (merge b' d) where spMerge :: (Ord a) => [a] -> [a] -> SplitList a spMerge u@(x:xs) w@(y:ys) = case compare x y of LT -> P (x:c) d where (P c d) = spMerge xs w EQ -> P (x:c) d where (P c d) = spMerge xs ys GT -> P (y:c) d where (P c d) = spMerge u ys spMerge u [] = P [] u spMerge [] w = P [] w mconcat ms = fold mappend (pairwise mappend ms) where fold f (a: ~(b: ~(c:xs))) = (a `f` (b `f` c)) `f` fold f (pairwise f xs) pairwise f (x:y:ys) = f x y:pairwise f ys primes :: Integral a => () -> [a] primes () = 2:3:5:7:primes' where primes' = [11,13] ++ drop 2 (rollFrom 11) `minus` comps mults = map (\p-> P [p*p] [p*n | n<- tail $ rollFrom p]) $ primes' P comps _ = mconcat mults _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe