我怎样才能优化这个列表理解？

Question

我想从列表中生成所有可能的对,限制为(a,b)==(b,a)和((a,b),(c,d))==(( c,d),(a,b))所有a,b,c,d.另外,我可以假设我作为参数提供的列表中的所有元素都是不同的.

我做的第一件事就是写下这个列表理解:

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]

这具有惯用的优点,但速度非常慢(剖析显示接近90%的运行时间花费在此功能上,而另一个类似的功能).

缓慢的原因是,对于n个元素的列表,它生成n ^ 4个候选对对,但是这些限制最终将其缩减为n!/(8*(n-4)!),这意味着我们正在做至少8次工作太多了.

有没有办法重写pairsOfPairs能够提高速度的功能？显然它仍然是O(n ^ 4),但我希望降低常数.

---

编辑:事实上,我几乎总是用长度为5的列表调用此函数,这意味着结果中有5个!/ 8 = 15个元素,但该函数生成一个5 ^ 4 = 625个元素的列表作为中间步骤.如果我能消除所有这些中间元素,我就会获得大约40倍的加速!

Answer 1

减少完成工作量的一种简单方法是尽早过滤.

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]

通过,尽快为他们提供检查的条件下,我们避免了每对为O(n ^ 2)工作(w,x)用x <= w等等.这是不是太糟糕.

但是通过预处理列表可以获得更多,如果它被排序,我们可以通过选择像这样的对来避免几乎所有不必要的工作

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