为什么Haskell表达式如此缓慢？ [英] Why is this Haskell expression so slow?

问题描述

  import Data.List 
 
 collat​​zLength :: Int-> Int 
 collat​​zLength 1 = 1 
 collat​​zLength n |奇数n = 1 + collat​​zLength（3 * n + 1）
 | （Int，Int） - >（Int，Int） - >订购
 maxTuple（x1，x2） ）（y1，y2）| x1> y1 = GT 
 | x1< y1 = LT 
 |否则= EQ 
  

我从GHCi中运行以下代码

  maximumBy maxTuple [（collat​​zLength x，x）| x < -  [1..1000000]] 
  

我知道如果Haskell严格评估，在这将是像O（n ³ ）。既然Haskell懒惰地评估，看起来这应该是n的几倍。这已经运行了近一个小时了。似乎很不合理。有人知道为什么吗？

解决方案

假设 collat​​zLength 函数将被记忆。 Haskell不会自动记忆。你需要自己做。以下是使用 data-memocombinators 软件包的示例。

 导入Data.List 
导入Data.Ord 
导入限定的Data.MemoCombinators作为备注
 
 collat​​zLength :: Integer - > Integer 
 collat​​zLength = Memo.arrayRange（1,1000000）collat​​zLength'
 where 
 collat​​zLength'1 = 1 
 collat​​zLength'n |奇数n = 1 + collat​​zLength（3 * n + 1）
 |即使n = 1 + collat​​zLength（n```2）
 
 main = print $ foldl1'max $ [（collat​​zLength n，n）| n < -  [1..1000000]] 
  

code> -O2 。

I'm working on Project Euler Problem 14. Here's my solution.

import Data.List

collatzLength :: Int->Int
collatzLength 1 = 1
collatzLength n | odd n = 1 + collatzLength (3 * n + 1)
                | even n = 1 + collatzLength (n `quot` 2)

maxTuple :: (Int, Int)->(Int, Int)->Ordering
maxTuple (x1, x2) (y1, y2)  | x1 > y1 = GT
                | x1 < y1 = LT
                | otherwise = EQ

I'm running the following out of GHCi

maximumBy maxTuple [(collatzLength x, x) | x <- [1..1000000]]

I know that if Haskell evaluated strictly, the time on this would be something like O(n³). Since Haskell evaluates lazily though, it seems like this should be some constant multiple of n. This has been running for nearly an hour now. Seems very unreasonable. Does anyone have any idea why?

解决方案

You're assuming that the collatzLength function will be memoized. Haskell does not do automatic memoization. You'll need to do that yourself. Here's an example using the data-memocombinators package.

import Data.List
import Data.Ord
import qualified Data.MemoCombinators as Memo

collatzLength :: Integer -> Integer
collatzLength = Memo.arrayRange (1,1000000) collatzLength'
  where
    collatzLength' 1 = 1
    collatzLength' n | odd n  = 1 + collatzLength (3 * n + 1)
                     | even n = 1 + collatzLength (n `quot` 2)

main = print $ foldl1' max $ [(collatzLength n, n) | n <- [1..1000000]]

This runs in about 1 second when compiled with -O2.

这篇关于为什么Haskell表达式如此缓慢？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！