이 문제는 자신이 이미 했던 것을 메모하여

다른 작업을 할 때 기존에 했던 작업인 경우 다시 계산하는 것이 아니라

적은 것을 찾아 그것을 불러와 쓰는 것입니다.

먼저 (memo-fib 3)의 계산 과정을 살펴보았습니다...만,

그리는 것이 혼란스럽고 귀찮아서 하지 않았습니다.

다만 처음에 이런 환경에서 table에 자신이 계산한 결과를 저장한다고 생각하였습니다.

왜 n번째 피보나치 수를 n에 비례하는 단계 만에 찾을 수 있는 이유는

피보나치 수열을 찾는 행위를 나무를 그리는 것이라 할 때

Root에 n을 넣은 후 왼쪽만을 살펴본다면 n이 하나씩 줄어듬을 알 수 있습니다.

왜냐하면 fib(n) = fib(n-1) + fib(n-2)이기 때문입니다.

그리고 한 번 계산한 것은 table에 저장되어있기에

fib(2) ~ fib(n-1)까지 한 번만 계산하므로 n에 비례하는 단계라 생각합니다.

(나무의 height와 관련이 있을 듯싶습니다.)

그리고 memo-fib를 (memoize fib)로 정의하였을 때 성능이 어떠한지 생각하였습니다.

처음에는 이 둘이 같은 효과를 낸다고 생각했습니다.

하지만 그렇지 않다는 것을 직접 확인하였습니다.

위의 결과에서 처음 것은 책에 적혀진 코드이고,

두 번째 것은 memo-fib를 (memoize fib)로 정의한 것입니다.

처음 것은 n이 1000일 때 빠른 시간안에 답이 나왔지만,

뒤의 것은 실행 후 밥을 먹고 스트레칭까지 했음에도 끝나지 않았더군요.;;

그래서 코드에 문제가 있는 것이 아니라 시간이 오래 걸린다는 것을 보여주고자

n이 30일 때 확인해보았습니다.

처음 것은 거의 순간에 가까울 정도의 성능을 나타내지만,

뒤의 것은 그렇지 못함을 보여주고 있습니다.

왜 이러한지 생각해보았습니다.

잠시 후 그 이유를 생각할 수 있었습니다.

처음 코드의 경우 table안에 fib의 계산된 값이 저장됩니다.

따라서 저 곳에 계속해서 접근하여 쓸 수 있는 것이지요.

하지만 두 번째 코드의 경우 table을 계속해서 여러 개 만들기에

이미 했던 계산을 다시 하는 결과가 나온다고 생각합니다.

이는 아직 환경 계산법(The Environment Model of Evaluation)에 익숙하지않아

그 돌아가는 원리를 꿰뚫고 있지 못하기 때문이라 생각합니다.

이 내용은 알고리즘 시간에 Dynamic Programming이라는 이름으로 배웠습니다.

알고리즘 강의 PDF

여기서는 배열을 사용하였네요.^^

저 얘기를 들을 때 생각한 것이지만,

만약 탐색하는 것이 계산하는 것보다 느리다면 별 효과가 없겠다고 생각했습니다.

하지만 대체로 탐색보다는 계산하는 것이 느리거나

계산의 횟수가 매우 많을 경우 많은 도움이 되겠지요.^^

참조

해럴드 애빌슨, 김재우 역, <컴퓨터 프로그램의 구조와 해석>, 인사이트, 2007, pp. 353

http://security.re.kr/~sjkim/sjkim_lectures.html

(define false (= 0 1))
;;;SECTION 3.3.3

(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)))))
  'ok)

(define (make-table)
  (list '*table*))

; exercise 3.27
(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

(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-fib1
  (memoize (lambda (n)
             (cond ((= n 0) 0)
                   ((= n 1) 1)
                   (else (+ (memo-fib1 (- n 1))
                            (memo-fib1 (- n 2))))))))

(define memo-fib2
  (memoize fib))

; check time
(define (timed-fib-test n case)
  (if (= case 1)
      (start-fib-test1 n (current-milliseconds))
      (start-fib-test2 n (current-milliseconds))))

(define (start-fib-test1 n start-time)
  (let ((fib-n (memo-fib1 n)))
    (if fib-n
        (report-fib n (- (current-milliseconds) start-time) fib-n)
        (= 0 1)
        )))

(define (start-fib-test2 n start-time)
  (let ((fib-n (memo-fib2 n)))
    (if fib-n
        (report-fib n (- (current-milliseconds) start-time) fib-n)
        (= 0 1)
        )))

(define (report-fib n elapsed-time result)
  (newline)
  (display "n : ")
  (display n)
  (display ",  time : ")
  (display elapsed-time)
  (display ",  result : ")
  (display result))

; execute
(timed-fib-test 3 1)
(timed-fib-test 3 2)
(timed-fib-test 30 1)
(timed-fib-test 30 2)

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.