Вот большая часть того, что вам нужно: кэш фиксированного размера для наименее использованных данных с O(1) поиском, O(1) вставкой и O(1) удалением.
Немного сложно заставить все эти операции выполняться за O(1), отсюда и такая немного сложная реализация. Я комбинирую хэш-таблицу (для быстрого поиска) с двусвязным списком элементов (для быстрого удаления, изменения порядка и поиска самого старого элемента).
(require 'cl)
(defstruct lru-cache max-size size newest oldest table)
(defstruct lru-item key value next prev)
(defun lru-remove-item (item lru)
(let ((next (lru-item-next item))
(prev (lru-item-prev item)))
(if next (setf (lru-item-prev next) prev)
(setf (lru-cache-newest lru) prev))
(if prev (setf (lru-item-next prev) next)
(setf (lru-cache-oldest lru) next))))
(defun lru-insert-item (item lru)
(let ((newest (lru-cache-newest lru)))
(setf (lru-item-next item) nil (lru-item-prev item) newest)
(if newest (setf (lru-item-next newest) item)
(setf (lru-cache-oldest lru) item))
(setf (lru-cache-newest lru) item)))
;;; Public interface starts here.
(defun* lru-create (&key (size 65) (test 'eql))
"Create a new least-recently-used cache and return it.
Takes keyword arguments
:SIZE the maximum number of entries (default: 65).
:TEST a hash table test (default 'EQL)."
(make-lru-cache
:max-size size
:size 0
:newest nil
:oldest nil
:table (make-hash-table :size size :test test)))
(defun lru-get (key lru &optional default)
"Look up KEY in least-recently-used cache LRU and return
its associated value.
If KEY is not found, return DEFAULT which defaults to nil."
(let ((item (gethash key (lru-cache-table lru))))
(if item
(progn
(lru-remove-item item lru)
(lru-insert-item item lru)
(lru-item-value item))
default)))
(defun lru-rem (key lru)
"Remove KEY from least-recently-used cache LRU."
(let ((item (gethash key (lru-cache-table lru))))
(when item
(remhash (lru-item-key item) (lru-cache-table lru))
(lru-remove-item item lru)
(decf (lru-cache-size lru)))))
(defun lru-put (key value lru)
"Associate KEY with VALUE in least-recently-used cache LRU.
If KEY is already present in LRU, replace its current value with VALUE."
(let ((item (gethash key (lru-cache-table lru))))
(if item
(setf (lru-item-value item) value)
(when (eql (lru-cache-size lru) (lru-cache-max-size lru))
(lru-rem (lru-item-key (lru-cache-oldest lru)) lru))
(let ((newitem (make-lru-item :key key :value value)))
(lru-insert-item newitem lru)
(puthash key newitem (lru-cache-table lru))
(incf (lru-cache-size lru))))))
;;; Exercise for the reader: implement lru-clr and lru-map to complete the
;;; analogy with hash tables.
Для вашего приложения, использующего пары ключей, вы, вероятно, захотите предоставить :test 'equal
для lru-create
. Или см. раздел Определение сравнения хэшей. если вам нужно что-то особенное.
Я дам вам понять, как сделать истечение срока действия по времени; это должно быть прямо отсюда.
(Если кто-нибудь знает более простой способ реализовать это, сохраняя при этом выполнение операций в постоянное время, мне было бы очень интересно это увидеть.)
person
Gareth Rees
schedule
13.07.2011