Chia-ch'i

The primary purpose of this website is to motivate me to write about life, thoughts, and learning observations.

2025-05-23 Leetcode 146.LRU 5433字记录思考的过程

使用 GPT refine 了文章

2025-05-25

读完题目, 我们需要设计一个支持以下操作的数据结构：get 和 put，并且这两个操作都要在 $O(1)$ 时间内完成。为了实现这一点，我们结合使用了 哈希表（dict） 和 双向链表（Doubly Linked List, DLList）, 这里补充的时候, 刚做这个题目的难点的, 这两个操作同时还要实现在时序上的 order.

为什么需要链表, 而且是 DLList？单用 Python 中的 dict 虽然查找快，但无法保持数据的访问顺序；而使用 list 虽然可以维护顺序，却无法在 $O(1)$ 时间内删除任意节点。而另外一个基础结构, 链表, 实现一个 stack 的时候, 我们在头结尾上添加和删除, 这就都是 O1 的,但是这个时候我们想到了, 我们这个题的逻辑在删除上是也是要 O1 的, 而且应该是从 tail 上删除, 这相当于实现了一个可以前进后出的队列, 但是链表的尾部删除是是 On 的, 就算我们有一个 tail 指针也是一样, 因为我们不知道 tail 这个 node 的前面是什么位置是哪个 node, tail 在被删除之后, 要重新遍历一遍找到新的 tail, , 除非我们在访问的一个节点的时候, 我们可以知道这个 node 的前面是是哪个节点, 方法呼之欲出了—- 使用 双向链表 来存储所有的缓存节点，并维护最近访问的顺序。最近使用的节点放在链表头部，最久未使用的节点在链表尾部；当容量超限时，我们就移除尾部节点。

然后, 我们想一下如何建立链表, 简单, 使用一个 node class 就行了, 于是我们开了一个新的 class, 如下

class Node:
    def __init__(self, key, val):
        self.key = key # why? 
        self.val = val
        self.prev = None
        self.next = None

这里的关键点是：为什么节点中还要记录 self.key？ 这是因为我们在删除最久未使用节点的时候（也就是链表尾部节点），需要从哈希表中同步删除对应的项。我们能通过链表找到这个节点 node，但要从哈希表中 O(1) 时间地删除 table[key]，就必须知道它对应的 key。

你可能会问，为什么不能直接使用这个 node 本身作为哈希表的 key 呢？这是 Python 和 Java 的一个差异。在 Python 中，字典的 key 默认是通过对象的 id（即地址）来计算的 hash 值，除非手动重写 __hash__ 和 __eq__ 方法。而且即使两个节点 Node(key=1, val=100) 看起来值一样，它们的实例地址是不同的。因此不能指望用节点本身作为哈希表的 key 来查找。

a = Node(1, 100)
b = Node(1, 100)
print(a == b)  # False

这意味着，即使两个 node 的内容一样，它们不是同一个 key。所以我们不能用 node 当 key，只能用原始输入的 key。

从功能逻辑上再解释一次：

哈希表 table 提供 $O(1)$ 的 key 到节点的映射。
双向链表记录访问顺序，支持 $O(1)$ 的插入和删除操作。
当我们访问一个 key（get 或 put 更新已有 key）时，我们需要：
1. 在哈希表中快速找到对应的 node。
2. 把这个 node 移到链表的头部（代表最近访问）。
当容量满了时：
1. 我们从链表尾部拿到最旧的节点 node。
2. 通过 node.key 在哈希表中删除对应条目。

所以我们必须在每个 Node 中保留 self.key，因为这是唯一能让我们在 $O(1)$ 时间内，从哈希表中同步删除那一项的手段。

这个结构的设计核心就是：
**哈希表用于快速定位，双向链表用于维护访问顺序。两者结合才能实现整体的 $O(1)$ 性能目标。

更加高屋建瓴地讲, 从 Infra 面试之数据结构六：LRU 文章来说, 解这道题的关键是如何管理复杂度, 把这个难的问题拆开来(难, 只是因为拆的不够简单) 宏观上，代码组织思路：

