2

在从 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），会对性能产生影响吗？

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

右三角形 = [ (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 分钟后停止了进程。结果尚未完成。

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

4

1 回答 1

6 
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测试到快捷方式。当然，将生成器更改为更有效。bab <- [1 .. c-1]

  • 添加谓词（其他谓词暗示）会影响性能吗？（例如a > b, c > a, c > b？）？

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

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

那要看。如果你把一个谓词放在一个可以捷径的地方，那将提高性能。使用这些谓词需要重新排序生成器（获取abefore 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)
于 2012-06-28T02:15:17.077 回答