我该如何优化这个列表推导式？

Question

我该如何优化这个列表推导式？

3

我希望生成一个列表中所有可能的成对组合，其中有一个限制条件是 (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的列表调用此函数，这意味着结果中有15个元素，但函数生成了625个元素的中间步骤。如果我能消除所有这些中间元素，我将获得大约40倍的加速！

- Chris Taylor

你的第一个段落似乎暗示着 a = b = c = d。我不认为这是你的意思。 - dave4420

@dave4420 我使用'=='表示等价，即(a,b)这一对应该被视为等同于(b,a)，但并不意味着a和b必须相等。 - Chris Taylor

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Daniel Fischer · Accepted Answer

简化工作量的一种简单方法是尽早进行过滤。

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]

一旦条件可用，我们立即进行检查，避免对于每个满足 x <= w 的(w,x) 对都进行 O(n^2) 的工作等。这并不太糟糕。

但如果预处理列表，可以获得更多收益，如果列表已排序，则可以通过选择类似的对来避免几乎所有不必要的工作

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