Java笔记··By/蜜汁炒酸奶

单链表实现LRU缓存淘汰算法

LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是如果数据最近被访问过,那么将来被访问的几率也更高,相反如果很长时间未被访问,则它在最近一段时间内也不会被访问。实现方式有很多种,这里先介绍基于数组和单链表的实现方式。

基于数组的LRU

首位置保存最新访问数据,末尾位置优先清理。

  1. 如果此数据之前已经被缓存在数组中了,查找到其位置并从原位置中删除该数据,将位置之前的数据依次右移一位,保存此数据到数组第一个元素位置上。
  2. 如果此数据没有在缓存数组中,又可以分为两种情况:
    • 如果此时缓存未满,将数组中数据全部右移一位,保存此数据到数组第一个元素位置上。
    • 如果此时缓存已满,将数组最后一位数据删除,再将数组中数据全部右移一位,保存此数据到数组第一个元素位置上。
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());
        }
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

当然也可以首位置优先清理,末尾位置保存最新访问数据,思想类似,这里就不再赘述。

基于单链表

维护一个有序单链表,越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时,我们从链表头开始顺序遍历链表。

  1. 如果此数据之前已经被缓存在链表中了,我们遍历得到这个数据对应的结点,并将其从原来的位置删除,然后再插入到链表的头部。
  2. 如果此数据没有在缓存链表中,又可以分为两种情况:
    • 如果此时缓存未满,则将此结点直接插入到链表的头部;
    • 如果此时缓存已满,则链表尾结点删除,将新的数据结点插入链表的头部。
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();
        }

    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161

延伸

什么是缓存

缓存是一种提高数据读取性能的技术,在硬件设计、软件开发中都有着非常广泛的应用,比如常见的 CPU 缓存、数据库缓存、浏览器缓存等等。

缓存的大小有限,当缓存被用满时,哪些数据应该被清理出去,哪些数据应该被保留?这就需要缓存淘汰策略来决定。

有哪些缓存淘汰策略?

常见的策略有三种:先进先出策略 FIFO(First In,First Out)、最少使用策略 LFU(Least Frequently Used)、最近最少使用策略 LRU(Least Recently Used)。

参考资料

数据结构与算法之美

Preview
Loading comments...
0 条评论

No Data

example
Preview