preface
- I have written an article about LRU elimination algorithm before. LRU algorithm records that the idea of LRU algorithm is to eliminate the least recently used elements. When an element is not accessed for a period of time, it is highly likely that it will not be accessed for a period of time afterwards, and then it will be eliminated when the data pool is full.
- This article intends to write about the idea and implementation of LFU algorithm. The idea of LFU algorithm is to eliminate the element with the lowest frequency of recent time use. If there are multiple elements with the lowest frequency of use, then the element with the shortest time in the data pool will be eliminated.
- Compared with LFU algorithm, LRU algorithm uses time dimension to eliminate data based on elements, while LFU algorithm uses frequency dimension to eliminate data. Generally speaking, THE LFU elimination algorithm is better than the LRU elimination algorithm, as long as it is more suitable for the business scenario.
- Before a little lazy so I did not write lRU algorithm code implementation -_-. This time, the lFU algorithm code implementation first out, later have the opportunity to find a time to write the LRU algorithm code implementation, anti-proper understanding of the principle of the realization of the idea is actually quite simple.
O(N) implementation of LFU code implementation
- First, according to the IDEA of LFU algorithm, the linked list is directly thought of:
/** * LFU algorithm list implementation **@author zrh
* @date2021/03/28 * /
public class LfuTest {
/** * Size of linked list datapool */
private final static Integer size = 3;
public static void main(String[] args) {
// Simulate the inserted element
String[] data = {"a"."b"."c"."a"."a"."a"."a"."b"."c"."d"};
LinkedList list = new LinkedList<LfuNode>();
for (String param : data) {
// Perform an insert
test(list, param);
System.out.println("Add element [" + param + "】, result:"+ list); }}private static void test(LinkedList<LfuNode> list, String param) {
// Check whether there are elements in the list
if(! list.isEmpty()) { Iterator<LfuNode> iterator = list.iterator();while (iterator.hasNext()) {
LfuNode next = iterator.next();
// Determine if there is an element in the list that is currently inserted
if (next.value.equals(param)) {
// Data usage frequency +1, and remove data
next.fre += 1;
iterator.remove();
// Loop the data to compare the FRE and reinsert the data into the list where appropriate
for (int i = 0; i < list.size(); i++) {
if (i == list.size() - 1) {
// Add the last bit to the end of the list
list.addLast(next);
return;
} else if (list.get(i).fre <= next.fre
&& list.get(i + 1).fre > next.fre) {
// Insert next at I +1 if the frequency of the I bit element data is less than or equal to the frequency of the current Next, and the frequency of the current Next is less than the frequency of the I +1 bit element data.
// If the elements have the same frequency, put the elements as far to the right as possible, because deleting an element directly removes the leftmost element (the list header element).
list.add(i + 1, next);
return; }}return; }}// If there is data in the list, and new data is inserted, and the list size has reached the maximum, delete the list head node element directly.
if(list.size() == size) { list.removeFirst(); }}// If the list has no elements, add them directly to the list header node
list.addFirst(new LfuNode(param));
}
@Data
static class LfuNode {
/ / data
private String value;
// Data usage frequency
private Integer fre;
public LfuNode(String value) {
this.value = value;
this.fre = 1; }}} -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- running after printing results: add elements [a], result: [LfuTest. LfuNode (value = a, fre =1Lfunode.lfunode (value=b, fre=1), LfuTest.LfuNode(value=a, fre=1[lfutest.lFUNode (value=c, fre=1), LfuTest.LfuNode(value=b, fre=1), LfuTest.LfuNode(value=a, fre=1LfuNode(value=c, fre=1), LfuTest.LfuNode(value=b, fre=1), LfuTest.LfuNode(value=a, fre=2LfuNode(value=c, fre=1), LfuTest.LfuNode(value=b, fre=1), LfuTest.LfuNode(value=a, fre=3LfuNode(value=c, fre=1), LfuTest.LfuNode(value=b, fre=1), LfuTest.LfuNode(value=a, fre=4LfuNode(value=c, fre=1), LfuTest.LfuNode(value=b, fre=1), LfuTest.LfuNode(value=a, fre=5[lfutest.lFUNode (value=c, fre=1), LfuTest.LfuNode(value=b, fre=2), LfuTest.LfuNode(value=a, fre=5LfuNode(value=b, fre=2), LfuTest.LfuNode(value=c, fre=2), LfuTest.LfuNode(value=a, fre=5LfuNode(value=d, fre=1), LfuTest.LfuNode(value=c, fre=2), LfuTest.LfuNode(value=a, fre=5)]
Copy the code- The last three elements in the datapool (linked list) are [D, C, a]. In this case, if lRU algorithm is used to eliminate data, the result after element insertion is [b, C, d].
O(1) implementation of LFU code implementation
- Optimize the time complexity to O(1) with the quick lookup of HashMap and the quick add and remove of elements of LinkedHashSet.
/** * LFU algorithm implementation 2: optimization implementation **@Author: ZRH
* @Date: 2021/3/29 * /
public class LfuCache<K.V> {
/** * Data pool capacity, minimum frequency */
private static Integer capacity;
private static Integer minFre;
private Map<K, LfuNode<K, V>> map1;
private Map<Integer, LinkedHashSet<LfuNode<K, V>>> map2;
/** * constructor - initialization parameter **@param capacity
*/
public LfuCache (Integer capacity) {
this.capacity = capacity;
this.minFre = 1;
this.map1 = new HashMap<>();
this.map2 = new HashMap<>();
}
/** * Add element method **@param k
* @param v
*/
private void add (K k, V v) {
// Add the first element
if (map1.isEmpty()) {
LfuNode node = new LfuNode(k, v);
map1.put(k, node);
LinkedHashSet set = new LinkedHashSet();
set.add(node);
map2.put(node.fre, set);
return;
}
LfuNode<K, V> node;
// The current key is in the data cache pool
if((node = map1.get(k)) ! =null) {
// Remove a node from the set where the node frequency is key
LinkedHashSet<LfuNode<K, V>> set1 = map2.get(node.fre);
set1.remove(node);
if (set1.isEmpty()) {
// Clear the empty collection
map2.remove(node.fre);
}
// Use frequency +1
node.fre += 1;
LinkedHashSet<LfuNode<K, V>> set2 = map2.get(node.fre);
if (null == set2) {
set2 = new LinkedHashSet();
}
// Add the current node to the new set with frequency key
set2.add(node);
map2.put(node.fre, set2);
// Maintain the minimum usage frequency parameter
minFre = map2.keySet().stream().min(Integer::compare).get();
return;
}
// Create a new node object based on K V
node = new LfuNode(k, v);
// The current datapool capacity is full, and the least frequently used elements will be eliminated.
// If the least frequently used element in the set has multiple elements, the oldest element will be eliminated.
if (map1.size() == capacity) {
// Fetch the set of keys based on the minimum frequency of use
LinkedHashSet<LfuNode<K, V>> set = map2.get(minFre);
// Delete the first element (which represents the oldest element) according to the insertion order of the LinkedHashSet
final Iterator<LfuNode<K, V>> iterator = set.iterator();
LfuNode<K, V> oldNode = null;
while (iterator.hasNext()) {
oldNode = iterator.next();
iterator.remove();
break;
}
// Eliminate elements in MAP1
map1.remove(oldNode.key);
}
// Insert new element into map1, map2 set
map1.put(k, node);
LinkedHashSet<LfuNode<K, V>> set1 = map2.get(node.fre);
if (set1 == null) {
set1 = new LinkedHashSet();
}
set1.add(node);
map2.put(node.fre, set1);
// Maintain the minimum usage frequency parameter
minFre = node.fre;
return;
}
@Data
static class LfuNode<K.V> {
/**
* K键 V值 fre使用频率
*/
private K key;
private V value;
private Integer fre;
public LfuNode (K key, V value) {
this.key = key;
this.value = value;
this.fre = 1; }}public static void main (String[] args) {
String[] data = {"a"."b"."c"."a"."a"."a"."a"."b"."c"."d"};
LfuCache cache = new LfuCache(3);
for (String param : data) {
cache.add(param, param);
System.out.println("-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --");
System.out.println(Insert element [" + param + ", minimum element frequency =" + minFre);
System.out.println(" map1 = " + JSON.toJSONString(cache.map1));
System.out.println(" map2 = "+ JSON.toJSONString(cache.map2)); }}} running after printing results: -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 【 a 】 insert element, element = minimum frequency1
map1 = {"a": {"fre":1."key":"a"."value":"a"}}
map2 = {1: [{"fre":1."key":"a"."value":"a"}]} ------------------------- Insert element [b], element minimum frequency =1
map1 = {"a": {"fre":1."key":"a"."value":"a"},"b": {"fre":1."key":"b"."value":"b"}}
map2 = {1: [{"fre":1."key":"a"."value":"a"}, {"fre":1."key":"b"."value":"b"}]} ------------------------- Insert element [c], element minimum frequency =1
map1 = {"a": {"fre":1."key":"a"."value":"a"},"b": {"fre":1."key":"b"."value":"b"},"c": {"fre":1."key":"c"."value":"c"}}
map2 = {1: [{"fre":1."key":"a"."value":"a"}, {"fre":1."key":"b"."value":"b"}, {"fre":1."key":"c"."value":"c"}]} ------------------------- Insert element [a], element minimum frequency =1
map1 = {"a": {"fre":2."key":"a"."value":"a"},"b": {"fre":1."key":"b"."value":"b"},"c": {"fre":1."key":"c"."value":"c"}}
map2 = {1: [{"fre":1."key":"b"."value":"b"}, {"fre":1."key":"c"."value":"c"}].2: [{"fre":2."key":"a"."value":"a"}]} ------------------------- Insert element [a], element minimum frequency =1
map1 = {"a": {"fre":3."key":"a"."value":"a"},"b": {"fre":1."key":"b"."value":"b"},"c": {"fre":1."key":"c"."value":"c"}}
map2 = {1: [{"fre":1."key":"b"."value":"b"}, {"fre":1."key":"c"."value":"c"}].3: [{"fre":3."key":"a"."value":"a"}]} ------------------------- Insert element [a], element minimum frequency =1
map1 = {"a": {"fre":4."key":"a"."value":"a"},"b": {"fre":1."key":"b"."value":"b"},"c": {"fre":1."key":"c"."value":"c"}}
map2 = {1: [{"fre":1."key":"b"."value":"b"}, {"fre":1."key":"c"."value":"c"}].4: [{"fre":4."key":"a"."value":"a"}]} ------------------------- Insert element [a], element minimum frequency =1
map1 = {"a": {"fre":5."key":"a"."value":"a"},"b": {"fre":1."key":"b"."value":"b"},"c": {"fre":1."key":"c"."value":"c"}}
map2 = {1: [{"fre":1."key":"b"."value":"b"}, {"fre":1."key":"c"."value":"c"}].5: [{"fre":5."key":"a"."value":"a"}]} ------------------------- Insert element [b], element minimum frequency =1
map1 = {"a": {"fre":5."key":"a"."value":"a"},"b": {"fre":2."key":"b"."value":"b"},"c": {"fre":1."key":"c"."value":"c"}}
map2 = {1: [{"fre":1."key":"c"."value":"c"}].2: [{"fre":2."key":"b"."value":"b"}].5: [{"fre":5."key":"a"."value":"a"}]} ------------------------- Insert element [c], element minimum frequency =2
map1 = {"a": {"fre":5."key":"a"."value":"a"},"b": {"fre":2."key":"b"."value":"b"},"c": {"fre":2."key":"c"."value":"c"}}
map2 = {2: [{"fre":2."key":"b"."value":"b"}, {"fre":2."key":"c"."value":"c"}].5: [{"fre":5."key":"a"."value":"a"}]} ------------------------- Insert element [d], element minimum frequency =1
map1 = {"a": {"fre":5."key":"a"."value":"a"},"c": {"fre":2."key":"c"."value":"c"},"d": {"fre":1."key":"d"."value":"d"}}
map2 = {1: [{"fre":1."key":"d"."value":"d"}].2: [{"fre":2."key":"c"."value":"c"}].5: [{"fre":5."key":"a"."value":"a"}}]Copy the codeThe last
- The LFU algorithm is supported in the Redis memory weeding strategy and the Dubbo cache weeding strategy.
- If there are any errors in the above code, you are welcome to point out and I will correct it -_-
- For details about algorithm implementation, see the LFU algorithm
- Study with an open mind and make progress together