# [Haskell-cafe] How to improve its performance ?

zaxis z_axis at 163.com
Wed Mar 17 23:29:53 EDT 2010

```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 .......

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
>
>>
>> Sincerely!
>>
>
> _______________________________________________
>
>

-----
fac n = let {  f = foldr (*) 1 [1..n] } in f
--
View this message in context: http://old.nabble.com/How-to-improve-its-performance---tp27940036p27941317.html