Shulou(Shulou.com)06/02 Report--

This article focuses on "what are the ways to achieve LFU", interested friends may wish to have a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn "what are the ways to implement LFU?"

LFU implementation

The original title is described as follows:

Please design and implement data structures for the least frequently used (LFU) caching algorithm. It should support the following operations: get and put. Get (key)-gets the value of the key (always a positive number) if the key exists in the cache, otherwise returns-1. Put (key, value)-if the key does not exist, set or insert the value. When the cache reaches its capacity, you should invalidate the least frequently used items before inserting new items. In this problem, when there is a draw (that is, two or more keys have the same frequency of use), the least recently used keys should be removed. The number of uses of an item is the sum of the number of times the get and put functions have been called on the item since it was inserted. The number of uses will be set to 0 after the corresponding item is removed. Example: LFUCache cache = new LFUCache (2 / * capacity (cache capacity) * /); cache.put (1,1); cache.put (2,2); cache.get (1); / / return 1 cache.put (3,3); / / remove key 2 cache.get (2); / / return-1 (key 2 not found) cache.get (3); / / return 3 cache.put (4,4) / / remove key 1 cache.get (1); / / return-1 (key 1 not found) cache.get (3); / / return 3 cache.get (4); / / return 4 sources: LeetCode link: https://leetcode-cn.com/problems/lfu-cache

It requires us to design a LFU algorithm to determine which element should be deleted according to the number of visits (access frequency). Both get and put operations will increase the access frequency. When the access frequency is equal, determine which element is the longest unused, and delete it.

Therefore, this question needs to consider two aspects, one is the visit frequency, the other is the order of visit time.

Option 1: use the priority queue idea:

We can do this using the priority queue PriorityQueue provided by JDK. Because a binary heap is maintained inside the priority queue, we can ensure that every time we poll elements, we can fetch the maximum or minimum values of all current elements according to our requirements. We just need our entity class to implement the Comparable interface.

Therefore, we need to define a Node to hold the current element's access frequency freq, a global self-increasing index for comparing sizes. Then define a Map

When the cache capacity is insufficient, the smallest freq is deleted according to the size of the access frequency freq. If equal, delete the smallest index, because the index is self-increasing. The larger the index, the more recently visited, and the smaller the element that has not been accessed for a long time.

Because it is essentially implemented with a binary heap, the time complexity is O (logn).

