[Haskell-cafe] How to improve its performance ?

zaxis z_axis at 163.com
Wed Mar 17 23:33:31 EDT 2010


`allPairs list = [(x,y) | x <- list, y <- list]  ` is not what `combination`
does !
>let allPairs list = [(x,y) | x <- list, y <- list] 
>allPairs [1,2,3]
[(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)]

>combination [1,2,3]
[[1,2,3],[2,3],[1,3],[3],[1,2],[2],[1],[]]


Alexander Solla-2 wrote:
> 
> 
> On Mar 17, 2010, at 6:14 PM, Daniel Fischer wrote:
> 
>> I found it surprisingly not-slow (code compiled with -O2, as usual).
>> There are two points where you waste time.
> 
> 
> I found one big point where time is wasted:  in computing the powerset  
> of a list.  He's making 2^n elements, and then iterating through them  
> all and filtering, but only needs n^2 or n `choose` 2 of the  
> (depending on the semantics for his "groups").
> 
> The answer is to do something like:
> 
> allPairs list = [(x,y) | x <- list, y <- list]
> 
> to get it done in n^2 time.
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at 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---tp27940036p27941343.html
Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.



More information about the Haskell-Cafe mailing list