performance - 列表理解中的性能(处理时间)影响因素是什么？

Question

在学习 learn-you-a-haskell 的例子时“哪个直角三角形有 所有边的整数和等于或小于 10 的所有边的周长为 24？”

rightTrianglesOriginal = [ (a,b,c) | c <- [1..10], b <- [1..10], a <- [1..10], a^2 + b^2 == c^2, a+b+c == 24]

我更改了原始示例的部分，想了解下面的过程(在极端条件下)。

• 谓词的顺序会影响性能吗？

• 添加谓词(其他谓词隐含)会影响性能吗？ (例如 a > b，c > a，c > b？)？

• 根据谓词 (1) a > b 和 (2) c > a 创建元组列表，然后进一步应用 a^2 + b^2 = c^2 是否会提高整体性能?

• 如果我们更改参数位置，例如(a,b,c) 还是 (c, b, a)？

• 如果需要如此繁重的排列和组合，在现实生活中的应用程序中，什么是明智的策略 - 我们是否应该存储预先计算的答案(尽可能)以供下次使用以提高性能或其他任何用途？

rightTriangles = [ (a,b,c) | c <- [1..10], b <- [1..10], a <- [1..10], a^2 + b^2 == c^2]

几乎可以立即给出结果。

rightTriangles10 = [ (a,b,c) | c <- [1..10], b <- [1..10], a <- [1..10], a^2 + b^2 == c^2, a > b , c > a]

几乎可以立即给出结果。

rightTriangles100 = [ (a,b,c) | c <- [1..100], b <- [1..100], a <- [1..100], a^2 + b^2 == c^2, a > b , c > a]

在几秒钟内给出结果。

rightTriangles1000 = [ (a,b,c) | c <- [1..1000], b <- [1..1000], a <- [1..1000], a^2 + b^2 == c^2, a > b , c > a]

我在 30 分钟后停止了进程。结果尚未完成。

请注意，作为初学者，我缺乏检查处理单个函数所花费的确切时间的知识。

Answer 1

rightTrianglesOriginal = [ (a,b,c) | c <- [1..10], b <- [1..10], a <- [1..10], a^2 + b^2 == c^2, a+b+c == 24]

• 谓词的顺序会影响性能吗？

这取决于。在这种情况下，更改谓词的顺序不会改变任何实质性内容，因此差异(如果有的话)将非常小。自 a^2 + b^2 == c^2检查起来比 a + b + c == 24 贵一点，并且两个测试都过滤掉了很多值，我希望通过交换两个测试可以实现小幅加速

rightTrianglesSwapped = [ (a,b,c) | c <- [1..10], b <- [1..10], a <- [1..10], a+b+c == 24, a^2 + b^2 == c^2]

但是整个计算量太小以至于很难可靠地测量。一般来说，您可以通过重新排序测试和生成器来获得很大的差异，特别是将测试和生成器交错到捷径死胡同会产生巨大的影响。在这里，您可以添加 b < c在 b 之间进行测试和 a发电机捷径。当然将生成器更改为 b <- [1 .. c-1]会更有效率。

• 添加谓词(其他谓词隐含)是否会影响性能？ (例如 a > b, c > a, c > b ？)？

是的，但通常很少，除非谓词的评估成本异常高。在上面，如果谓词成立，您将对隐含的第三个谓词进行不必要的评估。这里的谓词对于标准数字类型的计算成本很低，并且不经常对其进行评估(大多数候选三元组较早失败)，因此影响很难衡量。但这是额外的工作要做——编译器不够聪明，无法消除它——所以它会花费额外的时间。

• 根据谓词制作元组列表 (1) a > b和 (2) c > a然后进一步应用 a^2 + b^2 = c^2 是否会提高整体性能？

这取决于。如果将谓词放在它可以走捷径的地方，那将提高性能。使用这些谓词需要对生成器重新排序(在 a 之前获取 b，因此您可以在 c > a 上进行快捷方式)。比较计算起来也比 a^2 + b^2 == c^2 便宜一点。 ，因此即使测试的总数增加(后一种情况比前一种情况淘汰了更多的三元组)，仍然可以提高性能以先进行成本较低的测试(但先进行最具鉴别力的测试也可能是更好的策略，即使如果它们更昂贵，则取决于成本和功率之间的关系。

• 如果我们更改参数位置(例如(a,b,c)或 (c, b, a) ？

基本上，这不会产生任何可衡量的影响。

• 如果需要如此繁重的排列和组合，在现实生活中的应用程序中，什么是明智的策略 - 我们应该存储预先计算的答案(尽可能)以供下次使用以提高性能还是其他？

这取决于。如果计算复杂且结果很小，最好将结果存储起来以供重用。如果计算成本低且结果大，最好重新计算。在这种情况下，毕达哥拉斯三元组的数量很少，计算成本也不是特别低，因此存储以供重用可能是有益的。

rightTriangles10 = [ (a,b,c) | c <- [1..10], b <- [1..10], a <- [1..10], a^2 + b^2 == c^2, a > b , c > a]

几乎可以立即给出结果。

rightTriangles100 = [ (a,b,c) | c <- [1..100], b <- [1..100], a <- [1..100], a^2 + b^2 == c^2, a > b , c > a]

几分钟后给出结果。

rightTriangles1000 = [ (a,b,c) | c <- [1..1000], b <- [1..1000], a <- [1..1000], a^2 + b^2 == c^2, a > b , c > a]

好吧，要检查的三元组数量是极限的三次方，所以将极限增加 10 倍会使要检查的三元组数量增加 1000 倍，运行时间的因子大致相同，由于需要更大的内存，它可能会稍大一些。所以连编译都没有，更不用说优化代码了，

ghci> [ (a,b,c) | c <- [1..100], b <- [1..100], a <- [1..100], a^2 + b^2 == c^2, a > b , c > a]
[(4,3,5),(8,6,10),(12,5,13),(12,9,15),(15,8,17),(16,12,20),(24,7,25),(20,15,25),(24,10,26)
,(21,20,29),(24,18,30),(30,16,34),(28,21,35),(35,12,37),(36,15,39),(32,24,40),(40,9,41)
,(36,27,45),(48,14,50),(40,30,50),(45,24,51),(48,20,52),(45,28,53),(44,33,55),(42,40,58)
,(48,36,60),(60,11,61),(63,16,65),(60,25,65),(56,33,65),(52,39,65),(60,32,68),(56,42,70)
,(55,48,73),(70,24,74),(72,21,75),(60,45,75),(72,30,78),(64,48,80),(80,18,82),(84,13,85)
,(77,36,85),(75,40,85),(68,51,85),(63,60,87),(80,39,89),(72,54,90),(84,35,91),(76,57,95)
,(72,65,97),(96,28,100),(80,60,100)]
(2.64 secs, 2012018624 bytes)

极限 1000 的预计时间约为 45 分钟。对数据使用一些约束，我们可以做得更快:

ghci> length [(a,b,c) | c <- [2 .. 1000], b <- [1 .. c-1], a <- [c-b+1 .. b], a*a + b*b == c*c]
881
(87.28 secs, 26144152480 bytes)