LRU 居然翻译成最近最少使用？真相原来是这样！（附力扣题解）

2023-02-27 21:20 由 touryung 发表于 #其他

前言

相信有很多同学和我一样，第一次碰到 LRU（Least Recently Used）的这个解释「最近最少使用」都不知道是什么意思，用汤家凤老师的话来说：

我真的感到匪夷所思啊！

最近是表示时间，最少是表示频度，拆开来都知道，但是合在一起就不知道是什么意思了。经过一番搜索后，我发现这可能是国内一些专业名词的通病：翻译问题。甚至百度百科对 LRU 的解释也是这样：

LRU 是 Least Recently Used 的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。

什么叫「选择最近最久未使用的页面予以淘汰」？今天我们就来摸一摸它的底！

LRU 算法过程

LRU 常见的实现是使用一个双向链表保存缓存数据，算法步骤如下：

插入新数据时会插入到链表头部；
当缓存数据被访问时，将该数据移到链表尾部；
当链表满的时候，将链表头部的数据丢弃。

看完算法过程，内心惊呼：这不就是当容量不够用的时候淘汰最久没访问的数据么，和最少有个毛关系啊！按我的理解，Least Recently 其实应该翻译成「最不是最近的」也就是最远的，Least 其实是修饰 Recently，而不应该和它并列翻译成「最近最少」，LRU 说到底就是一个时间维度上的缓存优化算法。

LRU 的兄弟 LFU

LFU（Least Frequently Used）和 LRU 比较相似，也是缓存优化算法，但是他和 LRU 唯一的区别就是，LRU 是时间维度上的，当缓存满的时候，将最久没使用的数据丢弃，而 LFU 是频率维度上的，会将最少使用（使用频次最低）的数据丢弃。

百度百科上对 LFU 的解释如下：

LFU（least frequently used (LFU) page-replacement algorithm）。即最不经常使用页置换算法，要求在页置换时置换引用计数最小的页，因为经常使用的页应该有一个较大的引用次数。但是有些页在开始时使用次数很多，但以后就不再使用，这类页将会长时间留在内存中，因此可以将引用计数寄存器定时右移一位，形成指数衰减的平均使用次数。

这就有点搞笑了， LFU 的翻译是「最不经常使用」，既然作为 LRU 的兄弟，难道你不应该翻译成「最经常最少使用」算法吗？🤣 不过这好像也侧面印证了我上面的猜想应该是正确的。

同样的翻译灾难

鲁棒性

这个名词乍一听，这是什么玩意儿，完全不能从字面意思上推测出实际的含义，结果一查阅发现，这其实是英文 Robustness 的翻译，应该是直接音译的，更直观也更好听的翻译应该是「健壮性」、「稳健性」。

有理数

有人提过一个问题：有理数为什么叫「有理数」？难道是有道理的数？这个答案显然很离谱，但是我们大多数人也就得过且过吧，没有去较真了。但是细加挖掘，会发现有理数的英文是 rational number，其中 rational 被翻译成了「合理的」、「有道理的」，实际上 rational 还有一个意思是「可比的」，也就是能表示成两个整数之比的数是有理数。

这里面还有一段很有意思的历史，感兴趣的可以自行查阅。

总结

从这次经历来看，以后大家要是在一些专业名词上有困惑，不妨看看它翻译之前的英文，结合专业名称具体的含义多多推敲，如果是一个算法，就理解它的算法过程。最后会发现，一切都有源头，每个名词都有它的来历，不管是翻译错误还是什么，说不定还能了解到背后的一些历史渊源。

附：LeetCode 146. LRU 缓存实现

既然说到了 LRU 的实现，我们不妨将 LeetCode 上关于 LRU 的一道高频面试题给解决了。

题目要求如下：

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。

实现 LRUCache 类：

LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存

int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。

void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

首先分析一下这道题需要的数据结构，因为获取缓存元素的 get 方法需要 O(1) 的时间复杂度，因此存储元素很容易想到使用哈希表。但是再仔细读题就会发现，LRU 的核心思想「容量不够删除最远使用的元素」蕴含了数据需要以时间为维度排列成有序序列，且需要频繁在序列头部和尾部操作，因此最终选定使用双向链表。

最终，数据结构选取「哈希表+双向链表」来实现。

首先，先定义双向链表的节点：

var ListNode = function (key, value) {
  this.key = key;
  this.value = value;
  this.prev = null;
  this.next = null;
}

然后，初始化 LRU 的结构：

var LRUCache = function (capacity) {
  this.capacity = capacity;
  this.map = new Map(); // 哈希表
  
  // 初始化双向链表
  this.head = new ListNode();
  this.tail = new ListNode();
  this.head.next = this.tail;
  this.tail.prev = this.head;
};

由于算法中访问过的节点要移到链表末尾，因此先实现一下节点插入末尾的操作：

LRUCache.prototype.insertTail = function (node) {
  this.tail.prev.next = node;
  node.prev = this.tail.prev;
  node.next = this.tail;
  this.tail.prev = node;
}

准备工作做好之后，就开始实现最关键的 get 和 put 方法，由于题目中已经将各个情况都描述清楚了，因此按照题目要求进行逐个实现即可。

首先是 get 方法，如果缓存中没有 key，则返回 -1。如果有 key，那么将该 key 对应的节点从链表中原来的位置删除，然后插入链表末尾，代表最近访问过。最好返回该节点对应的值：

LRUCache.prototype.get = function(key) {
  if (!this.map.has(key)) return -1;
  
  let node = this.map.get(key);
  // 将 node 从原来位置删除
  node.prev.next = node.next;
  node.next.prev = node.prev;
  this.insertTail(node); // 插入链表末尾
  
  return node.value;
};

然后是 put 方法，如果 key 已经存在，那么就把对应的节点找出来修改值，然后移到链表末尾。如果 key 不存在，要先判断一下缓存是否已满，如果满了，要先把头部节点（最远使用）删除，并在哈希表中删除记录，再插入新节点，如果没满，就直接插入新节点：

LRUCache.prototype.put = function(key, value) {
  if (this.map.has(key)) {
    // 如果 key 已经存在，则修改值
    let node = this.map.get(key);
    node.value = value;
    // 移到链表末尾
    node.prev.next = node.next;
    node.next.prev = node.prev;
    this.insertTail(node);
  } else {
	  // 如果 key 不存在，判断是否超出容量
    if (this.map.size >= this.capacity) {
      let rmNode = this.head.next;
      // 删除头部节点
      this.head.next = rmNode.next;
      rmNode.next.prev = this.head;
      
      this.map.delete(rmNode.key);
    }

		// 新建节点插入链表末尾，并存入哈希表
    let newNode = new ListNode(key, value);
    this.map.set(key, newNode);
    this.insertTail(newNode);
  }
};

这道中等题在面试中出现的频率还是比较高的，因此最好还是能掌握。

热门相关：仙城纪第一神算：纨绔大小姐大神你人设崩了网游之逆天飞扬天启预报