Как реализовать кеш наименее часто используемого (LFU)?

Ответ 1

• По моему мнению, наилучшим способом реализации самого недавно использованного кеша объектов будет включение новой переменной в качестве "latestTS" для каждого объекта. TS обозначает отметку времени.

  //Статический метод, который возвращает текущую дату и время в миллисекундах с 1 января 1970 г. long latestTS = System.currentTimeMillis();

• ConcurrentLinkedHashMap еще не реализован в параллельных коллекциях Java. (Ссылка: Java Concurrent Collection API). Однако вы можете попробовать и использовать ConcurrentHashMap и DoublyLinkedList

• О рассматриваемом случае: в этом случае, как я уже сказал, вы можете объявить переменную latestTS, основанную на значении переменной latestTS, вы можете удалить запись и добавить новый объект. (Не забудьте обновить частоту и lastTS добавленного нового объекта)

Как вы уже упоминали, вы можете использовать LinkedHashMap, поскольку он дает доступ к элементу в O (1), а также вы получаете порядок прохождения. Пожалуйста, найдите приведенный ниже код для LFU Cache: (PS: приведенный ниже код является ответом на вопрос в заголовке i.e "Как реализовать кеш LFU" )

import java.util.LinkedHashMap;
import java.util.Map;

public class LFUCache {

    class CacheEntry
    {
        private String data;
        private int frequency;

        // default constructor
        private CacheEntry()
        {}

        public String getData() {
            return data;
        }
        public void setData(String data) {
            this.data = data;
        }

        public int getFrequency() {
            return frequency;
        }
        public void setFrequency(int frequency) {
            this.frequency = frequency;
        }       

    }

    private static int initialCapacity = 10;

    private static LinkedHashMap<Integer, CacheEntry> cacheMap = new LinkedHashMap<Integer, CacheEntry>();
    /* LinkedHashMap is used because it has features of both HashMap and LinkedList. 
     * Thus, we can get an entry in O(1) and also, we can iterate over it easily.
     * */

    public LFUCache(int initialCapacity)
    {
        this.initialCapacity = initialCapacity;
    }

    public void addCacheEntry(int key, String data)
    {
        if(!isFull())
        {
            CacheEntry temp = new CacheEntry();
            temp.setData(data);
            temp.setFrequency(0);

            cacheMap.put(key, temp);
        }
        else
        {
            int entryKeyToBeRemoved = getLFUKey();
            cacheMap.remove(entryKeyToBeRemoved);

            CacheEntry temp = new CacheEntry();
            temp.setData(data);
            temp.setFrequency(0);

            cacheMap.put(key, temp);
        }
    }

    public int getLFUKey()
    {
        int key = 0;
        int minFreq = Integer.MAX_VALUE;

        for(Map.Entry<Integer, CacheEntry> entry : cacheMap.entrySet())
        {
            if(minFreq > entry.getValue().frequency)
            {
                key = entry.getKey();
                minFreq = entry.getValue().frequency;
            }           
        }

        return key;
    }

    public String getCacheEntry(int key)
    {
        if(cacheMap.containsKey(key))  // cache hit
        {
            CacheEntry temp = cacheMap.get(key);
            temp.frequency++;
            cacheMap.put(key, temp);
            return temp.data;
        }
        return null; // cache miss
    }

    public static boolean isFull()
    {
        if(cacheMap.size() == initialCapacity)
            return true;

        return false;
    }
}

Ответ 2

Вы можете извлечь выгоду из реализации ActiveMQ в LFU: LFUCache

Они предоставили хорошие функциональные возможности.

Ответ 3

Я думаю, структура данных LFU должна сочетать очередь приоритетов (для поддержания быстрого доступа к элементу lfu) и хэш-карту (для обеспечения быстрого доступа к любому элементу по его ключу); Я бы предложил следующее определение node для каждого объекта, хранящегося в кеше:

class Node<T> {
   // access key
   private int key;
   // counter of accesses
   private int numAccesses;
   // current position in pq
   private int currentPos;
   // item itself
   private T item;
   //getters, setters, constructors go here
}

Вам нужно key для обращения к элементу. Вам нужно numAccesses в качестве ключа для очереди приоритетов. Вам нужно currentPos, чтобы быстро найти позицию позиции pq по ключу. Теперь вы организуете хэш-карту (ключ (Integer) → node (Node<T>)) для быстрого доступа к элементам и очереди с мини-кучей, используя число обращений в качестве приоритета. Теперь вы можете очень быстро выполнять все операции (доступ, добавление нового элемента, обновление номера acceses, удаление lfu). Вам нужно написать каждую операцию тщательно, чтобы она поддерживала все узлы согласованными (количество обращений, их положение в pq и существование на карте хэша). Все операции будут работать с постоянной усредненной временной сложностью, которую вы ожидаете от кеша.

Ответ 4

Как насчет очереди приоритетов? Вы можете сохранить элементы, отсортированные там, с ключами, представляющими частоту. Просто обновите позицию объекта в очереди после посещения. Вы можете обновлять время от времени для оптимизации производительности (но снижения точности).

Ответ 5

