[Haskell-cafe] How to improve its performance ?
Daniel Fischer
daniel.is.fischer at web.de
Thu Mar 18 12:13:49 EDT 2010
Am Donnerstag 18 März 2010 05:03:28 schrieb Alexander Solla:
> On Mar 17, 2010, at 8:33 PM, zaxis wrote:
> > `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)]
>
> Yeah, I know that. I said so specifically. combination computes the
> power set of a list. You said your goal was to compute a set of "two
> groups". You don't need the power set in order to compute a set of
> pairs. Moreover, computing the power set is a slow operation.
> Indeed, it is the source of your slowness.
I think you've been fooled by the names. If you look at the code (or run it
on a smaller sample), you'll see that allTwoGroup computes the list of all
partitions of sample into two complementary sets.
If sample were [1,2,3], the result would be (apart from the order)
[([1,2,3],[]),([1,2],[3]),([1,3],[2]),([2,3],[1]),([1],[2,3]),([2],[1,3]),
([3],[1,2]),([],[1,2,3])]
with sample = [1 .. 100], it's a list of 2^100 elements, that'll take a
long time to compute no matter how.
More information about the Haskell-Cafe
mailing list