[LeetCode]146. LRU Cacheの詳細説明とコード例
5088 ワード
1、要約
以下の考え方はハッシュと双方向チェーンテーブルの結合使用、キャッシュ設計などの知識点をカバーしている.
2、テーマ
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations:
Follow up: Could you do both operations in O(1) time complexity?
Example:
単純版の最近のキャッシュモデルを設計します.キャッシュスペースには容量制限があり,時間的複雑さの要件はO(1)である.
ここで、「最近使用」とは、最近アクセスされたこと(cache.getによって呼び出されたこと)を意味します.
4、問題を解く構想
以上のcacheの操作は、追加(put)、検索(get)、置換(put)であり、容量制限があるため削除が必要であり、容量が満たされるたびに、最も長く使用されていないノードを削除する.
迅速な追加と削除のために、双方向チェーンテーブルを使用してcacheを設計できます.チェーンテーブルの最初から最後までのデータの順序は、(最近アクセスした)->です.(最も古いアクセス):
1)ノードの追加:新しいノードを表頭に挿入すればよく、時間複雑度O(1);
2)ノードの検索:ノードがクエリされるたびに,ノードをチェーンテーブルヘッダに移動し,時間的複雑度O(n)
3)ノードの置換:検索後に置換(ノードvalueを更新)し、ノードをチェーンテーブルヘッダに移動する.
ノードを検索する際,チェーンテーブルを遍歴する必要があるため,時間的複雑度O(n),O(1)に達するため,データ構造にハッシュ(hash)を加えることが考えられる.
=>双方向チェーンテーブル、ハッシュテーブルの2つのデータ構造で問題を解く必要があります.
概略図は次のとおりです.
5、コード例-Java
---------------------------------------------------------------------------------------------------
このリンクは次のとおりです.http://blog.csdn.net/karen0310/article/details/75039604
作者の労働成果を尊重して、転載して出典を明記してください!
---------------------------------------------------------------------------------------------------
以下の考え方はハッシュと双方向チェーンテーブルの結合使用、キャッシュ設計などの知識点をカバーしている.
2、テーマ
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations:
get
and put
.get(key)
- Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(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.Follow up: Could you do both operations in O(1) time complexity?
Example:
LRUCache cache = new LRUCache( 2 /* capacity */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // returns 1
cache.put(3, 3); // evicts key 2
cache.get(2); // returns -1 (not found)
cache.put(4, 4); // evicts key 1
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4
3、審査問題単純版の最近のキャッシュモデルを設計します.キャッシュスペースには容量制限があり,時間的複雑さの要件はO(1)である.
ここで、「最近使用」とは、最近アクセスされたこと(cache.getによって呼び出されたこと)を意味します.
4、問題を解く構想
以上のcacheの操作は、追加(put)、検索(get)、置換(put)であり、容量制限があるため削除が必要であり、容量が満たされるたびに、最も長く使用されていないノードを削除する.
迅速な追加と削除のために、双方向チェーンテーブルを使用してcacheを設計できます.チェーンテーブルの最初から最後までのデータの順序は、(最近アクセスした)->です.(最も古いアクセス):
1)ノードの追加:新しいノードを表頭に挿入すればよく、時間複雑度O(1);
2)ノードの検索:ノードがクエリされるたびに,ノードをチェーンテーブルヘッダに移動し,時間的複雑度O(n)
3)ノードの置換:検索後に置換(ノードvalueを更新)し、ノードをチェーンテーブルヘッダに移動する.
ノードを検索する際,チェーンテーブルを遍歴する必要があるため,時間的複雑度O(n),O(1)に達するため,データ構造にハッシュ(hash)を加えることが考えられる.
=>双方向チェーンテーブル、ハッシュテーブルの2つのデータ構造で問題を解く必要があります.
概略図は次のとおりです.
5、コード例-Java
import java.util.*;
class Node{
int key;
int value;
Node next;
Node pre;
public Node(int key,int value,Node pre, Node next){
this.key = key;
this.value = value;
this.pre = pre;
this.next = next;
}
}
public class LRUCache {
int capacity;
int count;//cache size
Node head;
Node tail;
HashMaphm;
public LRUCache(int capacity) { //only initial 2 Node is enough, head/tail
this.capacity = capacity;
this.count = 2;
this.head = new Node(-1,-1,null,null);
this.tail = new Node(-2,-2,this.head,null);
this.head.next = this.tail;
hm = new HashMap();
hm.put(this.head.key, this.head);
hm.put(this.tail.key, this.tail);
}
public int get(int key) {
int value = -1;
if(hm.containsKey(key)){
Node nd = hm.get(key);
value = nd.value;
detachNode(nd); //detach nd from current place
insertToHead(nd); //insert nd into head
}
return value;
}
public void put(int key, int value) {
if(hm.containsKey(key)){ //update
Node nd = hm.get(key);
nd.value = value;
//move to head
detachNode(nd); //detach nd from current place
insertToHead(nd); //insert nd into head
}else{ //add
Node newNd = new Node(key,value,null,this.head);
this.head.pre = newNd; //insert into head
this.head = newNd;
hm.put(key, newNd); //add into hashMap
this.count ++;
if(this.count > capacity){ //need delete node
removeNode();
}
}
}
//common func
public void insertToHead(Node nd){
this.head.pre = nd;
nd.next = this.head;
nd.pre = null;
this.head = nd;
}
public void detachNode(Node nd){
nd.pre.next = nd.next;
if(nd.next!=null){
nd.next.pre = nd.pre;
}else{
this.tail = nd.pre;
}
}
public void removeNode(){ //remove from tail
int tailKey = this.tail.key;
this.tail = this.tail.pre;
this.tail.next = null;
hm.remove(tailKey);
this.count --;
}
public void printCache(){
System.out.println("
PRINT CACHE ------ ");
System.out.println("count: "+count);
System.out.println("From head:");
Node p = this.head;
while(p!=null){
System.out.println("key: "+p.key+" value: "+p.value);
p = p.next;
}
System.out.println("From tail:");
p = this.tail;
while(p!=null){
System.out.println("key: "+p.key+" value: "+p.value);
p = p.pre;
}
}
public static void main(String[] args){
LRUCache lc = new LRUCache(3);
lc.printCache();
lc.put(1, 1);
lc.put(2, 2);
lc.put(3, 3);
lc.printCache();
lc.get(2);
lc.printCache();
lc.put(4, 4);
lc.printCache();
lc.get(1);
lc.printCache();
lc.put(3, 33);
lc.printCache();
}
}
【注:】ここではhashmapとhashtableがjavaで使用する違い(異なるクラス、スレッドセキュリティ、拡張などに継承)を区別します.---------------------------------------------------------------------------------------------------
このリンクは次のとおりです.http://blog.csdn.net/karen0310/article/details/75039604
作者の労働成果を尊重して、転載して出典を明記してください!
---------------------------------------------------------------------------------------------------