2

我正在做一些Project Euler项目（不是作为家庭作业，只是为了好玩/学习），我正在学习 Haskell。问题之一是找到起始数低于 100 万的最大 Collat​​z 序列（http://projecteuler.net/problem=14）

所以无论如何，我能够做到这一点，并且我的算法在编译时可以工作并很快得到正确的答案。但是，它使用 1000000 深度递归。

所以我的问题是：我做对了吗？照原样，是正确的 Haskell 方法吗？我怎样才能让它更快？此外，对于内存使用，递归实际上是如何在低级实现的？就像它如何使用内存一样？

（剧透警告：如果您想自己解决 Project Euler 的第 14 题而不看答案，请不要看这个。）

--haskell script --problem：找到小于 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（应该是一个词）的方式来做到这一点。

提前致谢！

4

1 回答 1

8

编辑以回答问题

我做对了吗？

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

照原样，是正确的 Haskell 方法吗？

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

我怎样才能让它更快？

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

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

此外，对于内存使用，递归实际上是如何在低级实现的？就像它如何使用内存一样？

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

原始帖子 - 基准数字

原来的：

$ 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

这与之前的问题非常相似：与 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使用.remeven.&.shiftR

结果比原始速度快约 20 倍。

编辑：人们对 quotRem 在面对Int. 代码已包含在内，但我不清楚这一惊喜：仅仅因为某些事情可能是负面的，并不意味着您无法使用非常相似的位操作来处理它，这些位操作在正确的硬件上可能具有相同的成本。所有三个版本的nextStep性能似乎相同（ghc -O2 -fforce-recomp -fllvmghc 版本 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)
于 2013-06-17T19:50:35.100 回答