• 周五. 12月 9th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

Design data structure to implement a lrucache

[db:作者]

1月 6, 2022

Title Description

This is a LeetCode Upper 「146. LRU Caching mechanisms 」 , The difficulty is 「 secondary 」.

Use the data structure you have , Design and implement a LRU ( Recently at least use ) Caching mechanisms . Realization LRUCache class :

  • LRUCache(int capacity) Take positive integers as capacity capacity initialization LRU cache
  • int get(int key) If the keyword key In the cache , The value of the keyword is returned , Otherwise return to -1 .
  • void put(int key, int value) If the keyword already exists , Change its data value ; If the keyword does not exist , Insert the group 「 keyword – value 」. When the cache capacity reaches the upper limit , It should delete the oldest unused data values before writing new data , This leaves room for new data values .

Advanced : Can you be in

O(1)

Complete these two operations in time complexity ?

Example :

 Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]
explain
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // The cache is {1=1}
lRUCache.put(2, 2); // The cache is {1=1, 2=2}
lRUCache.get(1); // return 1
lRUCache.put(3, 3); // This operation causes the keyword to 2 To void , The cache is {1=1, 3=3}
lRUCache.get(2); // return -1 ( Not found )
lRUCache.put(4, 4); // This operation causes the keyword to 1 To void , The cache is {4=4, 3=3}
lRUCache.get(1); // return -1 ( Not found )
lRUCache.get(3); // return 3
lRUCache.get(4); // return 4

Tips :

  • 1 <= capacity <= 3000
  • 0 <= key <= 3000
  • 0 <= value <=
10^4
  • Call at most 3 *
10^4

Time get and put

Basic analysis

LRU Is a very common page replacement algorithm .

take LRU Translated into plain English : When you have to eliminate some data ( Usually the capacity is full ), Select the longest unused data for elimination .

Let’s achieve a fixed capacity LRUCache . If you insert data , When the container is found full , Then first follow LRU Rules eliminate a data , Insert the new data into , among 「 Insert 」 and 「 Inquire about 」 All count as one time “ Use ”.

Can pass ? To understand the , Suppose we have a capacity of

2

Of LRUCache and Test key value pairs [1-1,2-2,3-3] , Insert them in order & Inquire about :

  • Insert 1-1, At this point, the latest usage data is 1-1
  • Insert 2-2, At this point, the latest usage data becomes 2-2
  • Inquire about 1-1, At this time, the latest usage data is 1-1
  • Insert 3-3, Because the container has reached capacity , You need to eliminate existing data before you can insert it , At this time, it will be eliminated 2-2,3-3 Become the latest usage data

Key value vs. storage , We can use 「 Hashtable 」 To ensure that the insertion and query complexity is

O(1)

.

In addition, we need to maintain an extra 「 Order of use 」 Sequence .

We expect to be 「 New data is inserted 」 or 「 A key value pair query occurs 」 when , Can put the current key value pair to the sequence head , So when you trigger LRU When it’s eliminated , Just delete the data from the end of the sequence .

Expect in

O(1)

Adjust the position of a node in the sequence within the complexity , It’s natural to think of two-way linked lists .

Double linked list

Concrete , We use hash tables to store 「 Key value pair 」, The key of the key value pair is the key of the hash table Key, And hash table Value We use our own package Node class ,Node At the same time, as the node of the two-way linked list .

  • Insert : Check whether the current key value pair already exists in the hash table :
    • Not up to capacity : Insert hash table , And set the current key value to the corresponding Node The node is adjusted to the head of the list (refresh operation )
    • Capacity reached : First, find the element to be deleted from the end of the linked list to delete (delete operation ), Then insert the hash table , And set the current key value to the corresponding Node The node is adjusted to the head of the list (refresh operation )
    • If there is , Then update the key value pair , And set the current key value to the corresponding Node The node is adjusted to the head of the list (refresh operation )
    • If it doesn’t exist , Then check whether the hash table has reached its capacity :
  • Inquire about : If it is not found in the hash table Key, Go straight back to
-1

; If the Key, Then return the corresponding value to , And set the current key value to the corresponding Node The node is adjusted to the head of the list (refresh operation )

Some details :

  • In order to reduce the number of left and right nodes in the bidirectional list 「 Sentenced to empty 」 operation , We set up two in advance 「 sentry 」 node head and tail.

Code :

class LRUCache {
class Node {
int k, v;
Node l, r;
Node(int _k, int _v) {
k = _k;
v = _v;
}
}
int n;
Node head, tail;
Map<Integer, Node> map;
public LRUCache(int capacity) {
n = capacity;
map = new HashMap<>();
head = new Node(-1, -1);
tail = new Node(-1, -1);
head.r = tail;
tail.l = head;
}
public int get(int key) {
if (map.containsKey(key)) {
Node node = map.get(key);
refresh(node);
return node.v;
}
return -1;
}
public void put(int key, int value) {
Node node = null;
if (map.containsKey(key)) {
node = map.get(key);
node.v = value;
} else {
if (map.size() == n) {
Node del = tail.l;
map.remove(del.k);
delete(del);
}
node = new Node(key, value);
map.put(key, node);
}
refresh(node);
}
// refresh There are two steps :
// 1. First, delete the current node from the bidirectional list ( If the node itself exists in the bidirectional list )
// 2. Add the current node to the head of the bidirectional linked list
void refresh(Node node) {
delete(node);
node.r = head.r;
node.l = head;
head.r.l = node;
head.r = node;
}
// delete operation : Remove the current node from the bidirectional list
// Because we built it up in advance head and tail Two Sentinels , So if node.l Not empty , It stands for node It exists in two-way linked list ( It's not a new node )
void delete(Node node) {
if (node.l != null) {
Node left = node.l;
left.r = node.r;
node.r.l = left;
}
}
}
  • Time complexity : All operations are
O(1)
  • Spatial complexity :
O(n)

Last

This is us. 「 Brush through LeetCode」 The first of the series No.146 piece , The series begins with 2021/01/01, As of the start date LeetCode I have in common 1916 questions , Part of it is a locked question , We will finish all the questions without lock first .

In this series , In addition to explaining the idea of solving problems , And give the most concise code possible . If the general solution is involved, there will be corresponding code templates .

In order to facilitate the students to debug and submit code on the computer , I’ve built a warehouse :https://github.com/SharingSource/LogicStack-LeetCode .

In the warehouse address , You can see the links to the series 、 The corresponding code of the series 、LeetCode Links to the original problem and other preferred solutions .

This article is from WeChat official account. –
The diary of Miyoshi Sanye (LogicTech)
, author : Gongshui Sanye

The source and reprint of the original text are detailed in the text , If there is any infringement , Please contact the
[email protected]
Delete .

Original publication time :
2021-05-31

Participation of this paper Tencent cloud media sharing plan , You are welcome to join us , share .

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注