Cabbage Java self study room covers core knowledge

LRU cache mechanism LeetCode algorithm series (Java version) 460. LFU cache mechanism

Force buckles the original problem

460. LFU caching mechanism

You design and implement data structures for least-used (LFU) caching algorithms.

Implement the LFUCache class:

  • LFUCache(int capacity)– Use the capacity of the data structurecapacityInitialize an object
  • int get(int key)– Gets the value of the key if it exists in the cache, otherwise -1 is returned.
  • void put(int key, int value)– If the key already exists, change its value; If the key does not exist, insert a key-value pair. When the cache reaches its capacity, the least frequently used items should be invalidated before new items are inserted. In this problem, when there is a tie (that is, two or more keys with the same frequency of use), it should be removedLongest unusedThe key.

Note that the number of times the item was used is the sum of the number of get and PUT calls to the item since it was inserted. The number of times will be set to 0 after the corresponding item is removed.

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] explanation:  LFUCache lFUCache = new LFUCache(2); lFUCache.put(1, 1); lFUCache.put(2, 2); lFUCache.get(1); // return 1 lFUCache. Put (3, 3); // remove key 2 lFUCache. Get (2); // return -1 (not found) lFUCache. Get (3); // return 3 lFUCache. Put (4, 4); // remove key 1 lFUCache. Get (1); // return -1 (not found) lFUCache. Get (3); // return 3 lFUCache. Get (4); / / return 4Copy the code

LFU (Least Frequently Used) Cache mechanism

  • When the cache is full, the least used element in the cache is removed and a new element is added to the cache.
  • The number of times data is accessed is very important. The more times data is accessed, the less likely it is to be deleted.
  • When two or more keys have the same frequency of use, the least recently used key will be removed.

Note: In addition to the LRU cache mechanism, one more dimension (” access times “) is considered in the deletion strategy.

Key idea: Consider the number of accesses first, and then consider the cache time if the number of accesses is the same.

Their thinking

The cache is limited, and there are different cache deletion strategies for which elements are deleted when the cache is full.

  • Since the time complexity of the topic requires O(1)O(1)O(1) O(1), space must not be saved. The best time performance of accessing data is the hash table, so the underlying data structure must be a hash table;
  • In addition, the cache size is limited, and the deletion policy is “See the access frequency first, then the access time”. Therefore, the frequency of each data access needs to be recorded.
  • “Delete a data” is O(1)O(1)O(1) O(1)O(1)O(1) O(1)O(1)O(1) O(1)O(1)O(1) O(1) is O(1)O(1)O(1) O(1) is O(1)O(1)O(1) O(1) is O(1)O(1)O(1) O(1) is O(1)O(1)O(1) O(1).
  • The “linked list” node records: (1) value, (2) key (used when deleting from the hash table), (3) number of accesses to know the next number of accesses; 4. Reference of precursor node; 5. Reference of successor node;
  • The key stored in the hash table is the key of the question, which is convenient for quick query and deletion. The value is the reference of the node, which is convenient for operation on the node.

Here is a schematic of the memory structure:

  • Each time an existing element is accessed, the node class should be removed from the current access-count list before being added to the head of its “next access-count” list.

Code implementation

