头条面试题：如何实现 LRU 原理？
LRU 原理作为操作系统课程中的一个重要部分在很多地方会被考到（比如操作系统课的考试或者一些公司的面试题）。
LRU 算法的设计原则是：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。
这个算法的出发点在于：如果某个页面被访问了，则它可能马上还要访问。反之，如果很长时间未被访问，则它在最近一段时间也不会被访问。
该算法的性能接近于最佳算法，但实现起来较困难。因为要找出最近最久未使用的页面，必须为每一页设置相关记录项，用于记录页面的访问情况，并且每访问一次页面都须更新该信息。这将使系统的开销加大，所以在实际系统中往往使用该算法的近似算法。
对于考试题目而言，由于一般是卷面考试，所以我们通常需要完成的是在纸上描绘出 LRU 的置换原理，一般题目如下：
最近最久未使用算法例
假定系统为某进程分配了 3 个物理块，进程运行时的页面走向为 1，2，3，4，1，2，5，1，2，3，4，5，开始时 3 个物理块均为空，计算采用 最近最久未使用页面淘汰算法时的缺页率 ？（10/12）
对于面试而言，可能就不仅仅是「明白概念」+「画出示例」那么简单了，可能还需要自己动手去实现一个 LRU 算法的小 Demo。
146.LRU缓存机制
在力扣上有这么一道题：
并且给出了提示——在 O(1) 时间复杂度内完成 get 和 put 操作。
一个比较通用的做法是通过 Hashmap + Double Linked List 来完成，图示如下：
这样，整个数据的操作过程如下：
实现算法代码如下：
from collections import OrderedDict
class LRUCache:
"""Implement LRUCache using OrderedDict"""
def __init__(self, capacity: int):
self._ordered_dict = OrderedDict()
self._capacity = capacity
def get(self, key: int) -> int:
self._move_to_end_if_exist(key)
return self._ordered_dict.get(key, -1)
def put(self, key: int, value: int) -> None:
self._move_to_end_if_exist(key)
self._ordered_dict[key] = value
if len(self._ordered_dict) > self._capacity:
self._ordered_dict.popitem(last=False) # popitem支持弹出头部或尾部
def _move_to_end_if_exist(self, key: int) -> None:
if key in self._ordered_dict:
self._ordered_dict.move_to_end(key)
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
Redis
Redis LRU algorithm is not an exact implementation. This means that Redis is not able to pick the best candidate for eviction, that is, the access that was accessed the most in the past. Instead it will try to run an approximation of the LRU algorithm, by sampling a small number of keys, and evicting the one that is the best (with the oldest access time) among the sampled keys.
Redis 是一个著名的键值对数据库，在 Using Redis as an LRU cache 中我们知道 Redis 可以用来做为 LRU 缓存（虽然不是一个非常标准的实现，因为 Redis 可能无法选出最佳换出项），Redis 的方法是随机取出若干个 key，然后按照访问时间排序后，淘汰掉最不经常使用的页面，一个较为详尽的分析在参考资料中已经有所提及，建议有兴趣的读者参考。
参考资料
1.LRU原理和Redis实现——一个今日头条的面试题
2.LeetCode 算法题解——LRU 缓存机制
力扣
本文作者：Nova Kwok
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/14447.html
