[haskell] Haskell 프로그램의 성능을 분석하기위한 도구
Haskell을 배우기 위해 일부 프로젝트 오일러 문제를 해결하는 동안 (현재 저는 완전히 초보자입니다) 문제 12에 도달했습니다 . 이 (순진한) 솔루션을 썼습니다.
--Get Number of Divisors of n
numDivs :: Integer -> Integer
numDivs n = toInteger $ length [ x | x<-[2.. ((n `quot` 2)+1)], n `rem` x == 0] + 2
--Generate a List of Triangular Values
triaList :: [Integer]
triaList = [foldr (+) 0 [1..n] | n <- [1..]]
--The same recursive
triaList2 = go 0 1
where go cs n = (cs+n):go (cs+n) (n+1)
--Finds the first triangular Value with more than n Divisors
sol :: Integer -> Integer
sol n = head $ filter (\x -> numDivs(x)>n) triaList2이 솔루션 n=500 (sol 500)은 매우 느리기 때문에 (현재 2 시간 이상 실행 됨)이 솔루션이 왜 그렇게 느린 지 알아내는 방법이 궁금했습니다. 내 하스켈 프로그램의 어느 부분이 느린 지 알 수 있도록 대부분의 계산 시간이 어디에서 소비되는지 알려주는 명령이 있습니까? 단순한 프로파일 러와 같은 것.
명확히하기 위해 더 빠른 솔루션을 요구 하는 것이 아니라이 솔루션 을 찾는 방법 을 요구 합니다. 하스켈 지식이 없다면 어떻게 시작하겠습니까?
두 개의 triaList함수 를 작성하려고했지만 어느 것이 더 빠른지 테스트 할 방법이 없었기 때문에 여기에서 문제가 시작됩니다.
감사
답변
이 솔루션이 왜 그렇게 느린 지 알아내는 방법. 내 하스켈 프로그램의 어느 부분이 느린 지 알 수 있도록 대부분의 계산 시간이 어디에 소비되는지 알려주는 명령이 있습니까?
정확합니다! GHC는 다음을 포함한 많은 우수한 도구를 제공합니다.
시간 및 공간 프로파일 링 사용에 대한 튜토리얼 은 Real World Haskell의 일부입니다 .
GC 통계
첫째, ghc -O2로 컴파일하고 있는지 확인하십시오. 최신 GHC (예 : GHC 6.12.x)인지 확인할 수 있습니다.
가장 먼저 할 수있는 일은 가비지 컬렉션이 문제가 아닌지 확인하는 것입니다. + RTS -s로 프로그램 실행
$ time ./A +RTS -s
./A +RTS -s
749700
9,961,432,992 bytes allocated in the heap
2,463,072 bytes copied during GC
29,200 bytes maximum residency (1 sample(s))
187,336 bytes maximum slop
**2 MB** total memory in use (0 MB lost due to fragmentation)
Generation 0: 19002 collections, 0 parallel, 0.11s, 0.15s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 13.15s ( 13.32s elapsed)
GC time 0.11s ( 0.15s elapsed)
RP time 0.00s ( 0.00s elapsed)
PROF time 0.00s ( 0.00s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 13.26s ( 13.47s elapsed)
%GC time **0.8%** (1.1% elapsed)
Alloc rate 757,764,753 bytes per MUT second
Productivity 99.2% of total user, 97.6% of total elapsed
./A +RTS -s 13.26s user 0.05s system 98% cpu 13.479 total이미 많은 정보를 제공합니다. 힙이 2M에 불과하고 GC는 시간의 0.8 %를 차지합니다. 따라서 할당이 문제라고 걱정할 필요가 없습니다.
시간 프로필
프로그램의 시간 프로필을 얻는 것은 간단합니다. -prof -auto-all로 컴파일하십시오.
$ ghc -O2 --make A.hs -prof -auto-all
[1 of 1] Compiling Main ( A.hs, A.o )
Linking A ...N = 200의 경우 :
$ time ./A +RTS -p
749700
./A +RTS -p 13.23s user 0.06s system 98% cpu 13.547 total다음을 포함하는 A.prof 파일을 만듭니다.
Sun Jul 18 10:08 2010 Time and Allocation Profiling Report (Final)
A +RTS -p -RTS
total time = 13.18 secs (659 ticks @ 20 ms)
total alloc = 4,904,116,696 bytes (excludes profiling overheads)
COST CENTRE MODULE %time %alloc
numDivs Main 100.0 100.0을 나타내는 모든 시간이 numDivs에서 소비되고, 그것은 또한 모든 할당의 원천입니다.
힙 프로필
또한 + RTS -p -hy를 실행하여 A.hp를 실행하여 이러한 할당을 분석 할 수도 있습니다. 그러면 A.hp를 포스트 스크립트 파일 (hp2ps -c A.hp)로 변환하여 볼 수 있습니다.
이것은 당신의 메모리 사용에 아무런 문제가 없다는 것을 말해줍니다 : 그것은 일정한 공간에 할당되고 있습니다.
따라서 문제는 numDivs의 알고리즘 복잡성입니다.
toInteger $ length [ x | x<-[2.. ((n `quot` 2)+1)], n `rem` x == 0] + 2실행 시간의 100 % 인 문제를 해결하면 다른 모든 작업이 쉽습니다.
최적화
이 표현식은 스트림 융합 최적화에 적합한 후보 이므로 다음과 같이 Data.Vector 를 사용하도록 다시 작성하겠습니다 .
numDivs n = fromIntegral $
2 + (U.length $
U.filter (\x -> fromIntegral n `rem` x == 0) $
(U.enumFromN 2 ((fromIntegral n `div` 2) + 1) :: U.Vector Int))불필요한 힙 할당없이 단일 루프로 융합되어야합니다. 즉, 목록 버전보다 더 복잡합니다 (일정한 요인에 의해). ghc-core 도구 (고급 사용자 용)를 사용하여 최적화 후 중간 코드를 검사 할 수 있습니다.
이것을 테스트, ghc -O2 –make Z.hs
$ time ./Z
749700
./Z 3.73s user 0.01s system 99% cpu 3.753 total따라서 알고리즘 자체를 변경하지 않고도 N = 150의 실행 시간을 3.5 배 단축했습니다.
결론
문제는 numDivs입니다. 실행 시간의 100 %이며 끔찍한 복잡성이 있습니다. numDivs에 대해 생각해보십시오. 예를 들어 각 N에 대해 [2 .. n div2 + 1] N 번 생성하는 방법을 생각해보십시오 . 값이 변경되지 않으므로이를 메모 해보십시오.
어떤 함수가 더 빠른지 측정하려면 실행 시간의 마이크로 초 미만 개선에 대한 통계적으로 강력한 정보를 제공하는 기준 사용을 고려하세요 .
부록
numDivs는 실행 시간의 100 %이기 때문에 프로그램의 다른 부분을 만져도 큰 차이는 없지만 교육적 목적을 위해 스트림 융합을 사용하여 다시 작성할 수도 있습니다.
또한 trialList를 다시 작성하고 fusion을 사용하여 “prefix scan”기능 (scanl이라고도 함) 인 trialList2에서 직접 작성한 루프로 변환 할 수 있습니다.
triaList = U.scanl (+) 0 (U.enumFrom 1 top)
where
top = 10^6sol의 경우 :
sol :: Int -> Int
sol n = U.head $ U.filter (\x -> numDivs x > n) triaList전체 실행 시간은 동일하지만 코드가 조금 더 깔끔합니다.
답변
Dons의 대답은 문제에 대한 직접적인 해결책을 제공함으로써 스포일러가되지 않고 훌륭합니다.
여기에 제가 최근에 작성한 작은 도구 를 제안하고 싶습니다 . 기본값보다 더 자세한 프로필을 원할 때 SCC 주석을 직접 작성하는 시간을 절약 할 수 있습니다 ghc -prof -auto-all. 그 외에도 화려합니다!
다음은 여러분이 준 코드 (*), 녹색은 정상, 빨간색은 느립니다.
항상 제수 목록을 작성합니다. 이것은 당신이 할 수있는 몇 가지를 제안합니다 :
1. 필터링을 n rem x == 0더 빠르게 만들지 만 그것은 내장 함수이기 때문에 아마도 이미 빠를 것입니다.
2. 더 짧은 목록을 만듭니다. 까지만 확인하여 이미 해당 방향으로 무언가를 수행했습니다 n quot 2.
3. 목록 생성을 완전히 버리고 수학을 사용하여 더 빠른 솔루션을 얻으십시오. 이것은 프로젝트 오일러 문제에 대한 일반적인 방법입니다.
(*)라는 파일에 코드를 넣고 eu13.hs주 함수를 추가하여 이것을 얻었습니다 main = print $ sol 90. 그런 다음 실행 visual-prof -px eu13.hs eu13하면 결과는 eu13.hs.html.
답변
Haskell 관련 참고 : triaList2물론 triaList후자가 많은 불필요한 계산을 수행하기 때문에 더 빠릅니다 . 의 n 개의 첫 번째 요소를 계산하는 데 2 차 시간이 걸리지 triaList만 triaList2. 무한 게으른 삼각형 숫자 목록을 정의하는 또 다른 우아하고 효율적인 방법이 있습니다.
triaList = 1 : zipWith (+) triaList [2..]수학 관련 참고 : n / 2까지 모든 제수를 확인할 필요가 없으며 sqrt (n)까지 확인하는 것으로 충분합니다.
