LRU-缓存算法

1. LRU
   1.1. 原理
   LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

1.2. 实现
最常见的实现是使用一个链表保存缓存数据，详细算法实现如下：

1. 新数据插入到链表头部；

2. 每当缓存命中（即缓存数据被访问），则将数据移到链表头部；

3. 当链表满的时候，将链表尾部的数据丢弃。

1.3. 分析
【命中率】

当存在热点数据时，LRU的效率很好，但偶发性的、周期性的批量操作会导致LRU命中率急剧下降，缓存污染情况比较严重。

【复杂度】

实现简单。

【代价】

命中时需要遍历链表，找到命中的数据块索引，然后需要将数据移到头部。

class Node():
    def __init__(self, value):
        self.value = value
        self.next = None


class Cache_LRU():
    def __init__(self,n):
        self.data = None
        self.k = n
        self.count = 0
        self.head = Node(None)
        self.last = self.head

    def data_set(self, value):
        if self.count < self.k:
            #add link
            self.last.next = Node(value)
            self.last = self.last.next
            self.count += 1
        else:
            #remove head
            self.head.next = self.head.next.next
            self.last.next = Node(value)
            self.last = self.last.next
    

    def in_cache(self, node):
        # node.value -> node.next.value
        value = node.value

        if node.next != None:
            if node.next == self.last:
                    self.last = node
            node.value = node.next.value
            tmp = node.next
            node.next = node.next.next
            self.last.next = Node(value)
            self.last = self.last.next
            
    def print_node(self):
        node = self.head
        while(node.next != None):
            print(node.value, end=" ")
            node = node.next
        print(node.value)
        
    def data_get(self,value):
        node = self.head            
        while(node):
            if node.value == value:
                self.in_cache(node)
                return True
            node = node.next
        
        self.data_set(value)
            
            
        

import random

count = 0
cache = Cache_LRU(6)
choices = ["1","ad","adw","adwv","awdwd"]
for i in range(100):
    a =  random.choice(choices)
    if cache.data_get(a):
        count += 1
count 

95