将该数据结构分为数据和索引两部分
数据用链表组织，可动态维护时间先后。可保证替换时间复杂度为 $O(1)$
索引用哈希表组织，用于快速查找删除。可保证增删时间复杂度为 $O(1)$ 这种数据、索引分离考虑的思想，借鉴数据库的聚集索引|和二级索引.

当然还有题目实现上的细节需要考虑 OK, 我们继续从下面的这个题目中的空代码出发

class LRUCache:

    def __init__(self, capacity: int):
        
    def get(self, key: int) -> int:
        
    def put(self, key: int, value: int) -> None:
        
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value

original 分步骤部分 (这个部分用 GPT Gemini refine 之后发现变化特别大, 保留原始部分了)

现在我们已经写好了, 这里除了一些算法上的实现细节, 其实有两种大的逻辑, 实现同样的功能,

是在比对了有 key 之后使用原来的内存地址上的点, 进行 detach, 再使用同一个移动到最前面的位置,
是在对比有了 key 之后, 直接删除, 然后新创建一个 node 连在 head 后面, 这样会使用更加多的内存开销, 但是实现上更加简单, 而第二种其实代码更加复杂来避免反复的新建, 使用大量的内存, 所以我觉得第一种是第二种的优化, 所以我先写第二种, 再从优化的角度写第一种

OK, 我们现在有, 这里有一个初始值设定的问题, 有些会写 key = None 是什么的 , 继续写下面的代码,

class node:
	def __init__(self,key,val):
		self.key = key
		self.val = val
		self.prev = None
		self.next = None
class LRUCache:
    def __init__(self, capacity: int):
    	# table
    	self.table = {}
        
        # DLList
        self.head = node(None,None)
        self.tail = node(-1,-1)
        self.tail.prev = self.head
        self.head.next = self.tail
        
        # input capacity
        self.capacity = capacity
        
    def get(self, key: int) -> int:
        

    def put(self, key: int, value: int) -> None:

OK, 继续是初始化的步骤, 在这个位置想的是什么呢, 第一个是我们要 table , 第二个是我们要有链表啊, OK, 这就是所有了, 当然还有一个在使用链表做题时候一个 tricky 的地方, 就是 OK,在写了之后, 要继续想, 就是我们具体其实要操作的是数据结构本身, 那么, 其实, 这个要在上面画什么的决策树其实是 table 的添加和删除, 还有链表的添加和删除, 但是字典的添加和删除很简单, python 中都已经有接口实现了, 这时候注意, 我们的链表是我们本身创建的结构, 这个删除和添加的逻辑 python 并没有给我们,

很多题解都写在 class LRUCache 下, 我的疑问是能不能写在 node 中, 好像是可以的, _delete 操作删除 node, 哦哦哦不行? class 中的方法, 可以删除自己吗, 应该可以吧, 再想想插入的方法, 我一般要插入的话要干什么, 都是更新在最新的位置, 那么就是说, 好像和 table 也没什么关联, 那么, 问题就剩下, 如果, 写在本身的话, 插入和删除的输入可不可以是自己, 应该可以是自己的吧, 因为递归的输入就是自己,

OK 上面的问题的产生是因为我把 class node 和 class doublelinkedlist 弄混淆了, 也就是说, 其实这里我们的面向对象编程也省略掉了要创造 doublelinkedlist 这一步, 所以这里这个问题会出现是因为, 我没有思考过的. 继续, 我们先在 class LRUCache 中写我们的方法

class LRUCache:
	'''
	ignore upper codes
	'''
	
	def _delete(self,node):
		
	def _update(self,node):
		

其中删除的逻辑很简单, 就交给 python 的内存回收机制就好了

def _delete(self,node):
	# node.prev
	node.prev.next = node.next
	# node.next 
	node.next.prev = node.prev

