LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是如果数据最近被访问过,那么将来被访问的几率也更高,相反如果很长时间未被访问,则它在最近一段时间内也不会被访问。实现方式有很多种,这里先介绍基于数组和单链表的实现方式。
首位置保存最新访问数据,末尾位置优先清理。
public class LRUBasedArray<T> {
private final int DEFAUL_CAPACITY = 10;
private Integer capacity;
private Integer count;
private T[] value;
/**
* 用于元素记录所在数组位置
*/
private Map<T, Integer> holder;
public LRUBasedArray() {
this.capacity = this.DEFAUL_CAPACITY;
this.value = (T[]) new Object[capacity];
this.count = 0;
this.holder = new HashMap<T, Integer>(capacity);
}
public LRUBasedArray(Integer capacity) {
this.capacity = capacity;
this.value = (T[]) new Object[capacity];
this.count = 0;
this.holder = new HashMap<T, Integer>(capacity);
}
/**
* 缓存数据
* @param data
*/
public void add(T data){
if (data == null){
throw new IllegalArgumentException("该缓存容器不支持null!");
}
Integer index = holder.get(data);
if (index != null){
// 向右移动
update(index);
}else {
// 是否已满
if (isFull()){
// 删除,更新
removeAndCache(data);
}else {
// 右移元素更新
cache(data, count);
}
}
}
/**
* 数据之前已在数组中,将数组中的对应数据更新到数组开始。
* @param index
*/
private void update(Integer index){
T key = value[index];
rightOffer(index);
value[0] = key;
holder.put(key,0);
}
/**
* 向数组插入新数据
* @param data
* @param end
*/
private void cache(T data, Integer end){
rightOffer(end);
value[0] = data;
holder.put(data,0);
count++;
}
/**
* 删数组最后一位,并将新数据保存到数组开始
* @param data
*/
private void removeAndCache(T data){
T key = value[--count];
holder.remove(key);
cache(data, count);
}
/**
* index左侧的统一向右移动一位
* @param index
*/
private void rightOffer(Integer index){
for (int i=index;i>0;i--){
value[i] = value[i-1];
holder.put(value[i],i);
}
}
/**
* 判断数组是否已满
* @return
*/
private boolean isFull(){
return count == capacity;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < count; i++) {
sb.append(value[i]);
sb.append(" ");
}
return sb.toString();
}
public static void main(String[] args) {
LRUBasedArray<Integer> array = new LRUBasedArray();
Random random = new Random(20);
int num = 0;
for (int i=0;i<20;i++){
num = random.nextInt(20);
array.add(num);
PrintUtill.println("插入"+ num + ":");
PrintUtill.println(array.toString());
}
}
}
当然也可以首位置优先清理,末尾位置保存最新访问数据,思想类似,这里就不再赘述。
维护一个有序单链表,越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时,我们从链表头开始顺序遍历链表。
public class LRUBaseLinkedList<T> {
/**
* 默认容量
*/
private final int DEFAUL_CAPACITY = 10;
/**
* 头结点
*/
private SNode<T> head;
/**
* 链表长度
*/
private Integer length;
/**
* 链表容量
*/
private Integer capacipy;
public LRUBaseLinkedList() {
this.head = new SNode<>();
this.length = 0;
this.capacipy = DEFAUL_CAPACITY;
}
public LRUBaseLinkedList(Integer capacipy) {
this.head = new SNode<>();
this.length = 0;
this.capacipy = capacipy;
}
/**
* 缓存数据
* @param data
*/
public void add(T data){
SNode preNode = findPreNode(data);
if (preNode != null){
// 删除节点
deleteElemOptim(preNode);
}else {
// 节点不存在,队列是否已满
if (length>=capacipy){
// 已满,删除队尾
deleteElemAtEnd();
}
}
// 将节点插入到头
intsertElemAtBegin(data);
}
/**
* 删除某个结点
* @param node
*/
public void deleteElemOptim(SNode node){
node.setNext(node.getNext().getNext());
length--;
}
/**
* 删除链表尾部的结点
*/
public void deleteElemAtEnd(){
SNode node = head;
if (node.getNext() == null) return;
while (node.getNext().getNext() != null){
node = node.getNext();
}
node.getNext().setNext(null);
length--;
}
/**
* 在头部插入结点
* @param data
*/
public void intsertElemAtBegin(T data){
SNode node = new SNode(data, head.getNext());
head.setNext(node);
length++;
}
/**
* 获取查找到元素的前一个节点
* @param data
* @return
*/
private SNode findPreNode(T data){
SNode node = head;
while (node.getNext() != null){
if (node.getNext().element.equals(data)){
return node;
}
node = node.getNext();
}
return null;
}
private void printAll(){
SNode node = head.getNext();
while (node!=null){
PrintUtill.print(node.element+">");
node = node.getNext();
}
PrintUtill.printlnRule();
}
public class SNode<T> {
private T element;
private SNode next;
public SNode() {
this.next = null;
}
public SNode(T element, SNode next) {
this.element = element;
this.next = next;
}
public T getElement() {
return element;
}
public void setElement(T element) {
this.element = element;
}
public SNode getNext() {
return next;
}
public void setNext(SNode next) {
this.next = next;
}
}
public static void main(String[] args) {
LRUBaseLinkedList<Integer> list = new LRUBaseLinkedList<Integer>();
Random random = new Random(20);
int num = 0;
for (int i=0;i<20;i++){
num = random.nextInt(20);
list.add(num);
PrintUtill.println("插入"+ num + ":");
list.printAll();
}
}
}
缓存是一种提高数据读取性能的技术,在硬件设计、软件开发中都有着非常广泛的应用,比如常见的 CPU 缓存、数据库缓存、浏览器缓存等等。
缓存的大小有限,当缓存被用满时,哪些数据应该被清理出去,哪些数据应该被保留?这就需要缓存淘汰策略来决定。
常见的策略有三种:先进先出策略 FIFO(First In,First Out)、最少使用策略 LFU(Least Frequently Used)、最近最少使用策略 LRU(Least Recently Used)。
单链表、循环链表、双向链表、双向循环链表
一种特殊的单链表。
首节点的前驱指针指向尾节点,尾节点的后继指针指向首节点。
对于执行较慢的程序,可以通过消耗更多的内存(空间换时间)来进行优化。 消耗过多内存的程序,可以通过消耗更多的时间(时间换空间)来降低内存的消耗。
数组简单易用,在实现上使用的是连续的内存空间,可以借助 CPU 的缓存机制,预读数组中的数据,所以访问效率更高。而链表在内存中并不是连续存储,所以对 CPU 缓存不友好,没办法有效预读。
链表本身没有大小的限制,天然地支持动态扩容。
如果代码对内存的使用非常苛刻,那数组就更适合。
内存中没有足够的连续空间时,数组申请空间会失败,导致内存不足(out of memory)。
数组大小固定,当不够用时,需要扩容,一旦扩容就要进行数据复制,而这时非常费时。
内存消耗大,因为要消耗额外的空间存储指针信息。
对链表进行频繁的插入和删除操作,会导致频繁的内存申请和释放,容易造成内存碎片。Java语言中还可能会造成频繁的GC(Garbage Collection,垃圾回收)。