LeetCode 146. LRU cache mechanism | Python

Posted May 25, 20204 min read

146 . LRU cache mechanism


Source of the question:LeetCode https://leetcode-cn.com/problems/lru-cache

Title


Design and implement an LRU(least recently used) caching mechanism using the data structure you have. It should support the following operations:get data get and write data put.

Get data get(key)-If the key(key) exists in the cache, get the value of the key(always a positive number), otherwise return -1.
Write data put(key, value)-If the key already exists, change its data value; if the key does not exist, insert the group "key/data value". When the cache capacity reaches the upper limit, it should delete the longest unused data value before writing new data to make room for the new data value.

Advanced:

Can you accomplish both operations within O(1) time complexity?

Example:

LRUCache cache = new LRUCache(2/* cache capacity * /);

cache.put(1, 1);
cache.put(2, 2);
cache.get(1); //returns 1
cache.put(3, 3); //This operation will make key 2 invalid
cache.get(2); //returns -1(not found)
cache.put(4, 4); //This operation will make key 1 invalid
cache.get(1); //returns -1(not found)
cache.get(3); //returns 3
cache.get(4); //returns 4

Problem solving ideas


Thinking:hash table, doubly linked list

First, explain LRU, LRU(Least Recently Used), which has been used least recently. It is a cache elimination strategy.

For example, normally the cache capacity is limited. If you want to make room when deleting some content, what content should you consider deleting at this time? What content is useless and can be deleted? Which ones should be kept and useful?

This strategy of LRU considers the recently used data to be useful, and those that have not been used for a long time are useless. When the cache is insufficient, these unused for a long time will be deleted first.

This is a simple description of the LRU strategy, of course, there are other strategies, such as LFU.

Look at this question again, because the question has a requirement, [can it be done within the O(1) time complexity to get data get and write data put operations?

It should be considered here that to achieve the above operations within the time complexity O(1), the data structure conditions we want to use should have the following characteristics:search, insert, and delete should be fast.

We know the hash table, the search speed is fast, but there is no order. In the linked list, insertion and deletion are fast and orderly, but search is slow. At this time, we consider combining the two.

Here, because when the cache capacity reaches the upper limit, we need to perform a delete operation. To delete a node, not only the pointer of the current node but also the pointer of the predecessor node, here we need to use a doubly linked list to delete and When searching for the predecessor, the O(1) time complexity is achieved.

So now, if you use hash table + doubly linked list to achieve functional design:

  • First, the doubly linked list part, store key-value pairs in the order of use. Near the head is the most recent use, and near the tail is the non-recently used.
  • Hash table, the key maps its position in the doubly linked list.

Specific implementation method:

  • get:first determine whether key exists:

    • There is no return -1
    • When it exists, the corresponding node at this time is set as the most recently used. Then first locate it in the doubly linked list, move it to the head, and return the value of the node.
  • put:also determine whether key exists:

    • If it does not exist, create a new node, add the node at the head of the doubly linked list, and also add it to the hash table. At the same time, it is also necessary to determine whether the capacity of the doubly linked list is exceeded. If it is exceeded, delete the end node and delete the corresponding part of the hash table.
    • When it exists, locate the position of the doubly linked list through the hash table, update its value, and move to the head of the doubly linked list at the same time.

The specific implementation code is as follows.

Code


class Node(object):
    def __init __(self, key = 0, value = 0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class DoubleLinkedList(object):
    def __init __(self):
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    def add_to_head(self, node):
        "" "Add a node to the head
        "" "
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node
        self.size + = 1

    def remove_node(self, node):
        "" "Delete Node
        "" "
        node.prev.next = node.next
        node.next.prev = node.prev
        self.size-= 1

    def remove_tail(self):
        "" "Delete the tail node
        "" "
        if self.size == 0:
            return None
        node = self.tail.prev
        self.remove_node(node)
        return node

    def get_size(self):
        return self.size

class LRUCache:

    def __init __(self, capacity:int):
        self.capacity = capacity
        self.hashmap = {}
        self.cache = DoubleLinkedList()

    def get(self, key:int)-> int:
        # Judge whether the key exists, deal with each case
        if key not in self.hashmap:
            return -1
        # Locate its position on the doubly linked list by hash
        value = self.hashmap [key].value
        # The logic implemented here is reflected in the put operation
        # put operation also needs to move to the head of the linked list when the key exists
        self.put(key, value)
        return value

    def put(self, key:int, value:int)-> None:
        # Create node first
        node = Node(key, value)
        # Also determine whether the key exists
        # Case by case
        if key in self.hashmap:
            self.cache.remove_node(self.hashmap [key])
            self.cache.add_to_head(node)
            self.hashmap [key]= node
        else:
            # Determine whether the cache capacity is not enough
            if self.capacity == self.cache.get_size():
                # Delete the last node
                tail = self.cache.remove_tail()
                self.hashmap.pop(tail.key)
            # Add to head
            self.cache.add_to_head(node)
            self.hashmap [key]= node



# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key, value)

Results


Achievement Results

to sum up


  • Use hash table + doubly linked list to realize the operation with time complexity of O(1);
  • The doubly linked list stores key-value pairs in the order of use, most recently used in the head, and not recently used in the tail;
  • Hash table, where the key map is stored in the doubly linked list.

Welcome to the WeChat public account "Book Collection"