组成原理-缓存置换算法

这篇笔记记录了4种缓存置换算法

  • 随机置换算法
  • FIFO
  • LRU
  • LFU

FIFO(先进先出算法)

原理：置换缓存时，从硬件角度：当缓存不满时，直接添加所需内容，否则，将最先进入缓存的内容删除，并把需使用的内容添加到缓存。对应的逻辑角度：当缓存不满时，直接添加新节点到链表尾。若缓存满，先将链表头节点删除，并且把新的节点连接到链表尾部。

实现：缓存使用双向链表实现DoubleLinkedList，其中节点由Node实现。 

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
from DoubleLinkedList import Node, DoubleLinkedList


class FIFO(object):
    def __init__(self, capacity):
        self.capacity = capacity
        self.size = 0
        self.map = {}   # {key: node} as search table
        self.dlist = DoubleLinkedList(self.capacity)  # as the cache

    def get(self, key):
        if key not in self.map:
            return -1
        else:
            node = self.map.get(key)
            return node.value

    def put(self, key, value):
        if self.capacity == 0:
            return

        if key in self.map:   # if this key exist in map
            node = self.map.get(key)  # get this key
            self.dlist.remove(node)   # remove the node with this key
            node.value = value     # update the value of that node
            self.dlist.append(node)  # add node to the tail
        else:
            if self.size == self.capacity:   # if cache is full
                node = self.dlist.pop()
                del self.map[node.key]   # delete the node at the head
                self.size -= 1
            node = Node(key, value)
            self.dlist.append(node)   # add new node to the tail
            self.map[key] = node
            self.size += 1

    def print(self):
        self.dlist.print()

测试：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
if __name__ == '__main__':
    cache = FIFO(4)
    cache.put(1, 10)
    cache.put(2, 20)
    cache.put(3, 30)
    cache.print()
    cache.put(1, 12)
    cache.print()
    print("------")
    cache.put(4, 40)
    cache.print()
    cache.put(5, 50)
    cache.print()
    cache.put(1, 11)
    cache.print()
    cache.put(3, 30)
    cache.print()
    print(cache.get(1))
    print(cache.get(2))

结果如下，注释体现了FIFO算法过程：

1
2
3
4
5
6
7
8
9
{1: 10}->{2: 20}->{3: 30}            // 该时刻的缓存内容
{2: 20}->{3: 30}->{1: 12}            // 缓存未满，key=1的接点在缓存中，删除头部key=1的{1: 10}，尾部加入{1: 12}
------
{2: 20}->{3: 30}->{1: 12}->{4: 40}   // 缓存未满，key=4的节点不存在，所以在尾部加{4: 40}
{3: 30}->{1: 12}->{4: 40}->{5: 50}   // 缓存满，key=5的节点不存在，删除头部{2: 20}，尾部加{5: 50}
{3: 30}->{4: 40}->{5: 50}->{1: 11}   // 缓存满，key=1的节点在缓存中，删除key=1的{1: 12}，尾部加{1: 11}
{4: 40}->{5: 50}->{1: 11}->{3: 30}   // 同理
11                                   // 查找key=1的value，存在
-1                                   // 查找key=2的value，不存在

LRU(最不经常使用算法)

待填坑

LFU(最近最少使用算法)

待填坑

附录

Node定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Node:
    def __init__(self, key, val):
        self.key = key
        self.value = val
        self.prev = None
        self.next = None

    def __str__(self):
        val = '{%d: %d}' % (self.key, self.value)
        return val

    def __repr__(self):
        val = '{%d: %d}' % (self.key, self.value)
        return val

双向链表DoubleLinkedList定义

对于成员函数为什么返回看似无用的node节点，经验上讲这样做是最优的。在FIFO的实现过程中会发现，如果成员函数返回其他内容，或无返回值，最终的应用回出现逻辑错误。

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
class DoubleLinkedList:
    def __init__(self, cap=0xffff):
        self.capacity = cap
        self.head = None
        self.tail = None
        self.size = 0

    # add node from head
    def __add_head(self, node):
        if not self.head:
            self.head = node
            self.tail = node
            self.head.next = None
            self.head.prev = None
        else:
            self.head.prev = node
            node.next = self.head
            self.head = node
            self.head.prev = None
        self.size += 1
        return node

    # append node to the tail
    def __add_tail(self, node):
        if not self.tail:
            self.head = node
            self.tail = node
            self.tail.next = None
            self.tail.prev = None
        else:
            self.tail.next = node
            node.prev = self.tail
            self.tail = node
            self.tail.next = None

            self.size += 1
        return node

    # delete tail
    def __del_tail(self):
        if not self.tail:
            return
        node = self.tail
        if node.prev:
            self.tail = node.prev
            self.tail.next = None
            node.prev = None
        else:
            self.tail = self.head = None
        self.size -= 1
        return node

    # delete head
    def __del_head(self):
        if not self.head:  # if empty list
            return
        node = self.head  # assign self.head to a new node
        if node.next:
            self.head = node.next
            self.head.prev = None
            node.next = None
        else:  # only a head exist
            self.head = self.tail = None
        self.size -= 1
        return node

    # remove node in any position
    def __remove(self, node):
        # if node==None, remove tail by default
        if not node:
            node = self.tail
        if node == self.tail:
            self.__del_tail()
        elif node == self.head:
            self.__del_head()
        else:
            node.prev.next = node.next
            node.next.prev = node.prev
        self.size -= 1
        return node

    # APIs
    # pop node from head
    def pop(self):
        return self.__del_head()

    # add node to the tail
    def append(self, node):
        return self.__add_tail(node)

    # add node to the head
    def append_head(self, node):
        return self.__add_head(node)

    # remove
    def remove(self, node=None):
        return self.__remove(node)

    def print(self):
        p = self.head
        line = ''
        while p:
            line += '%s' % p
            p = p.next
            if p:
                line += '->'
        if not line:
            print("empty double linked list")
        print(line)