%cat Test.hs module Test(mcombs) where import Data.List mcombs = foldr (flip (>>=) . f) [[]] where f x xs = [x:xs,xs]
%ghc -c -O2 Test.hs %ghci > :l Test Ok, modules loaded: Test. > :set +s length $ mcombs [1..20] 1048576 (0.06 secs, 56099528 bytes) > length $ mcombs [1..50] ^CInterrupted. Daniel Fischer-4 wrote: > > Am Donnerstag 18 März 2010 04:29:53 schrieb zaxis: >> The time is wasted to run combination even if use `combination (x:xs) = >> concat [(x:ys), ys] | ys <- combination xs] ' instead. >> in ghci >> >> >combination [1..20] >> >> will wait for a long time ....... > > Hm, really? > > Prelude> :set +s > Prelude> let combination [] = [[]]; combination (x:xs) = [x:ys | ys <- > combination xs] ++ combination xs > > (0.00 secs, 1818304 bytes) > > Prelude> let combs [] = [[]]; combs (x:xs) = concat [[x:ys,ys] | ys <- > combs xs] > (0.00 secs, 2102280 bytes) > > Prelude> length [1 .. 2^20] > > 1048576 > > (0.07 secs, 49006024 bytes) > > Prelude> length $ combination [1 .. 20] > 1048576 > (8.28 secs, 915712452 bytes) > Prelude> length $ combs [1 .. 20] > 1048576 > (0.78 secs, 146841964 bytes) > > That's interpreted, so not optimised. Optimisation narrows the gap, speeds > both up significantly, so put > > > combination :: [a] -> [[a]] > combination [] = [[]] > combination (x:xs) = [x:ys | ys <- combination xs] ++ combination xs > > combs :: [a] -> [[a]] > combs [] = [[]] > combs (x:xs) = concat [[x:ys,ys] | ys <- combs xs] > > mcombs :: [a] -> [[a]] > mcombs = foldr (flip (>>=) . f) [[]] > where > f x xs = [x:xs,xs] > > in a file, compile with -O2 and load into ghci: > > > Prelude Parts> length $ combination [1 .. 20] > 1048576 > (0.16 secs, 43215220 bytes) > Prelude Parts> length $ combs [1 .. 20] > 1048576 > (0.05 secs, 55573436 bytes) > Prelude Parts> length $ mcombs [1 .. 20] > 1048576 > (0.06 secs, 55572692 bytes) > Prelude Parts> length $ combination [1 .. 24] > 16777216 > (3.06 secs, 674742880 bytes) > Prelude Parts> length $ combs [1 .. 24] > 16777216 > (0.62 secs, 881788880 bytes) > Prelude Parts> length $ mcombs [1 .. 24] > 16777216 > (0.62 secs, 881788956 bytes) > Prelude Parts> length [1 .. 2^24] > 16777216 > (0.64 secs, 675355184 bytes) > > So combs and the pointfree combinator version mcombs are equally fast and > significantly faster than combination. In fact they're as fast as a simple > enumeration. > > Now, if you actually let ghci print out the result, the printing takes a > long time. So much that the difference in efficiency is hardly discernible > or not at all. > >> >> Daniel Fischer-4 wrote: >> > Am Donnerstag 18 März 2010 00:53:28 schrieb zaxis: >> >> import Data.List >> >> >> >> combination :: [a] -> [[a]] >> >> combination [] = [[]] >> >> combination (x:xs) = (map (x:) (combination xs) )++ (combination xs) >> > >> > That would normally be called sublists (or subsets, if one regards >> > lists as >> > representing a set), I think. And, apart from the order in which they >> > are generated, it's the same as Data.List.subsequences (only less >> > efficient). >> > >> >> samp = [1..100] >> >> allTwoGroup = [(x, samp\\x) | x <- combination samp] >> >> >> >> The above code is used to calculate all the two groups from sample >> >> data >> > >> > All partitions into two sublists/sets/samples. >> > >> >> ? It is very slow ! >> > >> > I found it surprisingly not-slow (code compiled with -O2, as usual). >> > There are two points where you waste time. >> > First, in >> > >> > combination (x:xs) >> > >> > you calculate (combination xs) twice. If the order in which the >> > sublists come doesn't matter, it's better to do it only once: >> > >> > combination (x:xs) = concat [(x:ys), ys] | ys <- combination xs] >> > >> > Second, (\\) is slow, xs \\ ys is O(length xs * length ys). >> > Also, (\\) requires an Eq constraint. If you're willing to constrain >> > the type further, to (Ord a => [a] -> [([a],[a])]), and call it only >> > on ordered >> > lists, you can replace (\\) by the much faster difference of oredered >> > lists >> > (implementation left as an exercise for the reader). >> > >> > But you can work with unconstrained types, and faster, if you build >> > the two >> > complementary sublists at the same time. >> > The idea is, >> > -- An empty list has one partition into two complementary sublists: >> > partitions2 [] = [([],[])] >> > -- For a nonempty list (x:xs), the partitions into two complementary >> > -- sublists each have x either in the first sublist or in the second. >> > -- Each partition induces a corresponding partition of the tail, xs, >> > -- by removing x from the group in which it appears. >> > -- Conversely, every partition ox xs gives rise to two partitions >> > -- of (x:xs), by adding x to either the first or the second sublist. >> > So partitions2 (x:xs) >> > = concat [ [(x:ys,zs),(ys,x:zs)] | (ys,zs) <- partitions2 xs ] >> > >> > We can also write the second case as >> > >> > partitions2 (x:xs) = concatMap (choice x) (partitions2 xs) >> > >> > where >> > >> > choice x (ys,zs) = [(x:ys,zs),(ys,x:zs)] >> > >> > Now it's very easy to recognise that partitions2 is a fold, >> > >> > partitions2 xs = foldr (concatMap . choice) [([],[])] xs > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > > ----- fac n = let { f = foldr (*) 1 [1..n] } in f -- View this message in context: http://old.nabble.com/How-to-improve-its-performance---tp27940036p27950876.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
