LRUCache is a very common caching implementation, and we’ll simply implement it in Python

define

LRU is an abbreviation for Least Recently Used. LRUCache means a cache with a capacity to discard an old value when the cache is full and new values need to be inserted. How to eliminate, this time you need to use the LRU algorithm.

LRU implies such functionality

Get ('a') #... get('a') #... Countless cache. Get (' a ') cache. Get (' b ') cache. The put (' c ', 'c - value') # cache = > {' b ':' - the value b ', 'c' : '- the value c}Copy the code

We can see that no matter how many times a gets before A, as long as the last get(‘b’) is after the last get(‘a’), then the elimination of B must take precedence over A.

implementation

To ensure that the read and write complexity of LRUCache is O(1), we cannot simply use a map. In simple terms, we can implement it using bidirectional linked lists and dictionaries.

To quickly find the heads and tails of bidirectional lists, we need a virtual head node whose next pointer always points to the real head node (hereinafter referred to as the head node); Similarly, there is a virtual tail node whose pre pointer always points to the real tail node (hereafter referred to as the tail node).

The head node of the bidirectional list is the point with the lowest elimination priority, and the tail node is the point with the lowest elimination priority.

The val field of the bidirectional list points to an array [key, value], so if we find the list node, we can quickly find its position in the map.

The map key is the same as the original key, but the value is the node of the corresponding bidirectional linked list.

Then the two methods corresponding to LRUCache get put, we can think of the following ideas:

get(key)

Get does not affect the current length. If the key exists, simply move the node corresponding to the key to the head of the list

put(key, value)

  • If the key already exists, we just need to update the node value.

  • If the key exists, then we need to construct a node and insert it into the head of the list

    • If the capacity is not full, leave it alone
    • If the capacity is full, we need to remove the node at the end of the list and remove it from the map as well
# -*- coding: utf-8 -*- import sys class ListNode(object): """ LinkedListNode """ __slots__ = ['val', 'next', 'pre'] def __init__(self, x): self.val = x self.next = None self.pre = None class LinkedList(object): """ LinkedList """ __slots__ = ['head', 'tail', 'length'] def __init__(self): """ init """ self.head, self.tail = ListNode(-1), ListNode(-1) self.head.next = self.tail self.tail.pre = self.head self.length = 0 def insert_head(self, node): """ insert a value to head :param node: the value :return: ListNode the node has been inserted """ node.next = self.head.next self.head.next.pre = node node.pre = self.head self.head.next = node self.length += 1 return node def insert_tail(self, node): """ insert a node to tail :param node: the value :return: ListNode the node has been inserted """ node.pre = self.tail.pre node.next = self.tail self.tail.pre = node self.length += 1 return node def pop_head(self): """ pop a node from head :return: ListNode the node has been popped """ if self.length == 0: return None tempNode = self.head.next.next tempNode.pre = self.head self.head.next = tempNode self.length -= 1 return tempNode def remove_node(self, node): """ remove a node from linkedlist :param node: ListNode :return: ListNode the node has been removed """ node.next.pre = node.pre node.pre.next = node.next self.length -= 1 def pop_tail(self): """ pop a node from tail :return: ListNode the node has been popped """ if self.length == 0: return None shouldRemoveNode = self.tail.pre tempNode = shouldRemoveNode.pre tempNode.next = self.tail self.tail.pre = tempNode self.length -= 1 return shouldRemoveNode def print_self(self): if self.length == 0: print('none') return current_node = self.head.next while current_node.next is not None: sys.stdout.write(str(current_node.val[0]) + ":" + str(current_node.val[1]) + " => ") current_node = current_node.next if  current_node.next is None: break sys.stdout.write(" None ") sys.stdout.write(" :: Length: " + str(self.length)) sys.stdout.flush() print('') class LRUCache(object): """ LRUCache """ __slots__ = ['map', 'linkedlist', 'cap'] def __init__(self, cap): self.cap = cap self.map = {} self.linkedlist = LinkedList() def put(self, key, value): # if this key is exist, just update the value of the node and move this node to head if key in self.map: node = self.map[key] node.val[1] = value self.get(key) self.linkedlist.print_self() return # not exist yet, insert this value to head and put this node to map newNode = self.linkedlist.insert_head(ListNode([key, value])) self.map[key] = newNode # check the capacity, remove the tail node if LRUCache is full if self.linkedlist.length > self.cap: oldNode = self.linkedlist.pop_tail() oldKey = oldNode.val[0] self.map.pop(oldKey) self.linkedlist.print_self() def get(self, key): if key not in self.map: self.linkedlist.print_self() return -1 # get the node, move this node to head node = self.map[key] self.linkedlist.remove_node(node) self.linkedlist.insert_head(node) # return  the value self.linkedlist.print_self() return node.val[1] cmds = ["put", "put", "put", "put", "put", "get", "put", "get", "get", "put", "get", "put", "put", "put", "get", "put", "get", "get", "get", "get", "put", "put", "get", "get", "get", "put", "put", "get", "put", "get", "put", "get", "get", "get", "put", "put", "put", "get", "put", "get", "get", "put", "put", "get", "put", "put", "put", "put", "get", "put", "put", "get", "put", "put", "get", "put", "put", "put", "put", "put", "get", "put", "put", "get", "put", "get", "get", "get", "put", "get", "get", "put", "put", "put", "put", "get", "put", "put", "put", "put", "get", "get", "get", "put", "put", "put", "get", "put", "put", "put", "get", "put", "put", "put", "get", "get", "get", "put", "put", "put", "put", "get", "put", "put", "put", "put", "put", "put", "put"] params = [[10, 13], [3, 17], [6, 11], [10, 5], [9, 10], [13], [2, 19], [2], [3], [5, 25], [8], [9, 22], [5, 5], [1, 30], [11], [9, 12], [7], [5], [8], [9], [4, 30], [9, 3], [9], [10], [10], [6, 14], [3, 1], [3], [10, 11], [8], [2, 14], [1], [5], [4], [11, 4], [12, 24], [5, 18], [13], [7, 23], [8], [12], [3, 27], [2, 12], [5], [2, 9], [13, 4], [8, 18], [1, 7], [6], [9, 29], [8, 21], [5], [6, 30], [1, 12], [10], [4, 15], [7, 22], [11, 26], [8, 17], [9, 29], [5], [3, 4], [11, 30], [12], [4, 29], [3], [9], [6], [3, 4], [1], [10], [3, 29], [10, 28], [1, 20], [11, 13], [3], [3, 12], [3, 8], [10, 9], [3, 26], [8], [7], [5], [13, 17], [2, 27], [11, 15], [12], [9, 19], [2, 15], [3, 16], [1], [12, 17], [9, 1], [6, 19], [4], [5], [5], [8, 1], [11, 7], [5, 2], [9, 28], [1], [2, 2], [7, 4], [4, 22], [7, 24], [9, 26], [28] 13,, [11, 26]] def print_list(l): sys.stdout.write('[') sys.stdout.write(', '.join(str(p) for p in l)) sys.stdout.write(']') cache = LRUCache(10) for i in xrange(len(cmds)): cmd = cmds[i] param = params[i] sys.stdout.write(str(i) + " " + cmd + " ") print_list(param) sys.stdout.write("\n") val = getattr(cache, cmd)(*param) print("result " + str(val))Copy the code