但是,这里的 ` _update 要使用 key 吗, 不清楚, 但是可以先写, 首先理解这个逻辑是, 如果存在在 DLList 中, 就 ... 如果不在那么就可以直接加在 head 的后面, OK, 从这个逻辑出发, 我们的 _update` 方法是需要 key 的, 不然, 如何用 table $O(1)$ 时间地来判断重复呢? (这里也说明这个方法要在)

def _update(self, node): # 错了吗

所以我们认为这个 _update 方法需要我们的 key, 在没有做这个题之前, 我觉得我确实想不出来, 因为这些关系都是交织的, 很难一下子直接分割到最小, 所以写成 def _update(self, node, key): 哦是这样吗? 错了, 只是更新一个 node, 但是 key 不更新的话, 那么其实我们也不需要这个 key 了, OK,

def _update(self, node): # 对的?

其实, 我现在感觉没有这个对错, 问题的关键在于这个 key 的作用, 是什么作用, 要不要想不想切割到最小, 这个感觉, OK, 那先按照现在的思路继续写然后想一下, 这个方法要干什么, 现在排除掉了检测, 其实就是什么呢, 就是要实现了一个链表的插入节点的操作, 一共有三个节点的状态应该考虑, 分别是 head, head.next, node

def _update(self, node):

	# 从 head位置, 插入
	headnxt = self.head.next
	self.head.next = node
	
	# node的前后
	node.prev = self.head
	node.next = headnxt
	
	# 原先的head后面的node的prev要接上新的node
	headnxt.prev = node

OK, 那么现在就剩下题目原来的 put 和 get 方法了, 现在, 想一想这个方法要干什么, get 是要检查有没有(注意更新最近使用), 然后 put 是要完成插入的逻辑, 同时要注意更新最近的逻辑, 同时要注意整体的 size, 因为这个 cache 有 capacity. get 比较简单, 先写 get, 大的框架是有 or 没有的逻辑, 这是很简单想到的,

def get(self, key: int) -> int:
	# 有
	if key in self.table:
	
	# 没有
	else:
		return -1

OK, 那么继续实现一下

def get(self, key: int) -> int:
	# 有
	if key in self.table:
		
		# 返回那个对应table[key]
		# 要在前面更新
	# 没有
	else:
		return -1

def get(self, key: int) -> int:
	# 有
	if key in self.table:
		# 创建
		tempnode = node(key,self.table[key])
		
		# 删除
		self._delete(self.table[key])
		del self.table[key] # 要吗?
		# 新建?
		self._update(tempnode)
		self.table[key] = tempnode # 其实前面不要删除更新一下就行了
		return self.table[key].val
	# 没有
	else:
		return -1

那么还剩下一个 put 的方法了, 想一想逻辑,

def put(self, key: int, value: int) -> None:

把决策树都画出来,

输入key
	如果在其中有key的话
		删除原先的node在链表和table中
		添加这个新的node到head后面
		更新table
	如果在其中没有key的话
		现在的node放在head后面
		table更新一下
	最后检查size, 如果超过capacity就从tail开始删除一个
	

写, 这里要注意 table 和链表删除的顺序, 应该先从链表上删除, 因为使用 table 可以用 $O(1)$ 的时间访问对应的节点, 但是如果先在 table 上把这个节点删除掉的话, 那么我们会丢失这个用 key 快速访问的能力, 但是相反的, 我们的删除逻辑本身运行后, 不会影响我们 table 的逻辑, 因为我们是改变 key 对应的 node 的前后连接关系, 而不是说让这个 node 本身变成 None, 但是好像即使是变成 None 也没什么关系, OK, 这里就说完了

def put(self, key: int, value: int) -> None:
	if key in self.table:
		tempNode = node(key,value)
		self._delete(self.table[key])
		self._update(tempNode)
		
	else: # no key in self.table
		tempNode = node(key,value)
		self._update(tempNode)
		self.table[key] = tempNode
	
	if len(self.table) > self.capacity:
		delnode = self.tail.prev
		
		# del 
		self._delete(delnode)
		del self.table[delnode.key]

OK 现在都写完了, 那么, 整体的全部代码如下,

