Как реализовать последний использованный кеш - PullRequest
12 голосов
/ 25 февраля 2009

Каков наилучший способ реализации недавно использованного кэша объектов?

Вот требования и ограничения ...

  • Объекты хранятся в виде пар ключ / значение. Объект / объект, поэтому интерфейс будет немного похож на Hashtable get / put
  • При вызове get этот объект будет отмечен как последний использованный.
  • В любое время наименее использованный объект может быть удален из кэша.
  • Поиск и очистка должны быть быстрыми (как в Hashtable fast)
  • Количество объектов может быть большим, поэтому поиск по списку недостаточно хорош.
  • Реализация должна выполняться с использованием JavaME, поэтому возможности использования стороннего кода или классных библиотечных классов из стандартных библиотек Java ограничены. По этой причине я скорее ищу алгоритмические ответы чем рекомендации нестандартных решений.

Ответы [ 4 ]

22 голосов
/ 25 февраля 2009

Java Collections предоставляют LinkedHashMap из коробки, что хорошо подходит для построения кэшей. Вы, вероятно, не имеете этого в Java ME, но вы можете получить исходный код здесь:

http://kickjava.com/src/java/util/LinkedHashMap.java.htm

Если вы не можете просто скопировать и вставить его, посмотрите на него, и вы начнете реализовывать его для включения в свое мобильное приложение. Основная идея состоит в том, чтобы просто включить связанный список через элементы карты. Если вы будете обновлять его каждый раз, когда кто-либо размещает или получает, вы можете эффективно отслеживать порядок доступа и порядок использования.

В документах содержатся инструкции по созданию кэша MRU путем переопределения метода removeEldestEntry(Map.Entry). Все, что вам действительно нужно сделать, это создать класс, расширяющий LinkedHashMap, и переопределить метод следующим образом:

private static final int MAX_ENTRIES = 100;

protected boolean removeEldestEntry(Map.Entry eldest) {
   return size() > MAX_ENTRIES;
}

Также имеется конструктор , который позволяет вам указать, хотите ли вы, чтобы класс сохранял вещи по порядку, путем вставки или использования, поэтому у вас также есть небольшая гибкость для вашей политики выселения: *

public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder)

Pass true для порядка использования и false для порядка ввода.

7 голосов
/ 25 февраля 2009

ConcurrentLinkedHashMap сложно построить из-за требований к блокировке. LinkedHashMap с блокировкой прост, но не всегда эффективен. Параллельная версия будет пытаться уменьшить количество блокировок, либо путем разделения блокировок, либо в идеале делая операции CAS, чтобы сделать блокировку очень дешевой. Если операции CAS когда-либо становятся дорогостоящими, то подобное разделение сегментов может быть полезным. Поскольку LRU требует записи для каждой операции доступа и использует двусвязный список, это очень сложно реализовать с помощью чисто операций CAS. Я пытался это сделать, но мне нужно продолжать совершенствовать свой алгоритм. Если вы ищете ConcurrentLinkedHashMap, вы увидите страницу моего проекта ...

Если Java ME не поддерживает операции CAS, что, как я ожидаю, будет верным, то базовая синхронизация - это все, что вы можете сделать. Это, вероятно, достаточно хорошо для LHM, учитывая, что я видел проблемы с производительностью только при большом количестве потоков на стороне сервера. Так что +1 к ответам выше.

2 голосов
/ 25 февраля 2009

Зачем реализовывать что-то уже реализованное? Используйте Ehcache .

Однако , если о сторонних библиотеках совершенно не может быть и речи, я думаю, вы ищете реализацию структуры данных, которая выглядит примерно так:

  • В основном это HashMap (расширяет HashMap<Object, Object>, если хотите)
  • Каждое значение на карте указывает на объект в отсортированном списке, на основе которого он используется наиболее часто.
  • Недавно использованные объекты добавляются в начало списка - O(1)
  • Очистка наименее недавно использованного означает усечение конца списка - O(1)
  • По-прежнему дает вам поиск по карте, но в первую очередь сохраняет недавно использованные элементы ...
0 голосов
/ 25 февраля 2009

Другой подход может заключаться в том, чтобы взглянуть на раздел 5.6 Параллелизма Java на практике Брайана Гетца: «Создание эффективного масштабируемого кэша результатов». Посмотрите на Memoizer, хотя вам, возможно, придется настроить его для своих целей.

Кроме того, я не могу понять, почему в Java нет встроенной ConcurrentLinkedHashMap. Эта структура данных была бы очень полезна для построения кэша.

...