Public class LFUCache4 {public static void main (String [] args) {LFUCache4 cache = new LFUCache4 (2); cache.put (1,1); cache.put (2,2); / / returns 1 System.out.println (cache.get (1)); cache.put (3,3) / / remove key 2 / / return-1 (key 2 not found) System.out.println (cache.get (2)); / / return 3 System.out.println (cache.get (3)); cache.put (4,4) / / remove key 1 / / return-1 (key 1 not found) System.out.println (cache.get (1)); / / return 3 System.out.println (cache.get (3)); / / return 4 System.out.println (cache.get (4));} / / node Map cache with all elements cached / / priority queue Queue queue; / / capacity of cache cache int capacity; / / number of elements currently cached int size; / / global self-increment int index = 0; / / initialize public LFUCache4 (int capacity) {this.capacity = capacity; if (capacity > 0) {queue = new PriorityQueue (capacity) } cache = new HashMap ();} public int get (int key) {Node node = cache.get (key); / / if node does not exist, return-1 if (node = = null) return-1; / / for each visit, the frequency and global index are incremented by 1 node.freq++; node.index = index++ / / re-remove every time, and then offer is to enable the priority queue to reorder the current Node / / otherwise, the compared freq and index are inaccurate queue.remove (node); queue.offer (node); return node.value } public void put (int key, int value) {/ / capacity 0, then directly return if (capacity = = 0) return; Node node = cache.get (key); / / if node exists, update its value if (node! = null) {node.value = value; node.freq++; node.index = index++ Queue.remove (node); queue.offer (node);} else {/ / if cache is full, take an element from the priority queue. This element must be the least frequent and longest unvisited element if (size = = capacity) {cache.remove (queue.poll (). Key) / / after the element is taken out, size minus 1 size--;} / / otherwise, you can add the element, so create a new node and add it to the priority queue Node newNode = newNode (key, value, index++); queue.offer (newNode); cache.put (key,newNode) / / meanwhile, size plus 1 size++;}} / / the Comparable interface must be implemented before it can be used to sort private class Node implements Comparable {int key; int value; int freq = 1; int index Public Node () {} public Node (int key, int value, int index) {this.key = key; this.value = value; this.index = index } @ Override public int compareTo (Node o) {/ / compare frequency freq first, and then compare index int minus = this.freq-o.freq; return minus = = 0? This.index-o.index: minus;}

Option 2: use a two-way linked list

Train of thought:

Only a two-way linked list is used to maintain the frequency and chronological order. Well, think of it this way. Put the small freq in the front and the high frequency in the back. If the frequency is equal, traverse back from the current node until the first element with a greater frequency is found and inserted in front of it. (of course, if you traverse to tail, insert it in front of tail.) this ensures that elements with the same frequency are always last visited.

So, in general, the element with the lowest frequency and the longest unaccessed must be the first element in the linked list. In this way, when the cache capacity is full, just delete the header node. However, in order to facilitate the insertion and deletion of linked lists, we use two sentinel nodes to represent the header node head and the tail node tail. Therefore, deleting the header node is equivalent to deleting the head.next.

PS: the Sentinel node is only used to occupy space. It does not actually store valid data, just so that when the linked list is inserted and deleted, it is no longer necessary to determine the location of the current node. Otherwise, if the current node occupies the position of the head node or tail node, it is more troublesome to re-assign the head and tail node elements.

To make it easier to understand how the new node is inserted in the right place in the linked list, the figure is as follows:

The code is as follows:

Public class LFUCache {public static void main (String [] args) {LFUCache cache = new LFUCache (2); cache.put (1,1); cache.put (2,2); / / returns 1 System.out.println (cache.get (1)); cache.put (3,3) / / remove key 2 / / return-1 (key 2 not found) System.out.println (cache.get (2)); / / return 3 System.out.println (cache.get (3)); cache.put (4,4) / / remove key 1 / / return-1 (key 1 not found) System.out.println (cache.get (1)); / / return 3 System.out.println (cache.get (3)); / / return 4 System.out.println (cache.get (4));} private Map cache; private Node head; private Node tail Private int capacity; private int size; public LFUCache (int capacity) {this.capacity = capacity; this.cache = new HashMap (); / * initialize the header and tail nodes as Sentinel nodes * / head = new Node (); tail = new Node (); head.next = tail; tail.pre = head } public int get (int key) {Node node = cache.get (key); if (node = = null) return-1; node.freq++; moveToPostion (node); return node.value;} public void put (int key, int value) {if (capacity = = 0) return; Node node = cache.get (key) If (node! = null) {node.value = value; node.freq++; moveToPostion (node) } else {/ / if the element is full of if (size = = capacity) {/ / remove the first element directly, because this node is the node that has the least frequency and has not been accessed for the longest time, cache.remove (head.next.key); removeNode (head.next); size-- } Node newNode = newNode (key, value); / / add new elements to addNode (newNode); cache.put (key,newNode); size++ }} / / as long as the frequency of the current node is greater than or equal to the node behind it, keep looking backward, / / until you find the first node with a higher frequency than the current node, or tail node, and then insert it in front of private void moveToPostion (Node node) {Node nextNode = node.next; / / first delete the current element removeNode (node) / / traverse to the node while (node.freq > = nextNode.freq & & nextNode! = tail) {nextNode = nextNode.next;} / / insert the current element in front of the nextNode node.pre = nextNode.pre; node.next = nextNode; nextNode.pre.next = node; nextNode.pre = node } / / add the element (head insertion) and move to the appropriate location private void addNode (Node node) {node.pre = head; node.next = head.next; head.next.pre = node; head.next = node; moveToPostion (node);} / / remove the element private void removeNode (Node node) {node.pre.next = node.next Node.next.pre = node.pre;} class Node {int key; int value; int freq = 1; / the previous node of the current node Node pre; / / the latter node Node next of the current node Public Node () {} public Node (int key, int value) {this.key = key; this.value = value;}

You can see that no additional judgment is required when inserting or deleting elements, which is the advantage of setting up a Sentinel node.

Because every time you visit an element, you need to place the element in the right place according to certain rules, so the element needs to be traversed all the way. Therefore, the time complexity is O (n).

Plan 3: maintain the frequency linked list with LinkedHashSet

Train of thought:

We no longer use a linked list and maintain both frequency and access time. Here, instead of using the map key-value pair to maintain, use the frequency as the key, and use a linked list with the order of access to the current frequency as the value. Its structure is as follows:

Map freqMap

Because LinkedHashSet's iterator iteration method is in insertion order, the first element to be iterated must be the one that has not been accessed for the longest time at the current frequency. In this way, when the cache cache is full, you can simply delete the first element of the iteration.

In addition, freqMap also needs to re-maintain the relationship each time the element is accessed. Removes the current element from the bidirectional linked list corresponding to the frequency of the current element and adds it to the high-frequency linked list.

Public class LFUCache1 {public static void main (String [] args) {LFUCache1 cache = new LFUCache1 (2); cache.put (1,1); cache.put (2,2); / / returns 1 System.out.println (cache.get (1)); cache.put (3,3) / / remove key 2 / / return-1 (key 2 not found) System.out.println (cache.get (2)); / / return 3 System.out.println (cache.get (3)); cache.put (4,4) / / remove key 1 / / return-1 (key 1 not found) System.out.println (cache.get (1)); / / return 3 System.out.println (cache.get (3)); / / return 4 System.out.println (cache.get (4));} / / cache cache private Map cache / / map private Map freqMap; private int capacity; private int size; / / Storage minimum frequency value private int min; public LFUCache1 (int capacity) {this.capacity = capacity; cache = new HashMap (); freqMap = new HashMap ();} public int get (int key) {Node node = cache.get (key) If (node = = null) return-1; / / if the current element is found, add 1 freqInc (node) to the frequency; return node.value;} public void put (int key, int value) {if (capacity = = 0) return; Node node = cache.get (key); if (node! = null) {node.value = value; freqInc (node) } else {if (size = = capacity) {Node deadNode = removeNode (); cache.remove (deadNode.key); size -;} Node newNode = newNode (key,value); cache.put (key,newNode); addNode (newNode); size++ }} / / processing frequency map private void freqInc (Node node) {/ / delete the current node LinkedHashSet set = freqMap.get (node.freq) from the linked list corresponding to the original frequency; if (set! = null) set.remove (node) / / if the current frequency is the minimum frequency and the linked list is empty after the element is removed, the min value if (node.freq = = min & & set.size () = 0) {min = node.freq + 1;} / / is added to the linked list node.freq + +; LinkedHashSet newSet = freqMap.get (node.freq) corresponding to the new frequency. / / if the high frequency sublinked list does not already exist, initialize an if (newSet = = null) {newSet = new LinkedHashSet (); freqMap.put (node.freq,newSet);} newSet.add (node) } / / add elements, update frequency private void addNode (Node node) {/ / add new elements, definitely need to add LinkedHashSet set = freqMap.get (1) to the linked list of frequency 1; if (set = = null) {set = new LinkedHashSet (); freqMap.put (1);} set.add (node) / / the minimum frequency of update is 1 min = 1;} / the element private Node removeNode () {/ / the element that has not been accessed for the longest time with the minimum frequency is deleted and LinkedHashSet LinkedHashSet set = freqMap.get (min) corresponding to the minimum frequency is found. / / the first element iterated to is the one that has not been accessed for the longest time. Node node = set.iterator (). Next (); set.remove (node); / / if the current node frequency is equal to the minimum frequency, and after the element is removed, set is empty, then min plus 1 if (node.freq = = min & & set.size () = 0) {min + + } return node;} private class Node {int key; int value; int freq = 1; public Node (int key, int value) {this.key = key; this.value = value;} public Node () {}

Scheme 4: manually implement a frequency linked list

Train of thought:

Because scheme 3 uses LinkedHashSet which comes with JDK, which implements a class of hash table and two-way linked list, in order to reduce hash-related computation and improve efficiency, we implement a two-way linked list to replace it.

In that case, this two-way linked list needs to maintain the access order of all elements under the current frequency. We use head insertion to add the newly added elements to the head of the linked list, so that the longest unaccessed element is at the end of the linked list.

Similarly, we also use two sentinel nodes to represent head and tail nodes to facilitate linked list operation.

The code is as follows:

Public class LFUCache2 {public static void main (String [] args) {LFUCache2 cache = new LFUCache2 (2); cache.put (1,1); cache.put (2,2); / / returns 1 System.out.println (cache.get (1)); cache.put (3,3) / / remove key 2 / / return-1 (key 2 not found) System.out.println (cache.get (2)); / / return 3 System.out.println (cache.get (3)); cache.put (4,4) / / remove key 1 / / return-1 (key 1 not found) System.out.println (cache.get (1)); / / return 3 System.out.println (cache.get (3)); / / return 4 System.out.println (cache.get (4));} private Map cache; private Map freqMap; private int capacity Private int size; private int min; public LFUCache2 (int capacity) {this.capacity = capacity; cache = new HashMap (); freqMap = new HashMap ();} public int get (int key) {Node node = cache.get (key); if (node = = null) return-1; freqInc (node); return node.value } public void put (int key, int value) {if (capacity = = 0) return; Node node = cache.get (key); if (node! = null) {node.value = value; / / update value freqInc (node) } else {/ / if size reaches the maximum, the longest unaccessed element if (size = = capacity) {/ / the longest unaccessed element DoubleLinkedList list = freqMap.get (min) is removed at the lowest frequency. Because the linked list is head insertion, the first node of the tail node is the longest unvisited element. / / the node to be removed: Node deadNode = list.tail.pre; cache.remove (deadNode.key); list.removeNode (deadNode); size--;} / / create a new node and put the node in the list with frequency 1 Node newNode = newNode (key,value) DoubleLinkedList newList = freqMap.get (1); if (newList = = null) {newList = new DoubleLinkedList (); freqMap.put (1MagneNewList);} newList.addNode (newNode); cache.put (key,newNode); size++; min = 1 / / at this point, you need to reset the min value to 1}} / / modify the frequency private void freqInc (Node node) {/ / delete the frequency corresponding to node list DoubleLinkedList list = freqMap.get (node.freq); if (list! = null) {list.removeNode (node) } / / determine whether min is equal to the current node frequency, and the list of the current frequency is empty. If so, update the min value if (min = = node.freq & & list.isEmpty ()) {min + +;} / / then add the node frequency to 1 and put it to the high frequency list node.freq + +; DoubleLinkedList newList = freqMap.get (node.freq) If (newList = = null) {newList = new DoubleLinkedList (); freqMap.put (node.freq, newList);} newList.addNode (node);} private class Node {int key; int value; int freq = 1; Node pre; Node next Public Node () {} public Node (int key, int value) {this.key = key; this.value = value;}} / / A self-implemented bi-directional linked list private class DoubleLinkedList {Node head; Node tail / / set two sentinel nodes as header and tail nodes to facilitate insertion and deletion of public DoubleLinkedList () {head = new Node (); tail = new Node (); head.next = tail; tail.pre = head } / / is inserted to the front of the linked list every time, that is, public void addNode (Node node) {node.pre = head; node.next = head.next; / / after the head node is set to node head.next.pre = node; head.next = node first. } / / Delete element public void removeNode (Node node) {node.pre.next = node.next; node.next.pre = node.pre } / / determine whether it is empty, that is, whether there is a valid node other than the sentinel node public boolean isEmpty () {/ / determine whether the next node of the header node is the tail node, if so, empty return head.next = = tail;}

Scheme 5: nesting with two-way linked lists

Train of thought:

It can be found that both scheme 3 and scheme 4 use freqmap to store the relationship between frequency and its corresponding linked list, which is also a hash table. This time, we completely use our own two-way linked list to replace freqMap to further improve efficiency.

However, the structure is somewhat complex, it is a two-way linked list, and each element is a two-way linked list. For ease of understanding, I draw its structure as follows: (for convenience, they are called outer linked list and inner linked list respectively)

We think of the whole as a two-way linked list made up of DoubleLinkedList, and then in each DoubleLinkedList object is a two-way linked list made up of Node. Very similar to the form of HashMap array plus linked list.

However, we do not have an array here, so there is no hash collision problem. And are two-way linked lists, there are sentinels, it is easy to flexibly start from the head or tail of the linked list to manipulate elements.

Here, firstLinkedList and lastLinkedList represent the head and tail nodes of the outer linked list, respectively. The element DoubleLinkedList in the linked list has a field freq that records the frequency and forms the outer linked list in the order of big and small, that is, the DoubleLinkedList1.freq in the figure is greater than the DoubleLinkedList2.freq after it.

Whenever a new frequency of DoubleLinkedList needs to be added, it is inserted directly in front of the sentinel lastLinkedList, so lastLinkedList.pre is an internal linked list with a minimum frequency.

In the internal linked list is a two-way linked list made up of Node, and there are also two sentinels representing head-tail nodes, using header insertion. In fact, you can see the internal linked list and scheme 4, the two-way linked list structure shown in the figure is the same, needless to say.

In this way, we can find the element with the least frequency and the longest unvisited, that is,

/ / for the element with the least frequency and the longest unvisited, delete lastLinkedList.pre.tail.pre when cache is full

Therefore, the code is easy to understand:

Public class LFUCache3 {public static void main (String [] args) {LFUCache3 cache = new LFUCache3 (2); cache.put (1,1); cache.put (2,2); / / returns 1 System.out.println (cache.get (1)); cache.put (3,3) / / remove key 2 / / return-1 (key 2 not found) System.out.println (cache.get (2)); / / return 3 System.out.println (cache.get (3)); cache.put (4,4) / / remove key 1 / / return-1 (key 1 not found) System.out.println (cache.get (1)); / / return 3 System.out.println (cache.get (3)); / / return 4 System.out.println (cache.get (4));} Map cache / * these two represent the head and tail nodes of a two-way linked list connected by DoubleLinkedList, and are sentinel nodes. Each list also contains a two-way linked list made up of node. * in the outermost bi-directional linked list, the list with higher freq frequency is in the front, and the smaller list is behind * / DoubleLinkedList firstLinkedList, lastLinkedList; int capacity; int size; public LFUCache3 (int capacity) {this.capacity = capacity; cache = new HashMap (); / / initialize the header and tail nodes of the outer linked list as sentinel nodes firstLinkedList = new DoubleLinkedList (); lastLinkedList = new DoubleLinkedList () FirstLinkedList.next = lastLinkedList; lastLinkedList.pre = firstLinkedList;} / / node private class Node {int key; int value; int freq = 1; Node pre; Node next; DoubleLinkedList doubleLinkedList storing specific key-value pair information Public Node () {} public Node (int key, int value) {this.key = key; this.value = value;}} public int get (int key) {Node node = cache.get (key); if (node = = null) return-1; freqInc (node); return node.value } public void put (int key, int value) {if (capacity = = 0) return; Node node = cache.get (key); if (node! = null) {node.value = value; freqInc (node) } else {if (size = = capacity) {/ * if it is full, the node with the lowest frequency and the longest unaccessed node needs to be deleted * because the frequency of the linked list composed of list decreases in turn from going to the back. Therefore, the minimum frequency list is the two-way node linked list in lastLinkedList.pre * list, which uses head insertion, so the element that has not been accessed for the longest time is lastLinkedList.pre.tail.pre * / / minimum frequency list DoubleLinkedList list = lastLinkedList.pre. / / for the element that has not been accessed for the longest time, you need to delete Node deadNode = list.tail.pre; cache.remove (deadNode.key); list.removeNode (deadNode); size-- / / if the bi-directional linked list in this list is empty after deleting deadNode, delete the list if (list.isEmpty ()) {removeDoubleLinkedList (list);}} / / is not full, then create a new node Node newNode = newNode (key, value) Cache.put (key,newNode); / / determine whether the list with frequency 1 exists. If it does not exist, create a new DoubleLinkedList list = lastLinkedList.pre; if (list.freq! = 1) {DoubleLinkedList newList = new DoubleLinkedList (1); addDoubleLinkedList (newList,list); newList.addNode (newNode) } else {list.addNode (newNode);} size++;}} / / modify frequency private void freqInc (Node node) {/ / remove the current node DoubleLinkedList list = node.doubleLinkedList; if (list! = null) {list.removeNode (node) from the current frequency of list } / / if the bidirectional node chain list in the current list is empty, delete the list if (list.isEmpty ()) {removeDoubleLinkedList (list);} / / add 1 node.freq++; / / to the current node frequency to find the list in front of the current list and add the current node to DoubleLinkedList preList = list.pre / / if the previous list does not exist, a new one is created and inserted into the bi-directional linked list of list. / / the frequency of the previous list is not equal to the current node frequency, then there is no if (preList.freq! = node.freq) {DoubleLinkedList newList = new DoubleLinkedList (node.freq); addDoubleLinkedList (newList,preList); newList.addNode (node) } else {preList.addNode (node);}} / / Delete the current list node public void removeDoubleLinkedList (DoubleLinkedList list) {list.pre.next = list.next; list.next.pre = list.pre from the outer bi-directional linked list } / / once you know its front node, you can insert a new list node behind it public void addDoubleLinkedList (DoubleLinkedList newList, DoubleLinkedList preList) {newList.pre = preList; newList.next = preList.next; preList.next.pre = newList; preList.next = newList } / / maintain a bidirectional DoubleLinkedList linked list + bidirectional Node linked list structure private class DoubleLinkedList {/ / Bidirectional Node linked list in the current list all frequencies are the same int freq; / / the head node of the bidirectional Node linked list in the current list Node head; / / the tail node Node tail of the bidirectional Node linked list in the current list / / the previous list DoubleLinkedList pre; of the current list / / the last list DoubleLinkedList next; public DoubleLinkedList () of the current list {/ / initializes the header and tail node of the internal linked list and acts as a sentinel node head = new Node (); tail = new Node (); head.next = tail Tail.pre = head;} public DoubleLinkedList (int freq) {head = new Node (); tail = new Node (); head.next = tail; tail.pre = head; this.freq = freq } / / Delete a node node in the current list public void removeNode (Node node) {node.pre.next = node.next; node.next.pre = node.pre } / / insert a new node into the current list and record the reference public void addNode (Node node) of the current list in the new node {node.pre = head; node.next = head.next; head.next.pre = node; head.next = node; node.doubleLinkedList = this } / / whether there is a valid node public boolean isEmpty () {/ / only the head and tail sentinel node in the bidirectional node linked list in list, then it is empty return head.next = = tail;}. I believe you have a deeper understanding of "what LFU implementation methods are available". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.