What is the difference between lru and lfu algorithms?

Difference: LRU is the least recently used page replacement algorithm, which eliminates the pages that have not been used for the longest time; while LFU is the least recently used page replacement algorithm, which eliminates the pages that have been visited the fewest times in a certain period. The key to LRU is to look at the length of time from when the page was last used until scheduling occurs; while the key to LFU is to look at the frequency of page use within a certain period of time.

The operating environment of this tutorial: Windows 7 system, Dell G3 computer.

For web development, caching is essential and is also the most common way to improve performance. Whether it is the browser cache (if it is a chrome browser, you can view it through chrome:://cache), or the server-side cache (through an in-memory database such as memcached or redis). Caching can not only speed up user access, but also reduce server load and pressure. Then, it is particularly important to understand the strategies and principles of common cache elimination algorithms.

Common caching algorithms

• LRU (Least recently used) is the least recently used. If the data has been accessed recently, the probability of being accessed in the future will be greater. high.
• LFU (Least frequently used) Least frequently used. If a piece of data has been used rarely in the recent period, it is also very unlikely to be used in the future.
• FIFO (Fist in first out). If a piece of data enters the cache first, it should be eliminated earliest.

LRU Cache

The cache strategy of browsers and memcached cache strategies all use the LRU algorithm. The LRU algorithm will cache the least accessed data in the near future. The data is eliminated. 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. Let’s talk about how to implement LRU cache:

• New data is inserted into the head of the linked list
• Every time the cache hits (that is, the cached data is accessed) , then move the data to the head of the linked list
• When the linked list is full, discard the data at the end of the linked list

LRU Cache has the following operations:

• set(key,value): If the key exists in the hashmap, reset the corresponding value first, then obtain the corresponding node cur, delete the cur node from the linked list, and move it to the head of the linked list; if the key is in If the hashmap does not exist, create a new node and put the node at the head of the linked list. When the Cache is full, just delete the last node of the linked list.
• get(key): If the key exists in the hashmap, put the corresponding node at the head 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), that is, it is eliminated first and has not been used for the longest time. Use the page!

LFU is the least frequently used page replacement algorithm (Least Frequently Used), which means to eliminate the page with the least number of visits within a certain period of time!

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

Note that when page 4 is adjusted, a page fault interrupt will occur.

If the LRU algorithm is used, page 1 should be changed (page 1 has not been used for the longest time), but page 3 should be changed according to the LFU algorithm (within ten minutes, Page 3 has only been used once)

Summary

It can be seen that the key to LRU is to look at the length of time between the last time the page was used and the scheduling;

And The key to LFU is to look at how often a page is used within a certain period of time!

For more related knowledge, please visit the FAQ column!

The above is the detailed content of What is the difference between lru and lfu algorithms?. For more information, please follow other related articles on the PHP Chinese website!