Haskell의 메모리 할당 동작을 이해하기가 어렵다.

Question

나는 Haskell과 FP를 비틀 거리며 가능성에 놀랐다. 그리고 저의 오래된 수학은 실제 유용한 목적을 위해 순진한 코드를 작성하는 데 아무런 문제가 없었습니다. 그러나 모든 독서에 고무되어 저는 놀라운 성능 병목을 일으키지 않는 방법을 이해하는 데 여전히 어려움을 겪습니다.

순진한 구현으로 매우 짧은 코드를 작성한 다음 약간 변경하여 성능이 어떻게 반응하는지 확인하십시오. 그리고 여기에 정말 이해할 수없는 한 가지 예가 있습니다 ... Josephus problem, 에 대한 해결책을 찾은이 함수를 썼습니다. 순진한 목록 구현으로을 사용했습니다.

m = 3 
n = 3000 
main = putStr $ "Soldier #" ++ (show $ whosLeft [1..n]) ++ " survived...\n" 

whosLeft [lucky] = lucky 
whosLeft soldiers = whosLeft $ take (length soldiers -1) $ drop m $ cycle soldiers 

후자는 RTS에 따라 63 %의 생산성으로 190ms에서 실행됩니다.

그런 다음 시도해보고자했던 첫 번째 작업은 (길이 병사 -1)을 제거하고 감소하는 정수로 바꾸는 것입니다.

실행 시간이 최대 900ms로 뛰어 오르고 생산성은 16 %로 낮아졌으며 위의 간단한 코드보다 47 배 더 많은 메모리를 사용합니다! 그래서 엄격한 평가를 추가하고, Int 타입을 강제하고, 전역 변수와 다른 것들을 제거하는 것과 같은 것을 시도했지만 아직 유용하지는 않습니다. 그리고 저는이 속도 저하를 이해할 수 없습니다.

m = 3::Int 
n = 3000::Int 
main = putStr $ "Soldier #" ++ (show $ whosLeft n [1..n]) ++ " survived...\n" 

whosLeft 1 [lucky] = lucky 
whosLeft n' soldiers = n' `seq` left `seq` whosLeft (n'-1) left 
       where left = take (n'-1) $ drop m $ cycle soldiers 

성능 관련 기사와 게시물을 통해 체질했지만 필자는 이것에 대한 힌트를 얻지 못하고있는 것 같습니다. 아직도 하스켈 멍청 아. 나는 큰 것을 놓치고있을거야 ... 어떻게이 하나의 매개 변수 (미리 씹어 먹은 계산 ...)로 속도를 그렇게 많이 줄일 수 있을까?

PS : 요세푸스는 정말 3000 군인 이었다면 나는 알고있다, 그들은

Answer 1

첫 번째 솔루션은 길이를 고려하여 군인 목록의 전체 척추를 강제로 ... 자살에 필요한 않았을 것이다. 두 번째 해결책은 seq을 사용하여 군인 목록의 머리만을 강제합니다. seq 사이에 left을 넣고 length left으로 바꿔주세요. 실적이 다시 나타납니다.