class node:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        # table
        self.table = {}

        # DLList
        self.head = node(None, None)
        self.tail = node(-1, -1)
        self.tail.prev = self.head
        self.head.next = self.tail

        # input capacity
        self.capacity = capacity

    def _delete(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _update(self, node):
        headnxt = self.head.next
        self.head.next = node
        node.prev = self.head
        node.next = headnxt
        headnxt.prev = node

    def get(self, key: int) -> int:
        # 有key的情况下
        if key in self.table:
            # 创建
            tempnode = node(key, self.table[key].val)

            # 删除
            self._delete(self.table[key])
            # del self.table[key]  # 不需要删除，table 直接覆盖

            # 新建并更新
            self._update(tempnode)
            self.table[key] = tempnode

            return self.table[key].val
        # 没有key的情况下
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key in self.table:
            tempNode = node(key, value)
            self._delete(self.table[key])
            self._update(tempNode)
            self.table[key] = tempNode
        else:  # no key in self.table
            tempNode = node(key, value)
            self._update(tempNode)
            self.table[key] = tempNode

        if len(self.table) > self.capacity:
            delnode = self.tail.prev

            # del
            self._delete(delnode)
            del self.table[delnode.key]

对于代码本身的优化, 这里的一个细节和 two sum 题很像, 就我感觉是 code 层面上的剪枝, 对于 put 方法而言, 很容易的就看到, 在 self.table 中在判断完是否有 key 后, 这个条件判断中, 每一个子部分, 都有, 建立 tempNode, 然后是因为刚刚存入, 所以要更新到 head 后, 放置到最新的位置,这都是合理的, 哦那其实, 我们有代码重复在了一个两个不同的地方, 那么只要提出来就好了

def put(self, key: int, value: int) -> None:
	# 想什么时候要额外, 就是有key的时候, OK
	if key in self.table:
		self._delete(self.table[key])
	# 合并了
	tempNode = node(key,value)
	
	
	self.table[key] = tempNode # table
	self._update(tempNode)# 更新到最新
	
	# size检查
	if len(self.table) > self.capacity:
		del_target = self.tail.prev # del_target 
		self._delete(self.table[del_target.key])
		del self.table[del_target.key]

OK, 在这个部分写完之后, 我们可以发现, 我们不需要对于 ` put 方法和 get` 方法在每一步都建立一个新的 node, 在创建一个 node 的时候, 会在计算机上 grab 一个新的内存地址, 然后, 相当于 put 和 get 方法都需要频繁的内存操作,

deepseek- 14b 分析 比如 malloc 和 free 或者垃圾回收的压力。此外，当缓存容量达到上限时，需要替换掉旧的节点，这时候如果一直有新的节点被插入，老节点可能已经被移除或仍在链表中，这可能会导致一些问题，比如内存泄漏或者其他逻辑错误。 - 2第二种方法优点：实现相对直接，不需要复杂的指针调整。缺点：每次访问都创建新节点，导致更多的内存分配和释放操作，可能影响性能。此外，管理旧节点的引用可能会增加代码复杂度。

建立新节点的影响：
- 内存开销：频繁的新建会导致更多的内存分配，增加了垃圾回收或内存管理的压力。
- 性能影响：内存分配操作可能成为性能瓶颈，尤其是在高并发场景下。

OK 现在如果我们只是操作原来在内存上已经建立的节点的话, 那么我们只是用原来已经被创建的对象, 这样可以大幅减小使用内存的开销. 一开始我以为只需要改变 put 方法和 ` get 方法, 但是现在我感觉 _update` 方法也应该被更新

class LRUCache:
    ··· 
    ignoring
    ···
    def _delete(self, node):
    	node.prev.next = node.next
    	node.next.prev = node.prev
    	
	def _add_to_after_head(self,node):
		
		temp_pointer = node
		
		# head
		original_head_nxt = self.head.next
		self.head.next = temp_pointer
		
		# node(temp_pointer)
		temp_pointer.prev = self.head
		temp_pointer.next = original_head_nxt
		
		# original_head_nxt
		original_head_nxt.prev = temp_pointer
		
	def get(self, key: int) -> int: 
		# 剪枝
		if key not in self.table:
			return -1
		# key in table
		temp_pointer = self.table[key]
		# update logic
		self._delete(self.table[key])
		self._add_to_after_head(temp_pointer) # self._move_to_after_head(self.table[key]) both OK ?
		
		# table 不需要动, only 节点的联系在变化就可以了
		return self.table[key].val
	
	def put(self, key: int, value: int) -> None:
		

对于 put 方法而言, 我们还是按照原始的 flow 就好了

def put(self, key: int, value: int) -> None:
	if key not in self.table:
		newNode = node(key,value)
		
		self._add_to_after_head(newNode)
		self.table[key] = newNode
	else: # key in table 
		#dict value 更新
		self.table[key].val = value # 
		# 删除
			
		temp_pointer = self.table[key]  # 指针
		self._delete(self.table[key]) # 原先断掉
		# 更新
		self._add_to_after_head(temp_pointer) # 放到新位置
		
	# size, 实现lru
	if len(self.table) > self.capacity:
		# READ, find
		the_lru_node = self.tail.prev
		
		# DELETE
		self._delete(the_lru_node) # list
		del self.table[the_lru_node.key] # table

GPT 说的, 对 _add_to_after_head 方法的优化, 很简单, 其实我们不需要 tempnode 和 original_head_nxt

def _add_to_after_head(self,node):
		# head
		original_head_nxt = self.head.next
		self.head.next = node
		
		# node(temp_pointer)
		node.prev = self.head
		node.next = original_head_nxt
		
		# original_head_nxt
		original_head_nxt.prev = node

然后可以再简化一下

def _add_to_after_head(self,node):
	node.next = self.head.next
	node.prev = self.head
	# 上一次最新的节点(self.head.next), or现在head后一个的节点
	self.head.next.prev = node
	# head
	self.head.next = node

OK, 那么新的使用原始节点复用的 LRUCache 代码如下(下面的代码是 gpt 生成的, 有些名字不一样)

class Node:
    def __init__(self, key, val):
        self.key = key      # 用于反查哈希表
        self.val = val      # 实际存储的值
        self.prev = None    # 指向前一个节点
        self.next = None    # 指向后一个节点

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.table = dict()  # key -> Node

        # 虚拟头尾节点，便于统一操作
        self.head = Node(None, None)
        self.tail = Node(None, None)
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        """从链表中断开某个节点"""
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_front(self, node):
        """把节点加到链表头部（head后面）"""
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key not in self.table:
            return -1
        
        node = self.table[key]
        self._remove(node)         # 从原位置断开
        self._add_to_front(node)   # 移动到最前面
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.table:
            # 已存在：更新值，并移动到最前面
            node = self.table[key]
            node.val = value
            self._remove(node)
            self._add_to_front(node)
        else:
            # 不存在：判断是否超容量
            if len(self.table) >= self.capacity:
                # 删除最久未用（链表尾部的前一个）
                lru = self.tail.prev
                self._remove(lru)
                del self.table[lru.key]

            # 新建节点并放入头部
            new_node = Node(key, value)
            self.table[key] = new_node
            self._add_to_front(new_node)

最后谈谈, 简单写法用 ordered_dict

这个 title 是一开始全空白的时候留下的, 就是什么都没写的时候. 我一开始以为我这个部分没有写过, 会到时候写不出来, 但是现在实现了 python 版本的 lru 之后, 我发现这个如果用 ordered_dict 方法实现非常简单, 而且在 python3.6 之后, 我们的 dict 就已经默认是有 order 的了, 那感觉就太简单了就是想象一下头和尾可以 $O(1)$ 时间取到的有 append 的先后顺序的 dict 呗, 就留下一个坑吧

Appendix

original 开头部分

首先是背的, 使用链表, 而且是双向链表, 这里, 为什么是要用链表呢, 因为我们想实现 $O(1)$ 时间的删除, 如果使用 arr or 直接使用字典就是 $O (n)$ 了, 这里的这个 trade off 使用了这个性质, 是用 DLList 实现的. 而且因为单链表不行, 

这里的时候我其实对 key 有疑问, 就是, 什么是要在 `node` 这个 `class` 中, 写 `self.key` , 这个的 intuition 呢, 还有一个问题是我在第二次写的时候, 不知道 or 没有这个直接来判断在 dict 中使用的 key 是什么, 是那个输入的 key, 还是可以使用 node 本身呢 (这里有个疑问中的小疑惑, python 中的对象是和 java 一样会使用一个 hashcode 吗, 还是直接是地址, java 直接 print 是 hashcode 吗还是对象的内存地址), OK, 继续, 我自己想的是, 如果用 node 本身作为 table 的 key, 那么 value 一样的时候, key是不一样的, 会找不到对应的值, 所以这里, 可能应该要用本身 func 中输入的 key 作为 table 的 key, 

还有是为什么 DLList 的 node class 中要加入 `self.key`  这里要回到删除机制的概念了, 想到删除, 这里想到的是从 table 上删除, 但是 table 只是作为一个 $O(1)$ 时间访问的功能, table 的访问和删除, 我们可以很快的使用 key 来实现, 但是双向链表呢, 需要在链表上删除和添加对应的 node 的操作, 这个时候, 按照题目的要求, 我们也要 $O(1)$, 想起来(这里是背的), 我们怎么直接取到这个 node 呢, 为什么不可以就是 `table[key]` 然后在里面放一个正常形式的 node 呢? 我们已经是拿到了对应的 node, 为什么还要 key 呢, 对于正常的删除, 这里正常的意思是我们使用 put 方法的时候, 如果本身的 size 在添加的时候超出了 capacity 的话,~~那确实是不需要这个使用 node 中的 self.key,~~ 对就是在这个超出的 capacity 的功能上, 我们可以使用 $O(1)$ 的时间删除在链表上的点, 但是, 我们如果使用原始的 node class 的样式的话, 在 table 上如何删除对应的对象呢, 这里, table 要 O1 只能使用 key 来进行访问, 那么如果我们在访问到一个节点的时候, 我们没有 key 这个值的话, 我们就不可以在得到 node 的情况下, 用 O1 的时间定位到(查询到?)这个 node 在 table 上, 所以我们在设计这个 node 的时候, 我们加上了 self.key 这个参数

2025 11
2024 3
2023 8

Chia-ch'i

2025-05-23 Leetcode 146.LRU 5433字记录思考的过程

original 分步骤部分 (这个部分用 GPT Gemini refine 之后发现变化特别大, 保留原始部分了)

最后谈谈, 简单写法用 ordered_dict

Appendix

original 开头部分

2025

2025-06-04 lc59. Spiral Matrix II

2025-06-03 lc977.Squares of a Sorted Array

2025-06-03 lc704. Binary Search

2025-06-03 lc209. Minimum Size Subarray Sum

2025-05-29-反思日记-含蓄和直白写法的思考和对比(我与GPT的问答和后记前言)

2025-05-23 Leetcode 146.LRU 5433字记录思考的过程

2025-05-01 Dot products点积 and duality Chapter 9/16

Linear Algebra Starting from Matrix Multiplication

Thinking and Re-thinking of Learning and Happiness

Recursive problem and Thinking Process

2025-03-07-How I use LLMs by Andrej Karpathy 看后总结

2024

Life goals before the age of 30 (in addition to finding a job)

签证准备材料list

Notes for ‘How To Read MTF Curves’ article

2023

Inner producted 一些问题

learning how to learn powerful mental tools to help you master tough subjects

Discrete Mathematics

Injective, Surjective and bi-jective

MIT missing Cour

Proof of Cramer’s Rule

ELEC211: Digital Electronics & Microprocessor Systems

ELEC202 Lec 7&8 FM&PM