Haskell递归效率

Question

我正在做一些 Project Euler项目(不是家庭作业，只是为了娱乐/学习)，我正在学习 Haskell。其中一个问题是找到起始数在 100 万以下的最大 Collat​​z 序列 ( http://projecteuler.net/problem=14 )

所以无论如何，我能够做到，并且我的算法可以运行并且在编译时相当快地得到正确的答案。但是，它使用了 1000000 深度递归。

所以我的问题是:我这样做对吗？照原样，是正确的 Haskell 方法吗？我怎样才能让它更快？另外，对于内存使用，递归实际上是如何在底层实现的？至于它如何使用内存？

(剧透警告:如果你想自己解决 Project Euler 的问题 #14 而不看答案，请不要看这个。)

--haskell脚本--问题:找到小于 200 万的数字的最长 collat​​z 链。

collatzLength x| x == 1 = 1
               | otherwise = 1 + collatzLength(nextStep x)


longestChain (num, numLength) bound counter
           | counter >= bound = (num, numLength)
           | otherwise = longestChain (longerOf (num,numLength)
             (counter,   (collatzLength counter)) ) bound (counter + 1)
           --I know this is a messy function, but I was doing this problem just 
           --for myself, so I didn't bother making some utility functions for it.
           --also, I split the big line in half to display on here nicer, would
           --it actually run with this line split?


longerOf (a1,a2) (b1,b2)| a2 > b2 = (a1,a2)
                        | otherwise = (b1,b2)

nextStep n | mod n 2 == 0 = (n `div` 2)
           | otherwise = 3*n + 1

main = print (longestChain (0,0) 1000000 1)

使用 -O2 编译时，程序运行时间约为 7.5 秒。

那么，有什么意见/建议吗？我想尝试让程序以更少的内存使用量运行得更快，我想以一种非常 Haskellian(应该是一个词)的方式来实现。

提前致谢!

Answer 1

编辑以回答问题

did I do this right?

几乎，正如评论所说，你构建了一个很大的 1+(1+(1+...)) - 改用严格的累加器或为您处理事情的高级函数。还有其他一些小事，比如定义一个函数来比较第二个元素而不是使用 maximumBy (comparing snd)但这更具风格。

As is, is the the proper Haskell way to do it?

这是可以接受的惯用 Haskell 代码。

How could I make it faster?

请参阅我的以下基准。欧拉性能问题的最常见答案是:

• 使用 -O2(就像您所做的那样)
• 尝试 -fllvm(GHC NCG 是次优的)
• 使用 worker/wrappers 来减少参数，或者在您的情况下，利用累加器。
• 使用快速/不可装箱的类型(如果可以则使用 Int 代替 Integer，如果需要可移植性则使用 Int64 等)。
• 使用rem而不是 mod当所有的值都是正数时。对于您的情况，了解或发现 div 也很有用。倾向于编译成比 quot 慢的东西.

Also, with memory usage, how is the recursion actually implemented on the low-level? As in how does it use memory?

这两个问题都非常广泛。完整的答案可能需要解决惰性评估、尾部调用优化、工作人员转换、垃圾收集等问题。我建议您随着时间的推移更深入地探索这些答案(或者希望这里有人给出我正在避免的完整答案)。

原帖 - 基准数据

原文:

$ ghc -O2 so.hs ; time ./so
[1 of 1] Compiling Main             ( so.hs, so.o )
Linking so ...
(837799,525)

real    0m5.971s
user    0m5.940s
sys 0m0.019s

为 collatzLength 使用带累加器的辅助函数:

$ ghc -O2 so.hs ; time ./so
[1 of 1] Compiling Main             ( so.hs, so.o )
Linking so ...
(837799,525)

real    0m5.617s
user    0m5.590s
sys 0m0.012s

使用 Int而不是默认为 Integer - 使用类型签名也更容易阅读!

$ ghc -O2 so.hs ; time ./so
[1 of 1] Compiling Main             ( so.hs, so.o )
Linking so ...
(837799,525)

real    0m2.937s
user    0m2.932s
sys 0m0.001s

使用 rem而不是 mod :

$ ghc -O2 so.hs ; time ./so
[1 of 1] Compiling Main             ( so.hs, so.o )
Linking so ...
(837799,525)

real    0m2.436s
user    0m2.431s
sys 0m0.001s

使用 quotRem而不是 rem然后 div :

$ ghc -O2 so.hs ; time ./so
[1 of 1] Compiling Main             ( so.hs, so.o )
Linking so ...
(837799,525)

real    0m1.672s
user    0m1.669s
sys 0m0.002s

这与之前的问题非常相似:Speed comparison with Project Euler: C vs Python vs Erlang vs Haskell

编辑:是的，正如 Daniel Fischer 建议的那样，使用 .&. 的位操作和 shiftR改进了 quotRem :

$ ghc -O2 so.hs ; time ./so
(837799,525)

real    0m0.314s
user    0m0.312s
sys 0m0.001s

或者你可以只使用 LLVM 让它发挥它的魔力(注意这个版本仍然使用 quotRem)

$ time ./so
(837799,525)

real    0m0.286s
user    0m0.283s
sys 0m0.002s

LLVM 实际上做得很好，只要你避免 mod 的丑陋行为。 ，并使用 rem 优化基于守卫的代码或 even与手动优化的一样好 .&.与 shiftR .

结果比原来快 20 倍左右。

编辑:人们惊讶于 quotRem 在面对 Int 时表现得和位操作一样好。 .代码已包含在内，但我不清楚是否会感到惊讶:仅仅因为某些东西可能是负面的并不意味着您无法使用非常相似的位操作来处理它，这些位操作在正确的硬件上可能具有相同的成本。 nextStep 的所有三个版本似乎表现相同( ghc -O2 -fforce-recomp -fllvm ，ghc 版本 7.6.3，LLVM 3.3，x86-64)。

{-# LANGUAGE BangPatterns, UnboxedTuples #-}

import Data.Bits

collatzLength :: Int -> Int
collatzLength x| x == 1    = 1
               | otherwise = go x 0
 where
    go 1 a  = a + 1
    go x !a = go (nextStep x) (a+1)


longestChain :: (Int, Int) -> Int -> Int -> (Int,Int)
longestChain (num, numLength) bound !counter
   | counter >= bound = (num, numLength)
   | otherwise = longestChain (longerOf (num,numLength) (counter, collatzLength counter)) bound (counter + 1)
           --I know this is a messy function, but I was doing this problem just 
           --for myself, so I didn't bother making some utility functions for it.
           --also, I split the big line in half to display on here nicer, would
           --it actually run with this line split?


longerOf :: (Int,Int) -> (Int,Int) -> (Int,Int)
longerOf (a1,a2) (b1,b2)| a2 > b2 = (a1,a2)
                        | otherwise = (b1,b2)
{-# INLINE longerOf #-}

nextStep :: Int -> Int
-- Version 'bits'
nextStep n = if 0 == n .&. 1 then n `shiftR` 1 else 3*n+1
-- Version 'quotRem'
-- nextStep n = let (q,r) = quotRem n 2 in if r == 0 then q else 3*n+1
-- Version 'almost the original'
-- nextStep n | even n = quot n 2
--            | otherwise  = 3*n + 1
{-# INLINE nextStep #-}


main = print (longestChain (0,0) 1000000 1)