Jon*_*FTW 4 math optimization haskell
我正在做项目euler问题224.并在Haskell中掀起了这个列表理解:
prob39 = length [ d | d <- [1..75000000], c <- [1..37500000], b <-[1..c], a <- [1..b], a+b+c == d, a^2 + b^2 == (c^2 -1)]
我用GHC编译它并且它已经运行了超过一个小时的内核优先级超过一个小时而没有返回结果.我该怎么做才能优化此解决方案？我似乎越来越善于以天真的方式找到蛮力解决方案.我能做些什么吗？
编辑:我也不清楚'积分长度'的定义,这只是意味着边长的大小落在正整数集中,即:1,2,3,4,5 ......？
我的Haskell并不令人惊讶,但我认为这将是n ^ 5.
看起来你要说的是每个n从1到7千5百万,用一个小于或等于75百万的perimiter检查每个"几乎钝的"三角形,看看它是否有perimiter n.
此外,我不确定列表推导是否足够聪明,一旦c ^ 2 -1的当前值大于a ^ 2 + b ^ 2就停止查看.
一个简单的重构应该是
prob39 = length [ (a, b, c) | c <- [1..37500000], b <-[1..c], a <- [1..b], a^2 + b^2 == (c^2 -1), (a + b + c) <= 75000000]
你可以做得更好,但这应该快7500万倍.
对这种重构不太确定,但它也应该大大加快速度:
prob39 = length [ (a, b, c) | a <- [1..25000000], b <-[a..(75000000 - 2*a)], c <- [b..(75000000 - a - b)], a^2 + b^2 == (c^2 -1)]
语法可能不是100%.这个想法是a只能是1到2,500万(因为<= b <= c且a + b + c <= 7500万).b只能介于一半到七千万之间(因为b <= c)而且c只能从b到75百万 - (a + b),否则周长将超过7500万.
编辑:更新的代码片段,那里有几个错误.
另一种快速的建议,可以替换C < - [B ..(75000000 - A - B)]具有沿C的线<东西- 75000000 [b..min(( - A - B),SQRT(一个一个+ b b)+ 1)].没有必要费心检查c的任何大于(a ^ 2 + b ^ 2)的平方根的上限的值.不记得那些是否是haskell中正确的min/sqrt函数名称.
在这个问题上获得OCD,我还有一些建议.
1)可以设置上限b键是当前上界的最小和一个^ 2*2 + 1.这是基于这样的原理:(X + 1)^ 2×^ 2 = 2X + 1 .b不能大于我们可以保证(a ^ 2)+(b ^ 2)<(b + 1)^ 2.
2)将c的下限设置为b + 1和floor的最大值(sqrt(a ^ 2 + b ^ 2)-1).就像C的上限一样,不需要测试不可能正确的值.