Многие реализации, которые я видел, имеют сложность O(log(n)). Это означает, что когда размер кэша равен n, время, необходимое для вставки/удаления элемента в/из chache, является логарифмическим. Такие реализации обычно используют min heap для поддержания частот использования элементов. Корень кучи содержит элемент с наименьшей частотой, и доступ к нему можно получить за O(1) раз. Но чтобы сохранить свойство кучи, мы должны перемещать элемент каждый раз, когда он используется (и частота увеличивается) внутри кучи, чтобы поместить его в правильное положение, или когда нам нужно вставить новый элемент в кэш (и так положить его в кучу). Но сложность среды выполнения может быть уменьшена до O(1), когда мы поддерживаем hashmap (Java) или unordered_map (C++) с элементом в качестве ключа. Кроме того, нам нужны два вида списков, frequency list и elements lists. elements lists содержат элементы с одинаковой частотой, а frequency list содержит element lists.

  frequency list
  1   3   6   7
  a   k   y   x
  c   l       z
  m   n

Здесь в примере мы видим frequency list который имеет 4 элемента (4 elements lists). Список элементов 1 содержит элементы (a,c,m), список элементов 3 содержит элементы (k, l, n) и т.д. Теперь, когда мы используем, скажем, элемент y, мы должны увеличить его частоту и поместить в следующий список. Поскольку список элементов с частотой 6 становится пустым, мы его удаляем. Результат:

  frequency list
  1   3   7
  a   k   y
  c   l   x
  m   n   z

Мы помещаем элемент y в начало elements list 7. Когда мы позже должны удалить элементы из списка, мы начнем с конца (сначала z, затем x а затем y). Теперь, когда мы используем элемент n, мы должны увеличить его частоту и поместить его в новый список с частотами 4:

  frequency list
  1   3   4  7
  a   k   n  y
  c   l      x
  m          z

Надеюсь, идея понятна. Теперь я предоставлю свою реализацию C++ кеша LFU и позже добавлю реализацию Java. В классе есть только 2 открытых метода: void set(key k, value v) и bool get(key k, value &v). В методе get значение для извлечения будет установлено для каждой ссылки при обнаружении элемента, в этом случае метод возвращает значение true. Когда элемент не найден, метод возвращает false.

#include<unordered_map>
#include<list>

using namespace std;

typedef unsigned uint;

template<typename K, typename V = K>
struct Entry
{
    K key;
    V value;
};

template<typename K, typename V = K>
class LFUCache
{
private:
    unordered_map <K, pair<typename list<pair<uint, typename list<typename Entry<K,V>>>>::iterator, typename list<typename Entry<K, V>>::iterator>> cacheMap;
    list<pair<uint, typename list<typename Entry<K, V>>>> elements;
    uint maxSize;
    uint curSize;

    void incrementFrequency(pair<typename list<pair<uint, typename list<Entry<K, V>>>>::iterator, typename list<Entry<K, V>>::iterator> p) {
        if (p.first == prev(elements.end())) {
            elements.push_back({ p.first->first + 1, { {p.second->key, p.second->value} } });
            // erase and insert the key with new iterator pair
            cacheMap[p.second->key] = { prev(elements.end()), prev(elements.end())->second.begin() };
        }
        else {
            // there exist element(s) with higher frequency
            auto pos = next(p.first);
            // same frequency in the next list, add the element in the begin
            if (p.first->first + 1 == pos->first)
                pos->second.push_front({ p.second->key, p.second->value });
            // insert before next list
            else
                pos = elements.insert(pos, { p.first->first + 1 , {{p.second->key, p.second->value}} });

            cacheMap[p.second->key] = { pos, pos->second.begin() };
        }
        if (p.first->second.size() == 1)
            elements.erase(p.first);
        else
            p.first->second.erase(p.second);
    }

    void eraseOldElement() {
        if (curSize == maxSize) {
            if (elements.begin()->second.size() > 0) {
                auto p = std::prev(elements.begin()->second.end());
                cacheMap.erase(p->key);
                elements.begin()->second.pop_back();
                if (elements.begin()->second.size() < 1)
                    elements.erase(elements.begin());
                curSize--;
            }
        }
    }

public:
    LFUCache(uint size) {
        if (size > 0)
            maxSize = size;
        else
            maxSize = 10;
        curSize = 0;
    }
    void set(K key, V value) {
        auto entry = cacheMap.find(key);
        if (entry == cacheMap.end()) {
            eraseOldElement();
            if (elements.begin() == elements.end()) {
                elements.push_front({ 1, { {key, value} } });
            }
            else if (elements.begin()->first == 1) {
                elements.begin()->second.push_front({ key,value });
            }
            else {
                elements.push_front({ 1, { {key, value} } });
            }
            cacheMap.insert({ key, {elements.begin(), elements.begin()->second.begin()} });
            if (curSize < maxSize)
                curSize++;
        }
        else {
            entry->second.second->value = value;
            incrementFrequency(entry->second);
        }
    }

    bool get(K key, V &value) {
        auto entry = cacheMap.find(key);
        if (entry == cacheMap.end())
            return false;
        value = entry->second.second->value;
        incrementFrequency(entry->second);
        return true;
    }
};

Вот примеры использования:

    int main()
    {
      LFUCache2 lc(2);
        lc.put(1, 1);
        lc.put(2, 2);
        int r = lc.get(1);
        assert(r == 1); // found
        lc.put(3, 3);  // evict element 2
        r = lc.get(2);
        assert(r == -1); // not found
        r = lc.get(3);
        assert(r == 3); //found
        lc.put(4, 4); //evict 1
        r = lc.get(1);
        assert(r == -1); //not found
        r = lc.get(3);  //found
        assert(r == 3);
        r = lc.get(4);
        assert(r == 4);
   }