工程师如何用Python实现LRU缓存淘汰算法？

本文共计3043个文字，预计阅读时间需要13分钟。

各位好，欢迎来到算法数据结构专题。今天我们来聊一个非常实用的算法，叫作LRU。LRU的全称是Least Recently Used，即最近最少使用。简单来说，就是指最长时间未被使用的数据。听起来好像很抽象，但其实应用非常广泛。

大家好，欢迎大家来到算法数据结构专题，今天我们和大家聊一个非常常用的算法，叫做LRU。

LRU的英文全称是Least Recently Used，也即最不经常使用。我们看着好像挺迷糊的，其实这个含义要结合缓存一起使用。对于工程而言，缓存是非常非常重要的机制，尤其是在当下的互联网应用环境当中，起到的作用非常重要。为了便于大家更好地理解，我们从缓存的机制开始说起。

缓存

缓存的英文是cache，最早其实指的是用于CPU和主存数据交互的。早年这块存储被称为高速缓存，最近已经听不到这个词了，不知道是不是淘汰了。因为缓存的读写速度要高于CPU低于主存，所以是用来过渡数据用的。CPU从缓存当中读取数据，主存的数据也会先加载到缓存当中来，之后再进入CPU。

后来缓存有了更多的应用和意为，在后端服务当中一般用来快速响应请求。其实这里的思想和记忆化搜索有点像，我们把可能要用到的数据先存起来，后期如果要用到的话，就可以直接从内存当中读取而不是再去计算一遍了。原理也是一样的，有了缓存我们可以把要返回给用户的数据储存在内存中，当同样的请求过来的时候，我们就可以直接从内存当中读取结果，而不是再走一次链路获取数据了。

举一个很简单的例子，比如说我们打开淘宝首页会看到很多商品的推荐。其实推荐商品的流程是非常复杂的，首先要根据一定的策略去商品库当中召回商品。比如根据用户之前的行为召回和历史行为相关的商品，召回了商品之后还要进行清洗，过滤掉一些明确不感兴趣或者是非法、违规的商品。