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