LRU

Leave a comment

November 19, 2016 by oneOokay

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) – Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.


真是三刷LRU了啊…

  • get: 一般情况下都用HashMap, 以达到O(1).
  • 由于这题需要频繁的对访问的element放到“头”“尾”,所以用DoubleLinkedlist来作为一个cache。所以在hashmap的帮助下,这里我们移动double linked list 元素是 constant time complexity,不需要查找,只需要移动。
  • 最先想到的是 HashMap<Integer, Integer>,但是因为在hashmap和doublelinkedlist中需要达到一个“映射”的关系,所以hashmap里面应该用<Integer, Node>. (所以这里其实因为我想的这个“映射”关系导致我的接下来的疑惑)

此题我疑惑的地方是:我觉得在移动node的过程中,所影响到的其他的所有node的prev和next发生的改变,都需要去hashmap里面重新update 那个 node。其实不用的。因为我们并没有一个真正意义上的double linked list的存在,并没有一个额外的空间来存储它。它都是由map里面的Node的prev和next来构成的。所以当我们update node的时候,不要想成在update一个实体的list,我们其实就只是在update map中key对应的value(node)而已,所以并不需要额外的再去update map。所以回到前面HashMap和double linked list并不存在一个“映射”关系。

NOTE:

  • 一个method:add_to_head() 来处理move an existing / NEW node to the head两种情况的时候:add_to_head()仅处理把node放到头这个过程,而并不处理把node从原位置移除重接node前后元素。所以对于一个exisiting node,先把它从原linkedlist里面移除,再引用add_to_head(). 这样就能够同时处理旧node和新node了
  • 在set的时候,可以直接引用自身的get()起来简化程序: (参看九章)如果get != -1: get访问对于该node的移动已经在get里面处理完了,所以只需要更新一下它的value就可以了。
  • HashMap.remove(KEY)
  • HashMap.put(KEY, VALUE): 至今对hashmap依然不熟=。=

Oct 29:

Revisit的时候的想法是从Queue或者Stack里面选一种结构来实现:选了queue,因为FIFO。用一个hashmap来实现查找(不要用dictionary,因为dictionary没有if key exisits),两个queue来倒来倒去,结果TLE了。

所以!选择数据结构的时候应该有:Queue, Stack,LinkedList/DoubleLinkedList, HashMap.(以及他们之间的种种结合)。

这题应该用一个DoubleLinkedList来表达cache,另一个HashMap来查找<key, Node>

  • 可以把lru node放到头或者放到尾都可以,我的思维定式是把它想象成一个queue,新cache放在尾部。但是我觉得放head更好一点。所以新cache放HEAD
  • 一个head和一个tail不动,方便放入最新visited的node,也方便delete lru node。
  • 两个key method:(以把lru node处于尾部为例)
    • move_to_head:是把访问存在于cache中的node放到头部。当set一个新的cache的时候,就直接在主函数里面写就可以了,没有必要再弄一个小函数。
    • remove_lru_node: 移除处于尾部的lru node。
  • 注意保持 node和hashmap的一致性。
  • get和set都是对cache的一次访问,都要调整cache的顺序。

Aug 31:

http://bangbingsyb.blogspot.com/2014/11/leetcode-lru-cache.html

上面那个链接里已经写的很好了。

第一要达到一个查找的高效,一定是hashmap;其次进行排序。此处的排序的要求是,每“访问一次”,就需要将此次访问的key放到最前(此处默认最前为最近访问).doubleLinkedList能够迅速的move nodes。可以自己决定头或者尾为需要pop out的位置。每次一个node被访问的时候,将它放到头或者尾。


 public class LRUCache {
 private HashMap<Integer, Node> map;
 private Integer capacity;
 private Node head;
 private Node tail;
 public LRUCache(int capacity) {
 map = new HashMap<Integer, Node>();
 this.capacity = capacity;
 head = new Node(-1, -1);
 tail = new Node(-1, -1);
 head.next = tail;
 tail.prev = head;
 }
 
 public int get(int key) {
 if (map.containsKey(key)){
 Node current = map.get(key);
 current.prev.next = current.next;
 current.next.prev = current.prev;
 add_to_head(current);
 return map.get(key).value;
 }
 
 return -1;
 }
 
 public void set(int key, int value) {
 if (get(key) != -1){
 map.get(key).value = value;
 return;
 }
 
 if (map.size() == capacity){
 remove_lru();
 }
 
 Node current = new Node(key, value);
 map.put(key, current);
 add_to_head(current);
 }
 
 
 private void add_to_head(Node node){
 node.next = head.next;
 head.next.prev = node;
 head.next = node;
 node.prev = head;
 }
 
 
 private void remove_lru(){
 Node lru = tail.prev;
 map.remove(lru.key);
 lru.prev.next = tail;
 tail.prev = lru.prev;
 }
 
 private class Node {
 public Integer key;
 public Integer value;
 public Node next;
 public Node prev;
 
 public Node(Integer k, Integer v){
 this.key = k;
 this.value = v;
 next = null;
 prev = null;
 }
 }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: