LRUアルゴリズム(カスタム双方向リンクを使用して実現)
6508 ワード
LRUアルゴリズム:最近は少なくともアルゴリズムを使用します.
コア思想:最近の訪問回数が一番少ないブロックを淘汰する.
例を挙げます.キャッシュが4つのブロックがあると仮定します.
1 2 3 4 このとき、この4つのブロックがアクセスされてキャッシュにロードされると、このときcpuは2回目のアクセスで、3というブロックにアクセスし、LRUアルゴリズムは3というブロックをシーケンスの先頭に置き換えると仮定して、シーケンス順序は 3 1 2 4,このときcpuは3回目のアクセスでメモリの5番目のワードブロックにアクセスしたと仮定しますが、キャッシュにはこのブロックがありません.LRUアルゴリズムはこのブロックをキャッシュにロードしますが、この時点でキャッシュシーケンスはすでにいっぱいです.だから、LRUアルゴリズムはまずキャッシュの最後のブロック(つまり4)を淘汰し、5番目のワードブロックをキャッシュシーケンスの先頭に加算します.この時のシーケンスは、5 3 1 2となります.
本論文はこのアルゴリズムの実現に重点を置いているので、あまり多くの理論的な説明をしないで、ユーザー定義のチェーン類を使っていますので、コードが多くて、読解性が不足しています.しかし、コアコードの方法に必要な説明を加えました.
コードを実現
コア思想:最近の訪問回数が一番少ないブロックを淘汰する.
例を挙げます.キャッシュが4つのブロックがあると仮定します.
1 2 3 4 このとき、この4つのブロックがアクセスされてキャッシュにロードされると、このときcpuは2回目のアクセスで、3というブロックにアクセスし、LRUアルゴリズムは3というブロックをシーケンスの先頭に置き換えると仮定して、シーケンス順序は 3 1 2 4,このときcpuは3回目のアクセスでメモリの5番目のワードブロックにアクセスしたと仮定しますが、キャッシュにはこのブロックがありません.LRUアルゴリズムはこのブロックをキャッシュにロードしますが、この時点でキャッシュシーケンスはすでにいっぱいです.だから、LRUアルゴリズムはまずキャッシュの最後のブロック(つまり4)を淘汰し、5番目のワードブロックをキャッシュシーケンスの先頭に加算します.この時のシーケンスは、5 3 1 2となります.
本論文はこのアルゴリズムの実現に重点を置いているので、あまり多くの理論的な説明をしないで、ユーザー定義のチェーン類を使っていますので、コードが多くて、読解性が不足しています.しかし、コアコードの方法に必要な説明を加えました.
コードを実現
1.
public class DoubleLinkedQueue {
// Node ， ： （key,value）, （pre）, （next）
private class Node
{
private K key;
private V value;
private Node pre,next;
//
public Node( K key,V value) {
this.key=key;
this.value=value;
this.pre=null;
this.next=null;
}
@Override
//
public String toString() {
return "Node [key=" + key + ", value=" + value + "]";
}
}
//head
private Node head;
////tail
private Node tail;
//size
private int size;
//capacity
private int capacity;
public DoubleLinkedQueue( int capacity) {
this.capacity=capacity;
size=0;
}
public int getSize() {
return size;
}
/* head key ， Node
Node ， get ， get(node,key)
*/
public V get(K key) {
Node node=get(head,key);
return node.value;
}
// node key
private Node get( Node node, K key) {
// ，
if(node==null) {
return null;
}
// node node
Node cur=node;
//cur ， key
while(cur!=null) {
if(key.equals(cur.key))
return cur;
cur=cur.next;
}
// ，
return null;
}
public boolean contains(K key) {
return get(head,key)!=null;
}
//
public Node appendHead(K key,V value) {
// cache ，
if(contains(key)) {
delete(key);
}
// cache ， size==capacity ， ，
else if(size==capacity) {
removeTail();
}
// ，
return addHead(head,key,value);
}
// ，
private Node addHead( Node node,K key,V value) {
// ， ， head tail ， size
if(head==null) {
head=new Node(key,value);
tail=head;
size++;
}
// duil ，
else {
node=new Node(key,value);
node.next=head;
head.pre=node;
head=node;
head.pre=null;
size++;
}
// head
return head;
}
public Node appendTail(K key,V value) {
return addTail(tail,key,value);
}
private Node addTail(Node node,K key,V value) {
if(size==capacity)
{
removeHead();
}
if(tail==null) {
tail=new Node(key,value);
head=tail;
size++;
}else {
node=new Node(key,value);
tail.next=node;
node.pre=tail;
tail=node;
tail.next=null;
size++;
}
return head;
}
public V delTail() {
V value=tail.value;
removeTail();
return value;
}
private Node removeTail() {
if(tail==null)
return null;
if(tail.pre!=null) {
tail=tail.pre;
tail.next=null;
}else {
tail=head=null;
}
size--;
return head;
}
public V delHead() {
return removeHead().value;
}
private Node removeHead() {
if(head==null)
return null;
if(head.next==null) {
head=tail=null;
}
else {
head=head.next;
head.pre=null;
}
size--;
return head;
}
public V delete( K key) {
return remove(head,key);
}
private V remove(Node node,K key) {
Node cur=get(head,key);
V value=cur.value;
if(cur==head)
return delHead();
if(cur==tail)
return delTail();
else {
cur.pre.next=cur.next;
cur.next.pre=cur.pre;
size--;
}
return value;
}
public String toString() {
StringBuilder res=new StringBuilder();
Node cur=head;
res.append("Front:");
for(int i=0;i");
cur=cur.next;
}
res.append(" Tail" );
return res.toString();
}
}
LRUCache
public class LRUCache {
DoubleLinkedQueue doubleList=null;
public LRUCache(int capacity){
doubleList=new DoubleLinkedQueue<>(capacity);
}
public void print() {
System.out.println(doubleList.toString());
}
public void add(K key,V value) {
doubleList.appendHead(key, value);
}
// key ， key, ， ，
public V get(K key) {
if(doubleList.contains(key)) {
V value=doubleList.delete(key);
doubleList.appendHead(key, value);
return value;
}else {
return null;
}
}
public static void main(String args[]) {
LRUCache cache=new LRUCache<>(2);
for(int i=0;i<2;i++)
{
cache.add(i, i);
cache.print();
}
cache.print();
cache.add(0, 9);
cache.print();
cache.add(7, 8);
cache.print();
cache.get(0);
cache.print();
//cache.add(1, 9);
}