Написание кешированной функции в Racket - PullRequest
Новая
       32

Написание кешированной функции в Racket

1 голос
/ 11 ноября 2011

Итак, я работаю над некоторым кодом (прохожу практический экзамен для курса по ракетке), и мне нужно сделать следующее:

Напишите функцию cached-assoc, которая принимает список xs и число n и возвращает функцию, которая принимает один аргумент v и возвращает то же самое, что (assoc v xs) вернет.

Вы должны использовать n-элементный кеш недавних результатов, чтобы, возможно, сделать эту функцию быстрее, чем просто вызывать Assoc. Кеш должен быть вектором длины n, который создается вызовом cached-assoc и используется и, возможно, мутирует каждый раз, когда вызывается функция, возвращаемая cached-assoc.

Кеш начинается пусто (все элементы #f). Когда вызывается функция, возвращаемая cached-assoc, она сначала проверяет кеш на наличие ответа. Если его там нет, он использует assoc и xs, чтобы получить ответ, и если результат не #f (то есть, у xs есть пара, которая соответствует), он добавляет пару в кеш перед возвратом (используя векторный набор!).

Слоты кеша используются в циклическом порядке: при первом добавлении пары в кеш она помещается в позицию 0, следующая пара - в позицию 1 и т. Д. До позиции n - 1 и затем обратно в положение 0 (заменив уже существующую пару), затем в положение 1 и т. д.

Понятия не имею, как это сделать.

Ответы [ 2 ]

4 голосов
/ 13 ноября 2011

Вопрос требует от вас нескольких вещей.Вот неполный список:

  1. , как создать функцию с внутренним неглобальным состоянием.
  2. , как определить функцию, которая может искать элемент в векторе.
  3. как создать функцию, которая действует как обертка для другой.
  4. знает, что делает assoc .
  5. как преобразовать вектор.
  6. как преобразовать локальную переменную.

В качестве вопроса викторины, он действительно использует сразу несколько концепций, и, если у вас нет этих концепций, вы собираетесьесть трудности.

Есть ли проблемы с любым из них, или это что-то еще, что вас застревает?

2 голосов
/ 11 ноября 2011

Вот моя реализация.Это просто, чтобы дать вам представление о том, как подойти к этой проблеме;Я написал это так, что, вероятно, это не сработало бы для представления домашней работы (не то, чтобы я предполагал, что это ваше намерение вообще).: -) 

(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))))
...