• 周四. 12月 1st, 2022

5G编程聚合网

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

热门标签

Design data structure to implement a lfucache

[db:作者]

1月 6, 2022

Title Description

This is a LeetCode Upper 「460. LFU cache 」 , The difficulty is 「 difficult 」.

Tag : 「 Linked list 」、「 Double linked list 」、「 Design 」

Please help me 「 The least used (LFU)」 Cache algorithm design and implementation of data structure .

Realization LFUCache class :

  • LFUCache(int capacity) – With the capacity of the data structure capacity Initialize object
  • int get(int key) – If the key exists in the cache , Then get the value of the key , Otherwise return to -1.
  • void put(int key, int value) – If the key already exists , Then change its value ; If the key doesn’t exist , Please insert key value pair . When the cache reaches its capacity , Before inserting a new item , Invalidate the least frequently used items . In this question , When there is a draw ( That is, two or more keys have the same frequency of use ) when , It should be removed 「 Most recently unused 」 Key .

Be careful 「 Number of times the item was used 」 Is to call… On the item since it was inserted get and put The sum of the degrees of a function . The number of uses will be set to… After the corresponding item is removed 0 .

To determine the least frequently used keys , You can maintain one for each key in the cache Use counter . The key with the lowest count is the key that has not been used for the longest time .

When a key is first inserted into the cache , Its usage counter is set to 1 ( because put operation ). Execute… On the key in the cache get or put operation , Using the counter will increment the value .

Example :

 Input :
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
Output :
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]
explain :
// cnt(x) = key x Use count of
// cache=[] The order of last use will be displayed ( The leftmost element is the closest )
LFUCache lFUCache = new LFUCache(2);
lFUCache.put(1, 1); // cache=[1,_], cnt(1)=1
lFUCache.put(2, 2); // cache=[2,1], cnt(2)=1, cnt(1)=1
lFUCache.get(1); // return 1
// cache=[1,2], cnt(2)=1, cnt(1)=2
lFUCache.put(3, 3); // Remove the key 2 , because cnt(2)=1 , Use the minimum count
// cache=[3,1], cnt(3)=1, cnt(1)=2
lFUCache.get(2); // return -1( Not found )
lFUCache.get(3); // return 3
// cache=[3,1], cnt(3)=2, cnt(1)=2
lFUCache.put(4, 4); // Remove the key 1 ,1 and 3 Of cnt identical , but 1 Not used for a long time
// cache=[4,3], cnt(4)=1, cnt(3)=2
lFUCache.get(1); // return -1( Not found )
lFUCache.get(3); // return 3
// cache=[3,4], cnt(4)=1, cnt(3)=3
lFUCache.get(4); // return 4
// cache=[3,4], cnt(4)=2, cnt(3)=3

Tips :

  • 0 <= capacity, key, value <=
10^4
  • Call at most
10^5

Time get and put Method

Advanced : You can design the time complexity for these two operations to be

O(1)

The realization of ?

Basic analysis

We just talked about 146. LRU Caching mechanisms , Simple understanding LRU Namely 「 Remove the most unused elements 」.

So for LRU We just need to use 「 Hashtable 」 At the same time , Maintain a 「 Double linked list 」 that will do :

  • Every time get or put The element is stored in the head of the bidirectional linked list when the element is loaded
  • When you need to remove elements , Remove from the tail of the bidirectional list

LFU Simple understanding means 「 Remove the least used element 」, If there are multiple least used elements , The remove 「 The one that hasn’t been used recently 」(LRU The rules ). alike get and put All count as one use .

therefore , We need to record how many times each element is used , And in

O(1)

Within the complexity of 「 Modify the number of times an element is used 」 and 「 Find the least used element 」.

Bucket sort + Double linked list

「 We can use 「 Bucket sort 」 The idea of , collocation 「 Double linked list 」 Realization

O(1)

operation .」

「 stay LFUCache in , We maintain a system of Bucket As a bidirectional list of nodes , Every Bucket There is one. idx Number , Representing the current bucket is 「 How many times 」 The key/value pair 」idx = 1 The key value pair used once for bucket storage ;idx = 2 The bucket is used twice to store key value pairs … ).

meanwhile LFUCache Hold one 「 Hashtable 」, To record what key In which bucket .

「 stay Bucket Internally, it maintains a path to Item As a bidirectional list of nodes ,Item It is used to store real key value pairs .」

alike ,Bucket Also holding a 「 Hashtable 」, Used to record key And Item The mapping relation of .

therefore LFUCache It’s actually a 「 Linked list sets linked list 」 Data structure of :

Corresponding to LFUCache Several operations of :

  • get : Through the first LFUCache Hold the hash table to look up , Returns if none exists
-1

, If there is, find the bucket where the key value pair is cur

  • Call corresponding cur Of remove operation , Get the key value pair corresponding to item( Remove represents the current key value plus one number of uses , It’s not going to be in the same bucket ).
  • take item Put it in idx by
cur.idx + 1

