포토로그



3n + 1 Haskell 버전 -.- Erlang

Erlang과 별로 다르지 않게 만들었습니다.

step :: Int -> Int
step n = step n 1
where
step :: Int -> Int -> Int
step 1 acc = acc
step a acc | (rem a 2) == 0 = step (div a 2) (acc + 1)
| otherwise = step (3 * a + 1) (acc + 1)

maximum_step :: [Int] -> Int
maximum_step xs = maximum (map step xs)

main = putStrLn (show (maximum_step [1..1000000]))


근데 입력을 1000000으로 하면 스택 오버플로우 나버리네요. 속도도 얼랭 보다 느립니다. 하스켈 빠르다던데. 그래서 함수에 타입도 명시해주고, tail recursion 되게 하려고 step을 strict 버전으로 바꾸어 보고, maximum이 길이가 1000000인 리스트를 처리 못하길래 maximum도 strict 버전으로 구현해보고, maximum_step과 maximum을 합쳐서 strict 버전으로도 해봤는데 여전히 1000000만은 끝나지를 않는군요.

PS. 삽질해도 안된다... 하스켈 밉다. 왜 tail call optimization이 안되지...

덧글

  • 만성피로 2007/05/04 01:51 # 답글

    아... 누가 좀 안가르쳐주나... 이로써 하스켈은 쓸모 없는 호사가들의 장난감일 뿐이라는 것을 증며하는 셈이군요. ㅋㅋㅋ. 좀 덤벼 보세요.
  • 애자일컨설팅 2007/05/04 18:50 # 답글

    functional.or.kr에 도전해보라는 글을 써보시죠? 아마 mentalese님이 도전하시지 않을까. 근데 GHC 써보셨나요?
  • 만성피로 2007/05/04 23:21 # 답글

    애자일컨설팅: 좋은 생각이네요. 전 GHC로 했어요. Hugs라고 될 것 같지는 않고...
  • 2007/05/05 03:05 # 삭제 답글

    maximum [1..1000000]에서 스택 오버플로우가 나신다면 십중팔구 ghci에서 실행시키셨겠군요. ghci는 ghc에 딸려오는 인터프리터로 엄청 구립니다. ghc는 gcc frontend로 작동하는 컴파일러로서 제법 괜찮은 (바이트코드가 아니라)바이너리를 생성합니다. 제 컴퓨터(펜티엄D 2.6GHz, 1GB)에선 -O2 옵션주고 컴파일한 결과물은 계산을 끝내는데 40초 정도 걸립니다.
  • 2007/05/06 02:53 # 삭제 답글

    컴파일해도 실행이 안되는 이유는 113383에서 중간에 Int형 경계를 넘어가버리면서 무한루프에 빠지기 때문입니다. Integer형으로 하면 잘 됩니다. 코드를 손으로 최적화하면 계산 시간을 5초까지도 단축할 수 있습니다. 자세한 내용은 http://functional.or.kr/node/135#comment-214 을 참고하세요.
  • 만성피로 2007/05/06 23:17 # 답글

    귤: 중간에 Int가 표현할 수 있는 범위를 넘어가버리는군요. 고맙습니다. ^.^
  • 2007/05/07 02:34 # 삭제 답글

    흥미로운 주제라 좀 더 살펴봤습니다. Data.List 모듈을 import하고 maximum 대신 foldl1' max을 사용하면 ghci에서도 스택 넘침을 막을 수 있습니다. http://functional.or.kr/haskell/stack-overflow 을 참조하세요.
댓글 입력 영역