CODEWITHSUNDEEP
optimizationhaskellprofiling
Chris Taylor
Chris Taylor

Reputation: 47392

How could I optimize this list comprehension?

I'd like to generate all possible pairs of pairs from a list, with the restriction that (a,b) == (b,a) and that ((a,b),(c,d)) == ((c,d),(a,b)) for all a, b, c, d. Additionally, I can assume that all elements in the list I supply as an argument are distinct.

The first thing I did was to write down this list comprehension:

pairsOfPairs :: [a] -> [((a,a),(a,a))]
pairsOfPairs xs = [((w,x),(y,z)) | w <- xs, x <- xs, y <- xs, z <- xs,
                      w < x, y < z, w < y, w /= z, x /= y, x /= z]

This has the virtue of being idiomatic, but is very slow (profiling reveals that close to 90% of the running time was spent in this function and another, similar, function).

The reason for the slowness is that for a list of n elements it generates n^4 candidate pairs of pairs, but the restrictions eventually cut it down to n!/(8 * (n-4)!), meaning that we are doing at least 8 times too much work.

Is there a way to rewrite the function pairsOfPairs that will give it a speed boost? Obviously it will still be O(n^4), but I'm hoping to bring down the constant.

Edit: In fact, I almost always call this function with a list of length 5, meaning that there are 5!/8 = 15 elements in the result, but the function generates a list of 5^4 = 625 elements as an intermediate step. If I could eliminate all of these intermediate elements I'd therefore get a speedup of around 40x!

Upvotes: 3

Views: 174

Answers (1)

Daniel Fischer
Daniel Fischer

Reputation: 183958

A simple way to cut down the amount of work done is to filter as early as possible.

pairsOfPairs :: Ord a => [a] -> [((a,a),(a,a))]
pairsOfPairs xs = [((w,x),(y,z)) | w <- xs, x <- xs, w < x, y <- xs, w < y, x /= y, 
                                   z <- xs, y < z, w /= z, x /= z]

By checking the conditions as soon as they are available, we avoid O(n^2) work for each pair (w,x) with x <= w etc. That's not too bad.

But more can be gained by preprocessing the list, if it is sorted, we can avoid almost all unnecessary work by choosing pairs like

ordPairs :: [a] -> [(a,a)]
ordPairs (x:xs) = [(x,y) | y <- xs] ++ ordPairs xs
ordPairs [] = []

Upvotes: 8

Related Questions