어떻게이 Haskell 프로그램을 최적화 할 수 있습니까?

Question

다음과 같은 코드를 사용하여 상태 모나드를 사용하여 입력 - 결과 쌍을 캐시함으로써 총 중지 시간을 Collatz function으로 메모합니다.

또한 상태의 snd 부분은 출력을 최대화하는 입력 값을 추적하는 데 사용되며 목표는 총 중지 시간을 최대화하는 100 만 미만의 입력 값을 찾는 것입니다. (문제는 project euler에서 찾을 수 있습니다.

import Control.Applicative 
import Control.Arrow 
import Control.Monad.State 
import qualified Data.Map.Strict as M 

collatz :: Integer -> Integer 
collatz n = if odd n 
       then 3 * n + 1 
       else n `div` 2 

memoCollatz :: Integer 
      -> State (M.Map Integer Int, (Integer,Int)) Int 
memoCollatz 1 = return 1 
memoCollatz n = do 
    result <- gets (M.lookup n . fst) 
    case result of 
     Nothing -> do 
      l <- succ <$> memoCollatz (collatz n) 
      let update p@(_,curMaxV) = 
        if l > curMaxV 
         then (n,l) 
         else p 
      modify (M.insert n l *** update) 
      return l 
     Just v -> return v 

main :: IO() 
main = print $ snd (execState (mapM_ memoCollatz [1..limit]) (M.empty,(1,1))) 
    where 
    limit = 1000000 

이 프로그램은 잘 작동하지만 정말 느립니다. 그래서 더 빨리 작동하도록하는 방법을 알아 내는 시간을 보내고 싶다.

을 나는 모습을했다 RWH의 프로파일 장, 그러나의 문제가 무엇인지에 대한 단서가 없다 :

내가 ghc -O2 -rtsopts -prof -auto-all -caf-all -fforce-recomp를 사용하여 컴파일을하고 +RTS -s -p 그것을 실행하고 여기에 결과 :

98,728,229,897,그리고 .prof 파일 :

total time =  4.08 secs (4080 ticks @ 1000 us, 1 processor) 
    total alloc = 3,567,324,056 bytes (excludes profiling overheads) 

COST CENTRE  MODULE %time %alloc 

memoCollatz  Main  84.9 91.9 
memoCollatz.update Main  10.5 0.0 
main    Main  2.4 5.8 
collatz   Main  2.2 2.3 


                   individual  inherited 
COST CENTRE   MODULE     no.  entries %time %alloc %time %alloc 

MAIN     MAIN      52   0 0.0 0.0 100.0 100.0 
main     Main     105   0 0.0 0.0  0.0 0.0 
CAF:main1    Main     102   0 0.0 0.0  0.0 0.0 
    main     Main     104   1 0.0 0.0  0.0 0.0 
CAF:main2    Main     101   0 0.0 0.0  0.0 0.0 
    main     Main     106   0 0.0 0.0  0.0 0.0 
CAF:main4    Main     100   0 0.0 0.0  0.0 0.0 
    main     Main     107   0 0.0 0.0  0.0 0.0 
CAF:main5    Main      99   0 0.0 0.0 94.4 86.7 
    main     Main     108   0 1.4 0.9 94.4 86.7 
    memoCollatz   Main     113   0 82.4 85.8 92.9 85.8 
    memoCollatz.update Main     115  2168610 10.5 0.0 10.5 0.0 
CAF:main10   Main      98   0 0.0 0.0  5.1 11.0 
    main     Main     109   0 0.4 2.7  5.1 11.0 
    memoCollatz   Main     112  3168610 2.5 6.0  4.7 8.3 
    collatz   Main     114  2168610 2.2 2.3  2.2 2.3 
CAF:main11   Main      97   0 0.0 0.0  0.5 2.2 
    main     Main     110   0 0.5 2.2  0.5 2.2 
    main.limit   Main     111   1 0.0 0.0  0.0 0.0 
CAF     GHC.Conc.Signal   94   0 0.0 0.0  0.0 0.0 
CAF     GHC.IO.Encoding   89   0 0.0 0.0  0.0 0.0 
CAF     GHC.IO.Encoding.Iconv 88   0 0.0 0.0  0.0 0.0 
CAF     GHC.IO.Handle.FD   82   0 0.0 0.0  0.0 0.0 

내가 볼 수있는 것은 가비지 수집기가 너무 많은 시간이 소요되고, 프로그램이 memoCollatz을 실행하는 대부분의 시간을 보냈다는 것이다.

그리고 여기에 힙 프로파일에서이 스크린 샷은 다음과 같습니다

내가 메모리 사용량이 증가하고 프로그램이지도를 사용하여 메모이 제이션을하고 있기 때문에 빠른 속도로 감소하지만 기대

그래프에서 급격한 저하를 일으키는 원인이 무엇인지 확인하십시오 (결과를 시각화 할 때 버그 일 수 있습니까?).

이 테이블/그래프를 분석하는 방법과 실제 문제를 나타내는 방법을 알고 싶습니다.

Answer 1

하스켈 위키는이 문제에 다른 솔루션의 몇 가지를 포함 (link)

가 가장 빠른 해결책은 결과를 memoize하는 배열을 사용합니다. 내 컴퓨터에서는 약 1 초에서 최대로 실행됩니다. 거주는 약 35MB입니다.

다음은 약 0.3 초 ​​만에 실행되고 Array 버전의 메모리 1/4을 사용하지만 IO 모나드에서 실행되는 버전입니다.

다른 버전 간에는 절충점이 있으므로 허용되는 것으로 판단해야합니다.

{-# LANGUAGE BangPatterns #-} 

import Data.Array.IO 
import Data.Array.Unboxed 
import Control.Monad 

collatz x 
    | even x = div x 2 
    | otherwise = 3*x+1 

solve n = do 
    arr <- newArray (1,n) 0 :: IO (IOUArray Int Int) 
    writeArray arr 1 1 
    let eval :: Int -> IO Int 
     eval x = do 
     if x > n 
      then fmap (1+) $ eval (collatz x) 
      else do d <- readArray arr x 
        if d == 0 
        then do d <- fmap (1+) $ eval (collatz x) 
          writeArray arr x d 
          return d 
        else return d 
     go :: (Int,Int) -> Int -> IO (Int,Int) 
     go !m x = do d <- eval x 
        return $ max m (d,x) 
    foldM go (0,0) [2..n] 

main = solve 1000000 >>= print