2019년 1월 10일 목요일

[on lisp] 5.3 Memoizing 캐싱,메모

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


그림 5.2는 일반화 된 memoizing 유틸리티입니다.
memoize 함수를 제공하고, 이전 호출 결과를 저장하는 해시테이블을 포함하는(closure)를 반환한다.
;; Figure 5.2: Memoizing utility.
(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)  ;; 값이 없는 경우 setf로 해시에 가져온 키값에 설정한 값을 넣음
        (apply fn args))))))) ;; setf는 넣은 값 리턴으로 보임.
     
     
> (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의 구현에는 몇 가지 제한이 있다.
이 함수는 동일한 인수 목록이 있으면 동일하게 리턴값이 나와야 한다.
만약 함수에 키워드 파라미터가 있으면 너무 엄격할 수 있다.
또한 단일 값 함수에만 사용되며 여러 값을 저장하거나 반환 할 수 없다.

댓글 없음 :

댓글 쓰기