基于数据结构和算法的深入应用--2.失效算法与应用
2021-09-09 本文已影响0人
北有榆树
失效算法常见于缓存系统中.因为缓存往往占据大量内存,而内存空间是相对昂贵且空间有限,那么针对一部分值,就要依据相应的算法进行失效或者移除操作.
2.1 先来先淘汰(FIFO)
概述
first in first out,先来先淘汰.这种算法在每一次新数据插入时,如果队列已满,就将最早插入的数据移除.
实现
可以方便的借助linkedlist来实现
package com.zhb.algorithm;
import org.junit.jupiter.api.Test;
import java.util.Iterator;
import java.util.LinkedList;
/**
* @author zhuohb
* @date 2021/9/6 1:44 下午
*/
public class Fifo {
LinkedList<Integer> fifo = new LinkedList<Integer>();
int size = 3;
/**
* 添加元素
*/
public void add(int i) {
fifo.addFirst(i);
if (fifo.size() > size) {
fifo.removeLast();
}
System.out.println("当前数据为"+this.fifo);
}
/**
* 缓存命中
* @param i
*/
public void read(int i){
Iterator<Integer> iterator = fifo.iterator();
while (iterator.hasNext()) {
int j = iterator.next();
if (i == j) {
System.out.println("找到了!");
System.out.println("当前数据为"+this.fifo);
return;
}
}
System.out.println("没找到!");
System.out.println("当前数据为"+this.fifo);
}
@Test
public void test() {
Fifo fifo = new Fifo();
System.out.println("添 1,2,3");
fifo.add(1);
fifo.add(2);
fifo.add(3);
System.out.println("添 4");
fifo.add(4);
System.out.println("读 2");
fifo.read(2);
System.out.println("读 100");
fifo.read(100);
System.out.println("添 5");
fifo.add(5);
}
}
优缺点
- 实现非常简单
- 不管元素的使用情况,哪怕有些数据会被频繁使用也可能被踢掉
2.2 最近最少使用(LRU)
概述
Least Recently Used,最近最少使用,淘汰最后一次使用时间最久远的数据.FIFO非常粗暴,不管有没有用到,直接踢掉时间久的元素,而LRU认为,最近频繁使用过的数据,将来很大程度上也会被频繁使用,故而淘汰那些懒惰的数据.LinkedHashMap 数组 链表均可实现LRU, 下面仍然以链表为例: 新加入的数据放在头部,最近访问的也移动到头部,空间满时,将尾部元素删除
package com.zhb.algorithm;
import org.junit.jupiter.api.Test;
import java.util.Iterator;
import java.util.LinkedList;
/**
* @author zhuohb
* @date 2021/9/6 2:12 下午
*/
public class Lru {
LinkedList<Integer> lru = new LinkedList<Integer>();
int size = 3;
/**
* 添加元素
*/
public void add(int i) {
lru.addFirst(i);
if (lru.size() > size) {
lru.removeLast();
}
System.out.println("当前数据为" + this.lru);
}
/**
* 缓存命中
*/
public void read(int i) {
Iterator<Integer> iterator = lru.iterator();
int index = 0;
while (iterator.hasNext()) {
Integer next = iterator.next();
if (i == next) {
System.out.println("找到了!");
lru.remove(index);
lru.addFirst(next);
System.out.println("当前数据为:" + this.lru);
return;
}
index++;
}
System.out.println("未找到!");
System.out.println("当前数据为:" + this.lru);
}
@Test
public void test() {
Lru lru = new Lru();
System.out.println("添 1,2,3");
lru.add(1);
lru.add(2);
lru.add(3);
System.out.println("添 4");
lru.add(4);
System.out.println("读 2");
lru.read(2);
System.out.println("读 100");
lru.read(100);
System.out.println("添 5");
lru.add(5);
}
}
2.3 最不经常使用(LFU)
概述
Least Frequently Used, 它要淘汰的是最近一段时间内,使用次数最少的值.可以认为比LRU多了一重判断.LFU需要时间和次数两个维度的参考指标.需要注意的是,两个维度就可能涉及到同一个时间段内,访问次数相同的情况,就必须内置一个计数器和一个队列,计数器算数,队列放置相同计数时的访问时间
实现
package com.zhb.algorithm.lfu;
import lombok.Data;
/**
* @author zhuohb
* @date 2021/9/9 10:04 上午
*/
@Data
public class Entity implements Comparable<Entity> {
private Integer key;
private int count;
private long lastTime;
public Entity(Integer key, int count, long lastTime) {
this.key = key;
this.count = count;
this.lastTime = lastTime;
}
@Override
public int compareTo(Entity entity) {
int compare = Integer.compare(this.count, entity.count);
return compare == 0 ? Long.compare(this.lastTime, entity.lastTime) : compare;
}
}
package com.zhb.algorithm.lfu;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
/**
* @author zhuohb
* @date 2021/9/9 10:17 上午
*/
public class Lfu {
private final int size = 3;
private Map<Integer, Integer> cache = new HashMap<>();
private Map<Integer, Entity> count = new HashMap<>();
/**
* 投放
*
* @param key
* @param value
*/
public void put(Integer key, Integer value) {
Integer v = cache.get(key);
if (v == null) {
if (cache.size() == size) {
this.removeElement();
}
count.put(key, new Entity(key, 1, System.currentTimeMillis()));
} else {
this.addCount(key);
}
cache.put(key, value);
}
/**
* 读取
*
* @param key
* @return
*/
public Integer get(Integer key) {
Integer value = cache.get(key);
if (value != null) {
this.addCount(key);
return value;
}
return null;
}
/**
* 淘汰元素
*/
private void removeElement() {
Entity entity = Collections.min(count.values());
cache.remove(entity.getKey());
count.remove(entity.getKey());
}
private void addCount(Integer key) {
Entity entity = count.get(key);
entity.setCount(entity.getCount() + 1);
entity.setLastTime(System.currentTimeMillis());
}
public static void main(String[] args) {
Lfu lfu = new Lfu();
//前3个容量没满 1,2,3 均可加入
System.out.println("添加 1,2,3");
lfu.put(1, 1);
lfu.put(2, 2);
lfu.put(3, 3);
System.out.println("cache=" + lfu.cache);
System.out.println("count=" + lfu.count);
//1,2有访问,3没有, 加入4,淘汰3
System.out.println("读 1,2");
lfu.get(1);
lfu.get(2);
System.out.println("cache=" + lfu.cache);
System.out.println("count=" + lfu.count);
System.out.println("添加 4");
lfu.put(4, 4);
System.out.println("cache=" + lfu.cache);
System.out.println("count=" + lfu.count);
//2是3次, 1 4 是2次 但是4加入较晚,再加入5时淘汰1
System.out.println("读取 2,4");
lfu.get(2);
lfu.get(4);
System.out.println("cache=" + lfu.cache);
System.out.println("count=" + lfu.count);
System.out.println("添加 5");
lfu.put(5, 5);
System.out.println("cache=" + lfu.cache);
System.out.println("count=" + lfu.count);
}
}
2.4 应用案例
redis属于缓存失效的典型应用场景,常用策略是......
