寫緩存功能球拍

Question

所以我工作的一些代碼（去在實踐考試對球拍的課程），我必須做到以下幾點：

寫一個函數cached-assoc是獲得一個列表xs和n，並返回一個函數，該函數接受一個參數v並返回（assoc v xs）將返回的相同內容。

您應該使用最近結果的n元素緩存來使該函數可能比調用assoc更快。緩存應該是一個長度爲n的向量，每當調用cached-assoc返回的函數時，調用cached-assoc和used-and-possible-mutated就可以創建這個向量。

緩存開始爲空（所有元素#f）。當調用cached-assoc返回的函數時，它首先檢查緩存中的答案。如果它不在那裏，它使用assoc和xs來得到答案，如果結果不是#f（即，xs有一個匹配的對），它會在返回 （使用向量集！）之前將該對添加到緩存中。 。

槽在循環方式中所使用的高速緩衝存儲器：在第一時間在一對被添加到它被置於0位置的高速緩存中，下一對被置於位置1，等等，直到定位n - 1然後回到位置0（替換那對已經有），然後位置1等

我不知道如何做到這一點。

Answer 1

這個問題需要你幾件事。這裏有一個部分列表：

1. 如何構造一個具有內部非全局狀態的函數。
2. 如何定義一個可以在矢量中搜索項目的函數。
3. 如何構建一個函數作爲另一個函數的包裝。
4. 知道什麼assoc確實。
5. 如何改變一個向量。
6. 如何變異局部變量。

作爲一個測驗問題，它實際上是一次行使幾個概念，如果你沒有這些概念冷落，你會有困難。

確實有這些問題嗎？還是其他問題導致您卡住？

Answer 2

這是我的實現。這只是給你一個想法如何解決這個問題;我以一種可能不會通過作業提交的方式寫作（不是我假設這是你的意圖）。 :-)

(define (cached-assoc xs n) 
    (define cache (make-vector n #f)) 
    (define index 0) 
    (define (fetch-cache k i) 
    (if (or (negative? i) (< i (- index n))) #f 
     (let ((cur (vector-ref cache (modulo i n)))) 
      (if (equal? (car cur) k) cur 
       (fetch-cache k (sub1 i)))))) 
    (define (update-cache val) 
    (vector-set! cache (modulo index n) val) 
    (set! index (add1 index)) 
    val) 
    (lambda (k) 
    (cond ((fetch-cache k (sub1 index))) 
      ((assoc k xs) => update-cache) 
      (else #f))))