import java.util.HashMap; import java.util.Map; Public class LFUCache {private Map<Integer, ListNode> Map; public class LFUCache {private Map<Integer, ListNode> Map; Private Map<Integer, DoubleLinkedList> frequentMap; private Map<Integer, DoubleLinkedList> frequentMap; /** * External incoming capacity */ private Integer capacity; /** * Specifies the highest number of global accesses. */ private Integer minFrequent = 1; Public LFUCache(int capacity) {LFUCache(int capacity) {LFUCache(int capacity) {LFUCache(int capacity); Map = new HashMap<>(capacity, 1); frequentMap = new HashMap<>(); this.capacity = capacity; } /** * get; * * @param key * @return */ public int get(int key) { If (capacity == 0) {return -1; } if (map.containsKey) {ListNode ListNode = removeListNode(key); Int frequent = listnode. frequent; addListNode2Head(frequent, listNode); return listNode.value; } else { return -1; } } /** * @param key * @param value */ public void put(int key, int value) { if (capacity == 0) { return; } // If (map.containsKey) {ListNode ListNode = removeListNode(key); // Update value listNode.value = value; int frequent = listNode.frequent; addListNode2Head(frequent, listNode); return; } // if the key is not present // 1, if the key is full, delete the last node with the least number of accesses. If (map.size() == capacity) {// delete DoubleLinkedList DoubleLinkedList = frequentMap.get(minFrequent); ListNode removeNode = doubleLinkedList.removeTail(); Remove map.remove(removenode.key) from map. } newListNode = newListNode (key, value); addListNode2Head(1, newListNode); map.put(key, newListNode); This. MinFrequent = 1; // since this node is newly created, the minimum number of visits must be 1. Private class ListNode {private int key; private class ListNode {private int key; private int value; private int frequent = 1; private ListNode pre; private ListNode next; public ListNode() { } public ListNode(int key, int value) { this.key = key; this.value = value; } /** * private class DoubleLinkedList {/** * private ListNode dummyHead; /** * private ListNode dummyTail; /** * private int count; Public DoubleLinkedList() {this.dummyHead = new ListNode(-1, -1); this.dummyTail = new ListNode(-2, -2); dummyHead.next = dummyTail; dummyTail.pre = dummyHead; count = 0; } public void addNode2Head(ListNode addNode) {ListNode oldHead;} public void addNode2Head(ListNode addNode) = dummyHead.next; DummyHead. Next = addNode; oldHead.pre = addNode; Addnode. pre = dummyHead; addNode.pre = dummyHead; addNode.next = oldHead; count++; } /** * delete the end node of the bidirectional list (tail is the oldest data, * * @return */ public ListNode removeTail() {ListNode oldTail = dummytail.pre; ListNode newTail = oldTail.pre; Newtail. next = dummyTail; dummyTail.pre = newTail; // Its two properties break the connection oldtail. pre = null; oldTail.next = null; // Important: delete a node, the number of nodes in the current bidirectional list is 1 less count--; // Maintain return oldTail; }} /** * * * @param key * @return */ private ListNode removeListNode(int key) {ListNode deleteNode = map.get(key); ListNode preNode = deleteNode.pre; ListNode nextNode = deleteNode.next; Prenode. next = nextNode; nextNode.pre = preNode; Deletenode. pre = null; deleteNode.next = null; Frequentmap. get(deletenode.frequent).count--; // If the current node happens to be on the list with the minimum number of visits, and the number of nodes after removal is 0, If (deletenode. frequent == minFrequent && frequentmap. get(deletenode.frequent).count == 0) { MinFrequent++ is correct after testing; } // deletenode.frequent+ +; return deleteNode; } /** * put the nodes in the head of the frequent list ** @param * @param addNode */ private void addListNode2Head(int frequent, ListNode addNode) { DoubleLinkedList doubleLinkedList; // If there is no frequentmap. containsKey(frequent) {doubleLinkedList = frequentmap. get(frequent); } else { doubleLinkedList = new DoubleLinkedList(); } / / added to DoubleLinkedList header DoubleLinkedList addNode2Head (invoke the); frequentMap.put(frequent, doubleLinkedList); } public static void main(String[] args) { LFUCache cache = new LFUCache(2); cache.put(1, 1); cache.put(2, 2); System.out.println(cache.map.keySet()); int res1 = cache.get(1); System.out.println(res1); cache.put(3, 3); System.out.println(cache.map.keySet()); int res2 = cache.get(2); System.out.println(res2); int res3 = cache.get(3); System.out.println(res3); cache.put(4, 4); System.out.println(cache.map.keySet()); int res4 = cache.get(1); System.out.println(res4); int res5 = cache.get(3); System.out.println(res5); int res6 = cache.get(4); System.out.println(res6); }}Copy the code

Output result:

[2, 1]
1
[1, 3]
-1
3
[4, 3]
-1
3
4
Copy the code
  • When you insert a new node, because this node has never been accessed beforeminFrequent = 1, equivalent to return to the position;
  • whenput 和 getMove a node from the current list to another list node. If the list that is removed happens to be the least accessed list, and the number of nodes in the list after removal is0.minFrequentNeed to add1 。

Complexity analysis

  • Time complexity: Get time complexity O(1)O(1)O(1), PUT time complexity O(1)O(1)O(1). The time complexity of the two operations is O(1)O(1)O(1) O(1)O(1)O(1) O(1)O(1).

  • Space complexity: O(capacity)O(\textit{capacity})O(capacity), where capacity\textit{capacity}capacity is the cache capacity of the LFU. The hash table does not hold more key-value pairs than the cache capacity.

LRU cache mechanism LeetCode algorithm series (Java version) 460. LFU cache mechanism