写点什么

用 Python 手动实现 LRU 算法

发布于: 2021 年 06 月 26 日
用Python手动实现LRU算法

说到 LRU 算法,就不得不提哈希链表。

哈希链表

在开始介绍哈希链表前,我们先简单的回顾一下哈希表。

1. 哈希表的读操作

哈希表和我们现实世界中的“词典”很像,都是以一个“键值对(key-value)”的形式存在,比如我们像要查看“わたし”所对应的中文意思是什么,我们只需要通过“わたし”这个“键”在词典中找到与之对应的值即中文的“我”即可,而不需要从字典的第一页开始一页一页的翻,因此它的时间复杂度是 O(1)。

还记得自己学生时代,总是习惯在字典的侧面用笔将五十音图按照顺序涂上颜色,这样方便更快的查找。

我们查找“わたし”这三个假名,还是有点慢,因为它是三个字符,但是如果我们将他转换成页数,假设每个单词单独一页。然后通过这个页码找单词是不是会更快一些呢?

回到编程的世界,则存在一个叫做哈希函数的东西。在 Python 的语言中每一个对象都有一个与之对应的哈希值(hash 值),无论什么类型的对象,它的 hash 值都是一个整数对象。而值(value)则保存在一个数组里面。转换方式其实很简单:

size 就是我们保存值的数组的大小

但是,由于直接取 hash 值,有可能会出现负数的情况,比如我们“わたし”这个 key 的 hash 值就是“-6935749861035834984”。用负数进行模运算是比较麻烦的一件事。

通常我们是用每一个元素的 ASCII 码相加,再运行模运算。

例如我们上面的那个例子,如果我们用来保存中文“我”的数组大小是 8,而“わたし”的每个值的 ASCII 码分别是 12431,12383,12375

因此我们得到的“わたし”在数组中的下标是



这样我们便可以通过这个下标在数组中更快的找到“我”这个元素。

介绍完哈希表的的读(get),我们再看看怎么将一个值保存进哈希表,即写(put)的操作

2. 哈希表的写操作

比如我们希望将 YYDS 这个网络词语添加到字典中。

  1. 利用上面介绍的方法将 YYDS 转换成数组下标 1

  1. 如果数组中 1 的位置没有元素,则将“永远的神”保存在这个位置

  2. 但是如果,这个位置有内容了怎么办,这个中情况我们通常叫做哈希冲突。通常有两种方式解决这个问题,一个是开放寻址方法(Python 用的就是这种),另一个就是链表法。

  • 放寻址方法:从当前位置向后找,直到找到为空的位置,然后保存数据

  • 链表法:通过修改链表的 head 和 next 来保存数据

3. 哈希链表

其实就是将 hash 和双向链表结合在了一起。这个更方便数据的操作。

时间复杂度期望值:查找,删除,更新, 插入都是 O(1)。

即数据分布很平均,没有相同 hash 值

时间复杂度最坏值:查找,删除,更新, 插入都是 O(n)。

即所有的 hash 值都是重复的

LRU 算法实现

在介绍玩 hash 表后,我们来看一个业务场景。

我们需要对公司的所有员工信息进行管理,各个部门都会使用这个数据,因此为了减少数据的频繁访问,我们将数据保存在内存中的一个 hash 表中。这样数据的查询速度要快很多。但是随着人员增加,日积月累,在不扩展硬件的情况下,总有一天我们的内存会溢出,那么该怎么解决这个问题呢?

这便引出了我们今天的主角-----LRU 算法。

它的核心思想是在有新数据添加进来,且预先分配的空间已满时删除访问最少的那个数据,从而保证数据的正常。

  1. 这是员工数据在 hash 缓存中的,按照被访问的时间顺序,一次从右端开始插入

  1. 这时来了新员工,且分配的内存空间还充足的情况,就会变成下图所示

  1. 如果我们访问二号员工,它就会先将二号删除,然后在右端重新插入


  1. 接着又来一个新员工,但是已经没有足够的内存了,因此我们需要将最左端好久没有访问的数据删除,然后将 6 号员工插入到右端。


这个便是我们的 LRU 算法的核心原理了。

Python 中的 collections.OrderedDict 其实已经对哈希链表进行了很好的实现,但是为了学习我们还是来手动实现一下。

class Node:    def __init__(self, key, value):        self.key = key        self.value = value        self.pre = None        self.next = None
class LRUCache: def __init__(self, limit): self.limit = limit self.hash = {} self.head = None self.end = None
def get(self, key): node = self.hash.get(key) if node is None: return None self.refresh_node(node) return node.value
def put(self, key, value): node = self.hash.get(key) if node is None: # 如果key不存在,插入key-value if len(self.hash) >= self.limit: old_key = self.remove_node(self.head) self.hash.pop(old_key) node = Node(key, value) self.add_node(node) self.hash[key] = node else: # 如果key存在,刷新key-value node.value = value self.refresh_node(node)
def refresh_node(self, node): # 如果访问的是尾节点,无需移动节点 if node == self.end: return # 移除节点 key = self.remove_node(node) self.hash.pop(key) # 重新插入节点 self.put(node.key, node.value)
def remove_node(self, node): if node == self.head and node == self.end: # 移除唯一的节点 self.head = None self.end = None elif node == self.end: # 移除节点 self.end = self.end.pre self.end.next = None elif node == self.head: # 移除头节点 self.head = self.head.next self.head.pre = None else: # 移除中间节点 node.pre.next = node.pre node.next.pre = node.next return node.key
def add_node(self, node): if self.end is not None: self.end.next = node node.pre = self.end node.next = None self.end = node if self.head is None: self.head = node

if __name__ == "__main__": lruCache = LRUCache(5) lruCache.put("001", "用户1信息") lruCache.put("002", "用户2信息") lruCache.put("003", "用户3信息") lruCache.put("004", "用户4信息") lruCache.put("005", "用户5信息") print("----------初始化完成后的排序----------") print(lruCache.hash.keys()) print("----------查询完002后的排序----------") print(lruCache.get("002")) print(lruCache.hash.keys()) print("----------添加新员工后的排序----------") lruCache.put("006", "用户6信息") print(lruCache.hash.keys())
复制代码



发布于: 2021 年 06 月 26 日阅读数: 169
用户头像

一个日语专业的程序猿。 2017.09.10 加入

【坐标】无锡 【软件技能】Java,C#,Python 【爱好】炉石传说 【称号】InfoQ年度人气作者,Intel OpenVINO领航者联盟成员 【B站】https://space.bilibili.com/397260706/ 【个人站】www.it-worker.club

评论 (1 条评论)

发布
用户头像
2021 年 06 月 26 日 21:23
回复
没有更多了
用Python手动实现LRU算法