LRUアルゴリズムのO(1)実装
7300 ワード
本文はLOGI'S BLOGに先発し、著者が転載した.
前回は単一チェーンテーブルでLRUを実装したが,ノードの存在と削除のいずれもO(n)操作であると判断した.ページ置換アルゴリズムの場合、速度は通常第1の指標であり、ハッシュ・テーブルはO(1)時間以内にノードを見つけることができ、双方向チェーン・テーブルのテール・ノードの削除操作もO(1)であり、両者を組み合わせたデータ構造を採用すれば、LRUの性能をO(1)に向上させることができると考えられる.同時に、単一チェーンテーブルから双方向チェーンテーブルに追加的に導入されたハッシュ構造を加えると、記憶密度が1/3に低下し、あるいは空間複雑度がO(n)であり、典型的には空間で時間を変える動作であり、実際にはメモリの役割はこのようである.Javaでは、HashMapはハッシュ・リストの典型的な実装であり、チェーン・テーブルの操作を強調するために直接使用し、単純な2つのチェーン・テーブルのみを実装します.
LinkedHashMap
Javaの集合に詳しい人は、LinkedHashMapがHashMapとDoublyLinkedListの実装であることを知っているはずです.したがって、パッケージされたデータ構造を直接使用して、以上の操作を簡潔に実現することができます.
RedisのLRU
Redisはキャッシュ・データベースであり、すべてのデータをメモリにロードすることで最高の読み書き性能を獲得し、新浪熱捜などのホットなビジネスに広く応用されている.
RedisをCacheとして使用する場合、メモリ容量が制限されているため、最大メモリ使用量を構成する必要があり、使用量が参照グローバルクロック objectの初期化および動作毎に、それぞれのlruクロック が更新される.ランダムにいくつかのkeyを選択し、lruクロックに基づいてidleの時間を計算し、ソートしてEvictionPoolに入れ、最終的にidleの時間が最も長いfreeを選択する.なぜランダムに5つしか選択しないのかは,グローバルソートがCPUを非常に消費し,実際のアプリケーションではそれほど正確にする必要がないため,性能の観点からである.
Redisが実現するLRUと理論の違いは主に第3点,すなわちメモリがいっぱいになったときにn個のソートをランダムに選択することにあり,これにより工業分野におけるLRUのベストプラクティスも垣間見ることができる.
参考文献 LRUアルゴリズムの原理と実践 Java集合フレームワークのLinkedHashMap詳細 HashMapにおけるcapacity,loadFactor,threshold,sizeなどの概念の解釈 LRU CacheアルゴリズムRedisにおける応用
前回は単一チェーンテーブルでLRUを実装したが,ノードの存在と削除のいずれもO(n)操作であると判断した.ページ置換アルゴリズムの場合、速度は通常第1の指標であり、ハッシュ・テーブルはO(1)時間以内にノードを見つけることができ、双方向チェーン・テーブルのテール・ノードの削除操作もO(1)であり、両者を組み合わせたデータ構造を採用すれば、LRUの性能をO(1)に向上させることができると考えられる.同時に、単一チェーンテーブルから双方向チェーンテーブルに追加的に導入されたハッシュ構造を加えると、記憶密度が1/3に低下し、あるいは空間複雑度がO(n)であり、典型的には空間で時間を変える動作であり、実際にはメモリの役割はこのようである.Javaでは、HashMapはハッシュ・リストの典型的な実装であり、チェーン・テーブルの操作を強調するために直接使用し、単純な2つのチェーン・テーブルのみを実装します.
package com.logi.algorithm;
import java.util.HashMap;
/**
* @author LOGI
* @version 1.0
* @date 2019/7/10 16:02
*/
public class LRUWithHashMapAndDoublyLinkedList {
DoublyLinkedListNode head;
DoublyLinkedListNode tail;
HashMap map;
int capacity;
int size;
public LRUWithHashMapAndDoublyLinkedList(int capacity) {
this.head = new DoublyLinkedListNode();
this.tail = this.head;
this.map = new HashMap<>();
this.capacity = capacity;
}
public static void main(String[] args) {
LRUWithHashMapAndDoublyLinkedList lru = new LRUWithHashMapAndDoublyLinkedList(2);
lru.put(1, 1);
System.out.println(lru + ", after put(1,1)");
lru.put(2, 2);
System.out.println(lru + ", after put(2,2)");
lru.get(1);
System.out.println(lru + ", after get(1)");
lru.put(3, 3);
System.out.println(lru + ", after put(3,3)");
lru.get(2);
System.out.println(lru + ", after get(2)");
lru.put(4, 4);
System.out.println(lru + ", after put(4,4)");
lru.get(1);
System.out.println(lru + ", after get(1)");
lru.get(3);
System.out.println(lru + ", after get(3)");
lru.get(4);
System.out.println(lru + ", after get(4)");
}
public int get(int key) {
DoublyLinkedListNode current = this.map.get(key);
if (current == null) {
return -1;
} else {
DoublyLinkedListNode save = current;
this.delete(current);
this.insert(save);
return save.value;
}
}
public void put(int key, int value) {
DoublyLinkedListNode current = this.map.get(key);
if (current == null) {
current = new DoublyLinkedListNode(key, value);
if (this.size == this.capacity) {
// map.remove ， ，tail
this.map.remove(this.tail.key);
this.delete(this.tail);
}
this.insert(current);
this.map.put(key, current);
}
}
@Override
public String toString() {
StringBuilder list = new StringBuilder();
DoublyLinkedListNode current = this.head.next;
while (current != null) {
list.append(current.value);
if (current != this.tail) {
list.append("->");
}
current = current.next;
}
return list.toString();
}
/**
*
*
* @param current
*/
public void delete(DoublyLinkedListNode current) {
current.prev.next = current.next;
if (current.next != null) {
current.next.prev = current.prev;
} else {
this.tail = current.prev;
this.tail.next = null;
}
this.size--;
}
/**
*
*
* @param current
*/
public void insert(DoublyLinkedListNode current) {
current.prev = this.head;
current.next = this.head.next;
if (this.head.next == null) {
this.tail = current;
this.tail.next = null;
} else {
this.head.next.prev = current;
}
this.head.next = current;
this.size++;
}
}
class DoublyLinkedListNode {
DoublyLinkedListNode prev;
DoublyLinkedListNode next;
int key;
int value;
public DoublyLinkedListNode() {
}
public DoublyLinkedListNode(int key, int value) {
this.key = key;
this.value = value;
}
}
LinkedHashMap
Javaの集合に詳しい人は、LinkedHashMapがHashMapとDoublyLinkedListの実装であることを知っているはずです.したがって、パッケージされたデータ構造を直接使用して、以上の操作を簡潔に実現することができます.
package com.logi.algorithm;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
/**
* @author LOGI
* @version 1.0
* @date 2019/7/10 17:53
*/
public class LRUWithLinkedHashMap {
Map cache;
int capacity;
public LRUWithLinkedHashMap(int capacity) {
this.capacity = capacity;
// 0.75 ，true ，
this.cache = new LinkedHashMap(capacity, 0.75f, true) {
protected boolean removeEldestEntry(Map.Entry eldest) {
//
return size() > capacity;
}
};
}
public static void main(String[] args) {
// ， LinkedHashMap ，
LRUWithLinkedHashMap lru = new LRUWithLinkedHashMap(2);
lru.put(1, 1);
System.out.println(lru + ", after put(1,1)");
lru.put(2, 2);
System.out.println(lru + ", after put(2,2)");
lru.get(1);
System.out.println(lru + ", after get(1)");
lru.put(3, 3);
System.out.println(lru + ", after put(3,3)");
lru.get(2);
System.out.println(lru + ", after get(2)");
lru.put(4, 4);
System.out.println(lru + ", after put(4,4)");
lru.get(1);
System.out.println(lru + ", after get(1)");
lru.get(3);
System.out.println(lru + ", after get(3)");
lru.get(4);
System.out.println(lru + ", after get(4)");
}
@Override
public String toString() {
StringBuilder list = new StringBuilder();
Iterator iterator = this.cache.values().iterator();
while (iterator.hasNext()) {
list.append(iterator.next()).append("->");
}
return list.substring(0, list.length() - 2);
}
public int get(int key) {
// ， -1
return map.getOrDefault(key, -1);
}
public void put(int key, int value) {
// ，
cache.put(key, value);
}
}
RedisのLRU
Redisはキャッシュ・データベースであり、すべてのデータをメモリにロードすることで最高の読み書き性能を獲得し、新浪熱捜などのホットなビジネスに広く応用されている.
RedisをCacheとして使用する場合、メモリ容量が制限されているため、最大メモリ使用量を構成する必要があり、使用量が
maxmemoryを超えるとLRUなどのポリシーでデータを削除します.以下はRedisにおけるLRUの基本思想である.Redisが実現するLRUと理論の違いは主に第3点,すなわちメモリがいっぱいになったときにn個のソートをランダムに選択することにあり,これにより工業分野におけるLRUのベストプラクティスも垣間見ることができる.
参考文献