首页 > 代码库 > LRU算法总结
LRU算法总结
LRU算法总结
LRU
LRU-K
Two queues(2Q)
Muti Queue(MQ)
最后
class Node(object): def __init__(self, key=None, value=None, next=None, prev=None): self.key = key self.value = value self.next = next self.prev = prev class LRUCache(object): def __init__(self, capacity): """ :type capacity: int """ self.capacity = capacity # single linked list with a head node # always put new node to the tail # also move the revisted node to the tail self.head = Node() self.tail = self.head self.head.next = self.tail # <key, node.prev> self.hash_table = {} def pop_front(self): del self.hash_table[self.head.next.key] p_next = self.head.next.next self.head.next = p_next # update the reference for new front node self.hash_table[self.head.next.key] = self.head def append(self, node): self.hash_table[node.key] = self.tail self.tail.next = node self.tail = node def move_to_end(self, prev): node = prev.next if node == self.tail: return # disconnect node prev.next = node.next node.next = None self.hash_table[prev.next.key] = prev # append node self.append(node) def get(self, key): """ :type key: int :rtype: int """ if key not in self.hash_table: return -1 prev = self.hash_table[key] val = prev.next.value self.move_to_end(prev) return val def put(self, key, value): """ :type key: int :type value: int :rtype: void """ if key in self.hash_table: prev = self.hash_table[key] prev.next.value = value self.move_to_end(prev) else: self.append(Node(key, value)) if len(self.hash_table) > self.capacity: self.pop_front()
LRU算法总结
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。