缓存置换算法

FIFO缓存置换算法

FIFO（First in First out），先进先出。核心原则就是：如果一个数据最先进入缓存中，则应该最早淘汰掉。也就是说，当缓存满的时候，应当把最先进入缓存的数据给淘汰掉，使用python进行了简单实现，注意：其中用到的Node和DoubleLinkList为博客中《《双向链表的原理与实践》》所使用的示例

# -*- coding: UTF-8 -*-

class FIFOCache(object):
    def __init__(self, capacity):
        self.capacity = capacity
        self.size = 0
        self.map = {}
        self.list = DoubleLinkList(self.capacity)

    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

        # 如果key在缓存中 从map中取出key对应的节点取出，并且把新的值赋给该节点，因为值是新的，所以从链表中删除此节点，把该节点重新放到链表尾部
        # 此部分实际做的是替换操作，所以size不需要加1
        if key in self.map:
            node = self.map.get(key)
            self.list.remove(node)
            node.value = value
            self.list.append(node)
        else:
            # 缓存大小和设置的大小相等，则缓存满了,从链表中取出头部节点，并把map中对应的该元素删掉
            if self.size == self.capacity:
                node = self.list.pop()
                del self.map[node.key]
                self.size -= 1
            node = Node(key, value)
            self.list.append(node)
            self.map[key] = node
            self.size += 1

    def print(self):
        self.list.print()


if __name__ == '__main__':
    fifoCache = FIFOCache(2)

    fifoCache.put(1, 1)
    fifoCache.print()

    fifoCache.put(2, 2)
    fifoCache.print()

    print(fifoCache.get(1))

    fifoCache.put(1, 3)
    fifoCache.print()

    fifoCache.put(4, 4)
    fifoCache.print()

    print(fifoCache.get(2))

LRU缓存置换算法

LRU（Least Recently Used）最近最少使用，原理就是，当数据在最近一段时间经常被访问，那么它在以后也会经常被访问。这就意味着，如果经常访问的数据，我们需要然其能够快速命中，而不常访问的数据，我们在容量超出限制内，要将其淘汰。

class LRUCache(object):

    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}
        self.list = DoubleLinkList(self.capacity)

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

        node = self.map.get(key)
        self.list.remove(node)
        self.list.append_front(node)
        return node.value

    def put(self, key, value):

        if key in self.map:
            node = self.map[key]
            self.list.remove(node)
            node.value = value
            self.map[key] = node
            self.list.append_front(node)
        else:
            node = Node(key, value)

            # 如果链表已经满了，删除尾部节点
            if self.list.size >= self.list.capacity:
                old_node = self.list.remove()
                self.map.pop(old_node.key)
            self.map[key] = node
            self.list.append_front(node)

    def print(self):
        self.list.print()


if __name__ == '__main__':
    cache = LRUCache(2)
    cache.put(2, 2)
    cache.print()

    cache.put(1, 1)
    cache.print()

    print(cache.get(1))
    cache.print()

    cache.put(3, 3)

    cache.print()
    print(cache.get(1))
    cache.print()

LFU缓存置换算法

最少使用置换算法基于“如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小”的思路，和LRU的区别是LFU是基于访问次数的，即如果一个元素访问的次数足够多，即使一段时间不访问，也有可能不会被删除，而LRU会把时间上最久没被访问的数据删除

from computer_principle.DoubleLinkedList import DoubleLinkList, Node


class LFUNode(Node):

    def __init__(self, key, value):
        self.freq = 0
        super(LFUNode, self).__init__(key, value)


class LFUCache(object):

    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}
        # key 使用频率 value 频率对应的双向链表
        self.freq_map = {}
        self.size = 0

    def __update_freq(self, node):
        # 拿到节点的使用频率
        freq = node.freq
        # 通过频率找到对应链表，并从链表中删掉该节点
        node = self.freq_map[freq].remove(node)
        # 如果节点删除后，链表为空，则不再缓存此链表
        if self.freq_map[freq].size == 0:
            del self.freq_map[freq]

        freq += 1
        node.freq = freq

        # 如果当前使用频率的链表不存在，则创建一个新的链表缓存
        if freq not in self.freq_map:
            self.freq_map[freq] = DoubleLinkList()
        self.freq_map[freq].append(node)

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

        node = self.map.get(key)
        self.__update_freq(node)
        return node.value

    def put(self, key, value):

        if self.capacity == 0:
            return

        # 如果key已经存在对应的node节点
        if key in self.map:
            # 1.找到该节点
            node = self.map.get(key)
            # 2.更新该节点存在的频率链表
            self.__update_freq(node)
            # 3.更新节点新的值
            node.value = value

        #  如果缓存没有该key
        else:
            # 1.如果当前缓存已经满了
            if self.size == self.capacity:
                # 获取最小的key
                min_freq = min(self.freq_map)
                # 获取最小key对应的链表，并弹出其中的头部节点
                old_node = self.freq_map[min_freq].pop()
                # 删除当前缓存中对应的节点
                del self.map[old_node.key]
                self.size -= 1

            # 2.创建节点
            node = LFUNode(key, value)
            node.freq = 1
            # 3.缓存节点
            self.map[key] = node
            # 4.如果频率缓存中不存在频率为1的这个链表，则创建一个
            if node.freq not in self.freq_map:
                self.freq_map[node.freq] = DoubleLinkList()
            # 缓存频率节点
            self.freq_map[node.freq].append(node)
            self.size += 1

    def print(self):
        print('*******************************')
        for k, v in self.freq_map.items():
            print('Freq = %d' % k)
            self.freq_map[k].print()
        print('*******************************')


if __name__ == '__main__':
    cache = LFUCache(4)
    cache.put(1, 1)
    cache.put(2, 1)
    cache.put(3, 1)
    cache.put(4, 1)
    cache.print()

    print(cache.get(1))
    print(cache.get(2))

    cache.put(5, 1)
    cache.print()