(lintcode)第24题 LFU缓存

LFU是一个著名的缓存算法，实现LFU中的set 和 get

样例：capacity = 3

set(2,2)set(1,1)get(2)>> 2get(1)>> 1get(2)>> 2set(3,3)set(4,4)get(3)>> -1get(2)>> 2get(1)>> 1get(4)>> 4

我们来看看LFU的百度解释：

LFU（least frequently used (LFU) page-replacement algorithm）。即最不经常使用页置换算法，要求在页置换时置换引用计数最小的页，因为经常使用的页应该有一个较大的引用次数。但是有些页在开始时使用次数很多，但以后就不再使用，这类页将会长时间留在内存中，因此可以将引用计数寄存器定时右移一位，形成指数衰减的平均使用次数。

也就是有一下几点：

1.cache由键值对组成《key，map》，由于hashmap里面key（相当于数组的下标）是唯一的。

2.所有的get操作，我们都是直接查看是否存在，如果不存在这个key，直接返回-1.如果存在这个key，那么更新访问的时间（访问时间来确定哪一个更久没有被访问了），同时访问次数增加。

3.我们用两个属性来保存每一个键值对的状态，一个是调用的次数，一个是最近调用的时间。

4.在set的时候，如果存在这个key，使用次数直接加一次，更新使用的时间，更新成最新的value；否则，创建一个新的键值对，赋予value，调用时间，在这里顺便判断是否容量为0，为0则不进行任何操作。如果容量还没有使用完，则直接插入，如果已经满了，那么我们要移除一个最不常使用而且最久没有使用的，再进行插入。

5.移除的原则：找到使用次数最少的，如果有相同使用次数的，那么直接删除掉使用次数最少的里面最久没有使用的那个。

6.使用的时间属性：set的时候更新，get的时候也要更新。

7.调用次数更新：get和set的时候，只要存在就会加一次。

代码如下：

public class LFUCache {  private Mapcache = null;  private int capacity = 0;  private int used = 0;  public LFUCache(int capacity) {    //评论区指正：hashmap初始化要用2*capacity，否则当数组量很大时，当使用量超过0.75*capacity，hashmap会resize    // 影响性能，最后导致lintcode报超时,谢谢    cache = new HashMap(capacity*2, 0.75f);    this.capacity = capacity;  }  public int get(int key) {    Node node = cache.get(String.valueOf(key));    if (node == null) {      return -1;    }    node.useCount++;    node.lastGetTime = System.nanoTime();    return node.value;  }  public void set(int key, int value) {    Node n = cache.get(String.valueOf(key));    if (n != null) {      n.useCount ++;      n.lastGetTime = System.nanoTime();      n.value = value;      return;    }else{      Node node = new Node();      node.value = value;      node.useCount = 0;      node.lastGetTime = System.nanoTime();      if(this.capacity == 0)return;      if (used < this.capacity) {        used ++;        cache.put(String.valueOf(key), node);      } else {        removeLast();        cache.put(String.valueOf(key), node);      }    }  }  // 淘汰最少使用的缓存  private void removeLast() {    int minCount = Integer.MAX_VALUE;    long getTime = System.nanoTime();    String t = null;    Iteratorit = cache.keySet().iterator();    while(it.hasNext()){      String key = it.next();      Node node = cache.get(key);      if(node.useCount < minCount || (node.useCount == minCount && node.lastGetTime < getTime)){        t = key;        minCount = node.useCount;        getTime = node.lastGetTime;      }    }    cache.remove(t);  }  public class Node {    public int value;    public int useCount;    public long lastGetTime;  }}

如果有所帮助，脸皮厚求个赞~

此文章仅代表自己（本菜鸟）学习积累记录，或者学习笔记，如有侵权，请联系作者删除。人无完人，文章也一样，文笔稚嫩，在下不才，勿喷，如果有错误之处，还望指出，感激不尽~

技术之路不在一时，山高水长，纵使缓慢，驰而不息。

公众号：秦怀杂货店

更多相关文章

随机推荐