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

This article will explain in detail what is the difference between lru and lfu algorithm, the content of the article is of high quality, so the editor will share it with you for reference. I hope you will have a certain understanding of the relevant knowledge after reading this article.

Difference: LRU is the least recently used page replacement algorithm, eliminating the pages that have not been used for the longest time, while LFU is the least commonly used page replacement algorithm recently, eliminating the pages that have been visited the least in a certain period of time. The key to LRU is to see how long the page was last used until scheduling occurred, while the key to LFU is to see how often the page is used over a certain period of time.

Common caching algorithms

LRU (Least recently used) is the least used recently, and if the data has been accessed recently, it is more likely to be accessed in the future.

LFU (Least frequently used) is the least frequently used, and if a data is rarely used in the most recent period of time, it is less likely to be used in the future.

FIFO (Fist in first out) first-in, first-out, if a data is the first to enter the cache, it should be eliminated as soon as possible.

LRU caching

For example, the cache strategy of the browser and the cache strategy of memcached all use the LRU algorithm, and the LRU algorithm will eliminate the data that will not be accessed in the near future. The reason why LRU is so popular is that it is relatively simple to implement, and it is also very practical for practical problems, with good runtime performance and high hit rate. Here's how to implement LRU caching:

New data is inserted into the header of the linked list

Whenever the cache hits (that is, the cache data is accessed), the data is moved to the header of the linked list

When the list is full, discard the data at the end of the list

The operations that LRU Cache has:

Set (key,value): if key exists in hashmap, first reset the corresponding value, then get the corresponding node cur, delete the cur node from the linked list and move it to the header of the linked list; if key does not exist in the hashmap, create a new node and place the node in the header of the linked list. When the Cache is full, delete the last node of the linked list.

Get (key): if key exists in hashmap, put the corresponding node in the header of the linked list and return the corresponding value; if it does not exist, return-1.

The difference between LRU and LFU:

LRU is the least recently used page replacement algorithm (Least Recently Used), which is the first to eliminate pages that have not been used for the longest time!

LFU is the least commonly used page replacement algorithm (Least Frequently Used) recently, that is, eliminating the pages that have been visited the least in a certain period of time!

For example, the period T of the second method is 10 minutes, if the paging is done every minute, the main memory block is 3, and if the desired page direction is 2 1 2 1 2 3 4

Note that a page break occurs when page 4 is adjusted.

Page 1 should be replaced by LRU algorithm (page 1 has not been used for the longest time), but page 3 should be replaced by LFU algorithm (page 3 is only used once in ten minutes)

On the difference between lru and lfu algorithm to share here, I hope the above content can be of some help to you, can learn more knowledge. If you think the article is good, you can share it for more people to see.

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.