[%] 꼬리재귀 + 메모이제이션 쓰면 그렇게 느리지 않을껄?

[black73..(221.168)]

컴파일러가 지원한다는 가정하지만 말야 (생각보다 지원안하는 컴파일러들이 있음)

t가 꼬리재귀, m이 메모이제이션임

https://gist.github.com/black7375/afce7319b863dd53ac59cc60fd4e01cd

코드

- dc App

[익명(121.141)]

꼬리재귀까지는 "속도"범주에 들어갈 수 있어도 메모이제이션은 공간 복잡도가 바뀌는데 좀 어거지 아니노?

[black7375(221.168)]

예전에 그냥 테스트한거니까. 그리고 메모이제이션은 함수형 패러다임에서 비교적 쉽게 구현할 수 있는 최적화잖음.

[black7375(221.168)]

게다가 아까 원글에서는 공간 복잡도에 대한 이야기도 없었음. 약간 희생해서 성능을 높혀야하는 작업이 필요하다면 하는게 맞고.

[익명(121.141)]

대조군 설정이 잘못 됐다는 뜻임. "함수형 언어의 최적화가 나쁜가?"를 검증하고자 한다면 최적화 수준만 바꿔서 테스트 해야지 동적 계획법으로 해법을 바꾼 결과를 들고 오는 건 잘못된 거 아니겠노? 비교 할거면 동적 계획법을 적용한 명령형 대조군을 가져와서 각각 비교했어야 함

[black7375(221.168)]

저기 위에 d_loop가 동적 계획법 적용된거임

[익명(121.141)]

아 그러네 미안하다 게이야... 그걸 미리 적어놨으면 오해가 없었을건데 이건 아쉽노

[black7375(221.168)]

ㅇㅋㅇㅋ