memoization의 위력을 체감할 수 있었던 연습문제.
머리로 알고 있는 것과 실제 돌려본 것은 역시 느낌이 다르네 ㅎㅎ
(define (lookup key table)
(let ((record (assoc key (cdr table))))
(if record
(cdr record)
false)))
(define (assoc key records)
(cond ((null? records) false)
((equal? key (caar records)) (car records))
(else (assoc key (cdr records)))))
(define (insert! key value table)
(let ((record (assoc key (cdr table))))
(if record
(set-cdr! record value)
(set-cdr! table
(cons (cons key value) (cdr table))))))
(define (make-table)
(list '*table*))
(define (memoize f)
(let ((table (make-table)))
(lambda (x)
(let ((previously-computed-result (lookup x table)))
(or previously-computed-result
(let ((result (f x)))
(insert! x result table)
result))))))
(define memo-fib
(memoize (lambda (n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (memo-fib (- n 1))
(memo-fib (- n 2))))))))
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2))))))
내 컴퓨터에서는 (fib 35) 만 해도 대략 10초 정도 걸린다.
반면 (memo-fib 5000)까지도 5초 안에 결과가 나온다 (..)
> (memo-fib 5000)
387896845438832563370191630832590531208212771464624510616059721489555013
904403709701082291646221066947929345285888297381348310200895498294036143
015691147893836421656394410691021450563413370655865623825465670071252592
990385493381392883637834751890876297071203333705292310769300851809384980
180384781399674888176555465378829164426891298038461377896902150229308247
566634622492307188332480328037503913035290330450584270114763524227021093
463769910400671417488329842289149127310405432875329804427367682297724498
774987455569190770388063704683279481135897373999311010621930814901857081
539785437919530561751076105307568878376603366735544525884488624161921055
345749367589784902798823435102359984466393485325641195222185956306047536
464547076033090242080638258492915645287629157575914234380914230291749108
898415520985443248659407979357131684169286803954530954538869811466508206
686289742063932343848846524098874239587380197699382031717420893226546887
936400263079778005875912967138963421425257911687275560036031137054775472
4604639987588046985178408674382863125
(우와아악)
책의 문제로도 나오고 주의해야 하는 것이, 단순히 (define memo-fib (memoize fib)) 으로 정의해가지곤 같은 효과가 나오지 않는다. memoize를 다시 호출하게 되어있어야 재귀적으로 돌면서 테이블을 계속 찾아볼 수 있는데, (memoize fib)으로 정의해놓으면 처음 받은 그 값만 테이블 확인하고 나머지 과정은 이전처럼 무한 확장의 노가다를 하게 된다.
머리로 알고 있는 것과 실제 돌려본 것은 역시 느낌이 다르네 ㅎㅎ
(define (lookup key table)
(let ((record (assoc key (cdr table))))
(if record
(cdr record)
false)))
(define (assoc key records)
(cond ((null? records) false)
((equal? key (caar records)) (car records))
(else (assoc key (cdr records)))))
(define (insert! key value table)
(let ((record (assoc key (cdr table))))
(if record
(set-cdr! record value)
(set-cdr! table
(cons (cons key value) (cdr table))))))
(define (make-table)
(list '*table*))
(define (memoize f)
(let ((table (make-table)))
(lambda (x)
(let ((previously-computed-result (lookup x table)))
(or previously-computed-result
(let ((result (f x)))
(insert! x result table)
result))))))
(define memo-fib
(memoize (lambda (n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (memo-fib (- n 1))
(memo-fib (- n 2))))))))
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2))))))
내 컴퓨터에서는 (fib 35) 만 해도 대략 10초 정도 걸린다.
반면 (memo-fib 5000)까지도 5초 안에 결과가 나온다 (..)
> (memo-fib 5000)
387896845438832563370191630832590531208212771464624510616059721489555013
904403709701082291646221066947929345285888297381348310200895498294036143
015691147893836421656394410691021450563413370655865623825465670071252592
990385493381392883637834751890876297071203333705292310769300851809384980
180384781399674888176555465378829164426891298038461377896902150229308247
566634622492307188332480328037503913035290330450584270114763524227021093
463769910400671417488329842289149127310405432875329804427367682297724498
774987455569190770388063704683279481135897373999311010621930814901857081
539785437919530561751076105307568878376603366735544525884488624161921055
345749367589784902798823435102359984466393485325641195222185956306047536
464547076033090242080638258492915645287629157575914234380914230291749108
898415520985443248659407979357131684169286803954530954538869811466508206
686289742063932343848846524098874239587380197699382031717420893226546887
936400263079778005875912967138963421425257911687275560036031137054775472
4604639987588046985178408674382863125
(우와아악)
책의 문제로도 나오고 주의해야 하는 것이, 단순히 (define memo-fib (memoize fib)) 으로 정의해가지곤 같은 효과가 나오지 않는다. memoize를 다시 호출하게 되어있어야 재귀적으로 돌면서 테이블을 계속 찾아볼 수 있는데, (memoize fib)으로 정의해놓으면 처음 받은 그 값만 테이블 확인하고 나머지 과정은 이전처럼 무한 확장의 노가다를 하게 된다.
덧글