如何实现最少使用（LFU）缓存？ [英] How to implement a Least Frequently Used (LFU) cache?

问题描述

最不经常使用（LFU）是一种用于管理计算机内存的缓存算法。此方法的标准特性涉及系统跟踪内存中块被引用的次数。当缓存已满并且需要更多空间时，系统将清除具有最低参考频率的项目。

Least Frequently Used (LFU) is a type of cache algorithm used to manage memory within a computer. The standard characteristics of this method involve the system keeping track of the number of times a block is referenced in memory. When the cache is full and requires more room the system will purge the item with the lowest reference frequency.

什么是实现最近使用的最佳方法？对象的缓存，例如用Java？

What would be the best way to implement a most-recently-used cache of objects, say in Java?

我已经使用LinkedHashMap实现了一个对象（通过保持对象被访问的次数），但是我很好奇

I've already implemented one using LinkedHashMap(by maintaining the no. of times objects are accessed) But I'm curious if any of the new concurrent collections would be better candidates.

请考虑这种情况：假设缓存已满，我们需要为另一个空间留出空间。假设在缓存中记录了两个对象，它们只能访问一次。如果我们知道另一个（不在缓存中的）对象被访问了多次，该删除哪个对象？

Consider this case : Suppose cache is full and we need to make space for another one. Say two objects are noted in cache which are accessed for one time only. Which one to remove if we come to know that other(which is not in cache)object is being accessed for more than once ?

谢谢！

推荐答案

1. 根据我的看法，实现最近使用的对象缓存的最佳方法是：为每个对象添加一个新变量作为 latestTS。 TS代表时间戳。

1. According to me, the best way to implement a most-recently-used cache of objects would be to include a new variable as 'latestTS' for each object. TS stands for timestamp.

//一种静态方法，返回自1970年1月1日以来的当前日期和时间，以毫秒为单位。
long LatestTS = System.currentTimeMillis（） ;

// A static method that returns the current date and time as milliseconds since January 1st 1970 long latestTS = System.currentTimeMillis();

并发Java集合中尚未实现ConcurrentLinkedHashMap。
（参考： Java并发集合API ）。但是，您可以尝试使用 ConcurrentHashMap 和 DoublyLinkedList

ConcurrentLinkedHashMap is not yet implemented in Concurrent Java Collections. (Ref: Java Concurrent Collection API). However, you can try and use ConcurrentHashMap and DoublyLinkedList

关于要考虑的情况：在这种情况下，正如我所说的那样，您可以声明最新的变量，根据最新的变量的值，您可以删除一个条目，然后添加新对象。 （不要忘记更新添加的新对象的频率和最新TS）

About the case to be considered: in such case, as I have said that you can declare latestTS variable, based upon the value of latestTS variable, you can remove an entry and add the new object. (Don't forget to update frequency and latestTS of the new object added)

正如您所提到的，您可以使用 LinkedHashMap ，因为它在O（1）以及订单遍历。
请在LFU缓存中找到以下代码：
（PS：以下代码是标题为如何实现LFU缓存的问题的答案）

As you have mentioned, you can use LinkedHashMap as it gives element access in O(1) and also, you get the order traversal. Please, find the below code for LFU Cache: (PS: The below code is the answer for the question in the title i.e. "How to implement LFU cache")

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;
    }
}

这篇关于如何实现最少使用（LFU）缓存？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！