[on lisp] 5.3 Memoizing 캐싱,메모

5.3 Memoizing
어떤 함수가 계산하는데 비용이 많이 들고, 때로는 같은 호출을 두 번 이상하는 경우가 있다.
이전의 모든 호출의 반환 값을 캐싱하고 함수가 호출 될 때마다 다음과 같이 memoize하는 것이 좋다.
값이 저장되었는지 확인하려면 먼저 캐시를 살펴보십시오.


그림 5.2는 일반화 된 memoizing 유틸리티이다.
memoize 함수를 제공하고, 이전 호출 결과를 저장하는 해시테이블을 포함하는(closure)를 반환한다.

;; Figure 5.2: Memoizing utility.

;; memoize는 cache라는 해시테이블을 가지는 람다를 던진다.
;; 해당 람다는 구조분해를 한 다음에,
;; gethash의 리턴값은 (value, present-p)임 이걸 (val win)에 각각들어감.
;; (gethash에서 args를 키로 한 값을 가져온다.
;; 값이 없는 경우 setf로 해시에 가져온 키값에 설정한 값을 넣음
;; setf는 넣은 값 리턴으로 보임.
(defun memoize (fn)
  (let ((cache (make-hash-table :test #'equal)))
    #'(lambda (&rest args) 
        (multiple-value-bind (val win) (gethash args cache)
          (if win  ;; 값이 있으면
              val  ;; 해당 값 리턴
              (setf (gethash args cache)  
                    (apply fn args))))))) 

     
> (setq slowid (memoize #'(lambda (x) (sleep 5) x)))
Interpreted-Function C38346
> (time (funcall slowid 1))
Elapsed Time = 5.15 seconds
1
> (time (funcall slowid 1))
Elapsed Time = 0.00 seconds
1    

memoized 함수를 사용하면, 반복 호출은 해시 테이블 조회 일뿐이다.
물론 초기 호출마다 조회 비용이 추가되지만, 계산하기에 충분히 비싼 함수를 메모하는 것이므로 비용은 비교할 때 중요하지 않다고 가정하는 것이 합리적이다.
대부분의 용도에 적합하지만, memoize의 구현에는 몇 가지 제한이 있다.
이 함수는 동일한 인수 목록이 있으면 동일하게 리턴값이 나와야 한다.
만약 함수에 키워드 파라미터가 있으면 너무 엄격할 수 있다.
또한 단일 값 함수에만 사용되며 여러 값을 저장하거나 반환 할 수 없다.