(lintcode)第24题 LFU缓存

 

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

样例:capacity = 3

set(2,2)
set(1,1)
get(2)
>> 2
get(1)
>> 1
get(2)
>> 2
set(3,3)
set(4,4)
get(3)
>> -1
get(2)
>> 2
get(1)
>> 1
get(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;


  }
}

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

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

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

公众号:秦怀杂货店

 

 

上一篇:Java——值传递与引用传递


下一篇:zxing源码阅读