Haskell列表理解是否效率低下？

Question

我开始做项目欧拉并得到问题9.由于我使用Project Euler来学习Haskell,我决定使用列表推导(如Learn You A Haskell中所示).我这样做,GHCI需要一段时间来弄清楚三元组,由于涉及的计算,我认为这是正常的.现在,昨天上班(我不是专业的程序员),我正在和一位了解VBA的朋友交谈,他想尝试在VBA找到答案.我认为这也是一个有趣的挑战,我为ch循环和if语句制作了一些基本的东西,但是我得到的是它比Haskell快得多.

我的问题是:Haskell的列表理解是否非常低效？起初我以为这只是因为我处于GHC的交互模式,但后来我意识到VBA也被解释了.

请注意,我没有发布我的代码,因为它是项目euler的答案.如果它会回答我的问题(因为我做错了),那么我很乐意发布代码.

[编辑]这是我的Haskell列表理解:
[(a,b,c) | c <- [1..1000], b <- [1..c], a <- [1..b], a+b+c=1000, a^2+b^2=c^2]
我想我可以降低c的范围,但是真正放慢它的速度是什么？

Answer 1

你可以用这个问题做两件事,这会让你的代码变慢.一个是你如何尝试a,b和c的值.如果你将a,b,c的所有可能值从1循环到1000,那么你将花费很长时间.要给出提示,如果将其重新排列为c,则可以使用+ b + c = 1000.另一个是如果你只使用列表推导,它将处理a,b和c的每个可能的值.问题告诉您,只有一组唯一的数字可以解决问题,因此如果您更改答案:

[ a * b * c | .... ]

至:

head [ a * b * c | ... ]

然后Haskell的懒惰评估意味着它会在找到第一个答案后停止.当你找到第一个答案时,这就是Haskell等同于打破你的VBA循环.当我使用这两个技巧时,我得到的答案很快就完成了(在一秒钟内)ghci.

附录:我最初错过了条件a <b <c.您也可以在列表推导中使用它; 说出以下内容是有效的:

[(a, b) | b <- [1..100], a <- [1..b-1]]

Answer 2

考虑一下列表理解的简化版本:

[(a,b,c) | a <- [1..1000], b <- [1..1000], c <- [1..1000]]

这将给出a,b和c的所有可能组合.这有点像说,"三千面骰子可以通过多少种方式登陆？" 答案是1000*1000*1000 = 1,000,000,000种不同的组合.如果生成每个组合需要0.001秒,那么完成所有组合需要1,000,000秒(~11.5天).(好吧,对于一台电脑来说,0.001秒实际上很慢,但你明白了)

将谓词添加到列表推导中时,它仍然需要相同的时间来计算; 事实上,它需要更长的时间,因为它需要检查它计算的10亿个组合中的每个组合的谓词.

现在考虑一下你的理解力.它看起来应该快得多,对吧？

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

c有1000种选择.b和a有多少？那么,c的平均选择是500.对于c的所有选择,那么b的平均有500个选择(因为b的范围从1到c).同样,对于c和b的所有选择,a平均有250种选择.这是非常手工波浪,但我相信它是准确的.因此,对于a*10亿/ 8~ = 1亿,b*1000/4选择的c*1000/2选择有1000种选择.它的速度提高了8倍,但是如果你注意到它,你会注意到它实际上与上面的简化版本相同.如果我们比较同一问题的"简化"和"改进"版本,但是从[1..100000]而不是[1..1000],"改进"仍然只比"简化"快8倍.

不要误会我的意思,8x是一个很好的恒定因素加速.但除非你想等几个小时才能得到解决方案,否则你需要得到一个更好的大哦.

正如尼尔指出的那样,降低这个问题的复杂性的方法是,对于给定的,b并c选择a满足的a+b+c=1000.这样,你就不会尝试一堆a失败的东西.这将降低大的复杂性; 你只会考虑大约1000*500*1 = 500,000组合,而不是~100,000,000.