美文网首页
2021-08-01 手撕LRU

2021-08-01 手撕LRU

作者: 何几时 | 来源:发表于2021-08-01 22:37 被阅读0次
    class Node:
        def __init__(self, key, val):
            self.key = key
            self.val = val
            self.prev = None
            self.next = None
    
    
    class DoubleList:
        def __init__(self):
            # 头指针、尾指针
            self.head = Node(0, 0)
            self.tail = Node(0, 0)
            self.head.next = self.tail
            self.tail.prev = self.head
    
            self.lenSize = 0
    
        # 尾插、头出、任意删
        def add_last(self, x):
            x.next = self.tail
            x.prev = self.tail.prev
            self.tail.prev.next = x
            self.tail.prev = x
            self.lenSize += 1
    
        def pop_head(self):
            if self.lenSize > 0:
                tmp = self.head.next
                self.remove_anywhere(tmp)
                return tmp
    
        def remove_anywhere(self, x):
            x.prev.next = x.next
            x.next.prev = x.prev
            self.lenSize -= 1
    
        def get_size(self):
            return self.lenSize
    
    
    class LRU:
        def __init__(self, cap):
            self.map = {}
            self.cache = DoubleList()
            # 最大容量
            self.cap = cap
    
        def get(self, key):
            if key in self.map:
                self.make_recently(key)
                return self.map[key].val
            else:
                return -1
    
        def put(self, key, val):
            if key in self.map:
                self.remove(key)
                self.add_recently(key, val)
                return
            if self.cache.lenSize == self.cap:
                self.remove_least_used()
            self.add_recently(key, val)
    
        # 对手机后台的操作
        # 1. 打开新应用
        def add_recently(self, key, val):
            node = Node(key, val)
            node.prev = self.cache.tail.prev
            self.cache.tail.prev.next = node
            self.cache.tail.prev = node
            node.next = self.cache.tail
            # 放进map
            self.map[key] = node
    
        # 2. 打开后台应用
        def make_recently(self, key):
            node = self.map[key]
            self.cache.remove_anywhere(node)
            self.cache.add_last(node)
    
        # 3. 划掉后台应用
        def remove(self, key):
            node = self.map[key]
            self.cache.remove_anywhere(node)
            self.map.pop(key)
    
        # 4. 杀后台
        def remove_least_used(self):
            tmp = self.cache.pop_head()
            self.map.pop(tmp.key)
    

    相关文章

      网友评论

          本文标题:2021-08-01 手撕LRU

          本文链接:https://www.haomeiwen.com/subject/iqarvltx.html