The barrel target in ( Represents the number of times the current key value is used plus one , It should be in a new target bucket ).

  • If the target bucket target non-existent , Create ; If the original barrel cur Empty after removing key value pairs , Then destroy .
  • to update LFUCache The information in the hash table .
  • put : Through the first LFUCache Hold the hash table to look up :
    • If the capacity reaches the quantity, it needs to call 「 The smallest barrel 」 Of clear operation , stay clear Inside the operation , From item The tail of the two-way list begins to remove elements . Insert when you’re done .
    • If there is : Find the bucket where the key value pair is located cur, call cur Of put operation , Update key value pairs , And then call LFUCache Of get Operation to achieve the number of use plus one .
    • If it doesn’t exist : First check whether the capacity reaches the quantity :
    • The insert : Add key value pairs to
    idx = 1

    The barrels ( Represents the number of times the current key value pair is used

    1

    ), If the bucket does not exist, create .

Code :

class LFUCache {
class Item {
Item l, r;
int k, v;
public Item(int _k, int _v) {
k = _k;
v = _v;
}
}
class Bucket {
Bucket l, r;
int idx;
Item head, tail;
Map<Integer, Item> map = new HashMap<>();
public Bucket(int _idx) {
idx = _idx;
head = new Item(-1, -1);
tail = new Item(-1, -1);
head.r = tail;
tail.l = head;
}
void put(int key, int value) {
Item item = null;
if (map.containsKey(key)) {
item = map.get(key);
// Update value
item.v = value;
// Remove from the original double linked list position
item.l.r = item.r;
item.r.l = item.l;
} else {
item = new Item(key, value);
// Add to hash table
map.put(key, item);
}
// Add to the head of the double linked list
item.r = head.r;
item.l = head;
head.r.l = item;
head.r = item;
}
Item remove(int key) {
if (map.containsKey(key)) {
Item item = map.get(key);
// Remove from a two-way list
item.l.r = item.r;
item.r.l = item.l;
// Removed from the hash table
map.remove(key);
return item;
}
return null; // never
}
Item clear() {
// Find the node to be deleted from the tail of the bidirectional list
Item item = tail.l;
item.l.r = item.r;
item.r.l = item.l;
// Removed from the hash table
map.remove(item.k);
return item;
}
boolean isEmpty() {
return map.size() == 0;
}
}
Map<Integer, Bucket> map = new HashMap<>();
Bucket head, tail;
int n;
int cnt;
public LFUCache(int capacity) {
n = capacity;
cnt = 0;
head = new Bucket(-1);
tail = new Bucket(-1);
head.r = tail;
tail.l = head;
}
public int get(int key) {
if (map.containsKey(key)) {
Bucket cur = map.get(key);
Bucket target = null;
if (cur.r.idx != cur.idx + 1) {
// The target is
target = new Bucket(cur.idx + 1);
target.r = cur.r;
target.l = cur;
cur.r.l = target;
cur.r = target;
} else {
target = cur.r;
}
// Remove the current key value pair from the current bucket , And add new buckets
Item remove = cur.remove(key);
target.put(remove.k, remove.v);
// Update the bucket information of the current key value pair
map.put(key, target);
// If after removing the current key value pair , The current bucket is empty , Delete the current bucket ( Make sure the space is O(n) Of )
// Also make sure to call the lowest numbered bucket clear Method , Can effectively remove an element
deleteIfEmpty(cur);
return remove.v;
}
return -1;
}
public void put(int key, int value) {
if (n == 0) return;
if (map.containsKey(key)) {
// Element already exists , Change the value
Bucket cur = map.get(key);
cur.put(key, value);
// Call get Realization 「 Times of use 」+ 1
get(key);
} else {
// The container is full , You need to delete the element first
if (cnt == n) {
// From the first bucket ( Minimum number 、 The least number of uses ) Clear in
Bucket cur = head.r;
Item clear = cur.clear();
map.remove(clear.k);
cnt--;
// If after removing the key value pair , The current bucket is empty , Delete the current bucket ( Make sure the space is O(n) Of )
// Also make sure to call the lowest numbered bucket clear Method , Can effectively remove an element
deleteIfEmpty(cur);
}
// You need to add the current key value pair to 1 Bucket number
Bucket first = null;
// If 1 If no barrel exists, create
if (head.r.idx != 1) {
first = new Bucket(1);
first.r = head.r;
first.l = head;
head.r.l = first;
head.r = first;
} else {
first = head.r;
}
// Add key value pairs to 1 Bucket number
first.put(key, value);
// Update the bucket information of the key value pair
map.put(key, first);
// Add one counter
cnt++;
}
}
void deleteIfEmpty(Bucket cur) {
if (cur.isEmpty()) {
cur.l.r = cur.r;
cur.r.l = cur.l;
cur = null; // help GC
}
}
}
  • Time complexity : All operations are
O(1)
  • Time complexity :
O(n)

Last

This is us. 「 Brush through LeetCode」 The first of the series No.460 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-06-03

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

发表回复

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