我如何优化这个列表理解？
我想从列表中生成所有可能的对，限制为 (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 倍的加速！
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!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
减少工作量的一个简单方法是尽早过滤。
通过在条件可用时立即检查条件，我们可以避免每对
(w,x)和x <= w等的 O(n^2) 工作。那还不错。但是通过预处理列表可以获得更多，如果它是排序的，我们可以通过选择像这样的对来避免几乎所有不必要的工作
A simple way to cut down the amount of work done is to filter as early as possible.
By checking the conditions as soon as they are available, we avoid O(n^2) work for each pair
(w,x)withx <= wetc. 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