Как я могу реализовать истекающий кэш LRU в elisp? - PullRequest
Новая
       18

Как я могу реализовать истекающий кэш LRU в elisp?

3 голосов
/ 11 июля 2011

У меня есть данные, которые состоят из следующих трех компонентов:

  • a_path
  • a_key
  • a_value =f(a_path, a_key)

a_value дорого рассчитывать, поэтому я хочу вычислять его редко.В идеальном мире это будет только тогда, когда оно изменится.Итак, мои требования к этому кешу следующие:

  • Кэш LRU с настраиваемым максимальным размером
  • Включено (a_path, a_key)
  • Возможность истечения срока действия записи на основеage (например, пересчитывать каждый час или около того)
  • Возможность истечения срока действия записи на основе expiry_func(a_path, a_key)

Мой поиск в Google не помог мнеВот;Я нахожу много сайтов на Java даже при поиске «elisp LRU cache».

1 Ответ

6 голосов
/ 13 июля 2011

Вот большая часть того, что вам нужно: кэш фиксированного размера с наименьшим количеством использовавшихся за последнее время файлов с поиском 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. Или посмотрите Определение хеш-сравнений , если вам нужно что-то особенное.

Я дам вам понять, как сделать истечение по времени; это должно быть просто отсюда.

(Если кто-нибудь знает более простой способ реализовать это, поддерживая выполнение операций в постоянном времени, мне было бы очень интересно увидеть это.)

...