# ACCORDING TO PASSED maxsize ARGUMENT _lru_cache_wrapper
# DEFINES AND RETURNS ONE OF wrapper DECORATORS
def _lru_cache_wrapper(user_function, maxsize, typed, _CacheInfo):
# Constants shared by all lru cache instances:
sentinel = object() # unique object used to signal cache misses
cache = {} # RESULTS SAVES HERE
cache_get = cache.get # bound method to lookup a key or return None
# ... maxsize is None:
def wrapper(*args, **kwds):
# Simple caching without ordering or size limit
nonlocal hits, misses
key = make_key(args, kwds, typed) # BUILD A KEY FROM ARGUMENTS
result = cache_get(key, sentinel) # TRYING TO GET PREVIOUS CALLS RESULT
if result is not sentinel: # ALREADY CALLED WITH PASSED ARGS
hits += 1
return result # RETURN SAVED RESULT
# WITHOUT ACTUALLY CALLING FUNCTION
misses += 1
result = user_function(*args, **kwds) # FUNCTION CALL - if cache[key] empty
cache[key] = result # SAVE RESULT
return result
# ...
return wrapper
sentinel = object() # unique object used to signal cache misses
make_key = _make_key # build a key from the function arguments
PREV, NEXT, KEY, RESULT = 0, 1, 2, 3 # names for the link fields
cache = {}
hits = misses = 0
full = False
cache_get = cache.get # bound method to lookup a key or return None
cache_len = cache.__len__ # get cache size without calling len()
lock = RLock() # because linkedlist updates aren't threadsafe
root = [] # root of the circular doubly linked list
root[:] = [root, root, None, None] # initialize by pointing to self
def wrapper(*args, **kwds):
# Simple caching without ordering or size limit
nonlocal hits, misses
key = make_key(args, kwds, typed)
result = cache_get(key, sentinel)
if result is not sentinel:
hits += 1
return result
misses += 1
result = user_function(*args, **kwds)
cache[key] = result
return result
nonlocal root, hits, misses, full
key = make_key(args, kwds, typed)
with lock:
link = cache_get(key)
if link is not None:
# Move the link to the front of the circular queue
print(f'Cache hit for {key}, {root}')
link_prev, link_next, _key, result = link
link_prev[NEXT] = link_next
link_next[PREV] = link_prev
last = root[PREV]
last[NEXT] = root[PREV] = link
link[PREV] = last
link[NEXT] = root
hits += 1
return result
当项目已经在该高速缓存中时,不需要检查循环队列是否已满或者从缓存中弹出项目,而是改变循环队列中项目的位置,由于最近使用的项目总是在最上面代码移动到队列顶部的最近值,并且前一个顶部项目成为当前项目last[NEXT] = root[PREV] = link和link[PREV] = last和link[NEXT] = root的下一个. NEXT和PREV在顶部初始化,指向列表PREV, NEXT, KEY, RESULT = 0, 1, 2, 3 # names for the link fields中的适当位置。最后,递增该高速缓存命中信息并返回结果。
...
else:
# Put result in a new link at the front of the queue.
last = root[PREV]
link = [last, root, key, result]
last[NEXT] = root[PREV] = cache[key] = link
# Use the cache_len bound method instead of the len() function
# which could potentially be wrapped in an lru_cache itself.
full = (cache_len() >= maxsize)
...
elif full:
# Use the old root to store the new key and result.
oldroot = root
oldroot[KEY] = key
oldroot[RESULT] = result
# Empty the oldest link and make it the new root.
# Keep a reference to the old key and old result to
# prevent their ref counts from going to zero during the
# update. That will prevent potentially arbitrary object
# clean-up code (i.e. __del__) from running while we're
# still adjusting the links.
root = oldroot[NEXT]
oldkey = root[KEY]
oldresult = root[RESULT]
root[KEY] = root[RESULT] = None
# Now update the cache dictionary.
del cache[oldkey]
# Save the potentially reentrant cache[key] assignment
# for last, after the root and links have been put in
# a consistent state.
cache[key] = oldroot
当该高速缓存已满时,使用根作为oldroot(oldroot=root)并更新键和结果。
然后将oldroot的下一项作为新的根(root=oldroot[NEXT]),复制新的根键和结果(oldkey = root[KEY] and oldresult = root[RESULT])。
if key in cache:
# Getting here means that this same key was added to the
# cache while the lock was released. Since the link
# update is already done, we need only return the
# computed result and update the count of misses.
pass
cache = {}
cache_get = cache.get
....
make_key = _make_key # build a key from the function arguments
key = make_key(args, kwds, typed)
result = cache_get(key, sentinel)
更新链表的要点是:
elif full:
oldroot = root
oldroot[KEY] = key
oldroot[RESULT] = result
# update the linked list to pop out the least recent function call information
root = oldroot[NEXT]
oldkey = root[KEY]
oldresult = root[RESULT]
root[KEY] = root[RESULT] = None
......
3条答案
按热度按时间cnwbcb6i1#
functools
的源代码可以在这里找到:https://github.com/python/cpython/blob/master/Lib/functools.pylru_cache
使用_lru_cache_wrapper
装饰器(带参数模式的python装饰器),它有一个cache
字典 * 在上下文 * 中,它保存了所调用函数的返回值(每个装饰的函数都有自己的缓存字典)。字典键是由_make_key
函数从参数中生成的。在下面添加了一些粗体注解:slsn1g292#
LRU缓存的Python 3.9源代码:https://github.com/python/cpython/blob/3.9/Lib/functools.py#L429
示例Fib代码
LRU缓存装饰器检查一些基本情况,然后用wrapper _lru_cache_wrapper Package 用户函数。在 Package 器内部,发生向该高速缓存添加项的逻辑,LRU逻辑,即向循环队列添加新项,从循环队列中删除项。
lru_cache规范化
maxsize(when negative)
,添加CacheInfo
细节,最后添加 Package 器并更新装饰器文档和其他细节。lru_cache_wrapper
maxsize
值的项。要记住的重要概念是根在上一个(0)和下一个位置(1)中自引用自身(root[:] = [root, root, None, None])
三项高级检查
maxsize
为0时,意味着没有缓存功能, Package 器 Package 没有缓存功能的用户函数。 Package 器增加缓存未命中计数并返回结果。maxsize
为None时。在节中,该高速缓存中存储的元素数量没有限制。因此 Package 器检查缓存中的键(字典)。当键存在时, Package 器返回值并更新该高速缓存命中信息。并且当键缺失时, Package 器调用具有用户传递的参数的用户函数,更新缓存,更新该高速缓存未命中信息,并返回结果。maxsize
是默认值(128)或用户传递的整数值时。这里是实际的LRU缓存实现。整个代码在 Package 器中以线程安全的方式。在执行任何操作之前,从该高速缓存中读取/写入/删除, Package 器获得RLock。LRU缓存
[[[...], [...], 1, 1], [[...], [...], 1, 1], None, None]
的实际值。[...]表示对self(列表)的引用。当项目已经在该高速缓存中时,不需要检查循环队列是否已满或者从缓存中弹出项目,而是改变循环队列中项目的位置,由于最近使用的项目总是在最上面代码移动到队列顶部的最近值,并且前一个顶部项目成为当前项目
last[NEXT] = root[PREV] = link
和link[PREV] = last
和link[NEXT] = root
的下一个. NEXT和PREV在顶部初始化,指向列表PREV, NEXT, KEY, RESULT = 0, 1, 2, 3 # names for the link fields
中的适当位置。最后,递增该高速缓存命中信息并返回结果。该高速缓存未满时
result(link = [last, root, key, result])
以包含根的先前引用、根、键和计算结果。root[PREV] = link
),root的上一个项的下一个指向最近的结果(last[NEXT]=link
),并将最近的结果添加该高速缓存(cache[key] = link
)。cache_len() >= maxsize and cache_len = cache.__len__ is declared in the top
),并将状态设置为已满。1
时,根为空,根值为[[...], [...], None, None]
,将结果添加到循环队列后,根值为[[[...], [...], 1, 1], [[...], [...], 1, 1], None, None]
。上一个和下一个都指向键1
的结果。对于下一个值0
,插入后根值为[[[[...], [...], 1, 1], [...], 0, 0], [[...], [[...], [...], 0, 0], 1, 1], None, None]
,上一个为[[[[...], [...], None, None], [...], 1, 1], [[...], [[...], [...], 1, 1], None, None], 0, 0]
,下一个为[[[[...], [...], 0, 0], [...], None, None], [[...], [[...], [...], None, None], 0, 0], 1, 1]
该高速缓存满时
oldroot=root
)并更新键和结果。root=oldroot[NEXT]
),复制新的根键和结果(oldkey = root[KEY] and oldresult = root[RESULT]
)。root[KEY] = root[RESULT] = None
)。del cache[oldkey]
)中删除旧键的项,并将计算结果添加到缓存(cache[key] = oldroot
)中。2
时,根值为[[[[...], [...], 1, 1], [...], 0, 0], [[...], [[...], [...], 0, 0], 1, 1], None, None]
,块末尾的新根为[[[[...], [...], 0, 0], [...], 2, 1], [[...], [[...], [...], 2, 1], 0, 0], None, None]
。正如您所看到的,键1
被删除并替换为键2
。获取锁后,key出现在该高速缓存中。
当键出现在该高速缓存中时,在获得锁之后,另一个线程可能已经将该值入队。所以没有什么要做的, Package 器返回结果。
最后,代码返回结果。在执行该高速缓存未命中部分之前,代码更新缓存未命中信息并调用make_key函数。
注:我不能让嵌套列表缩进工作,因此答案可能看起来有点少的格式。
ngynwnxp3#
你可以在这里查看源代码。
本质上,它使用两种数据结构,一个字典将函数参数Map到其结果,以及一个链表来跟踪函数调用历史。
该高速缓存基本上是使用以下代码实现的,这是非常不言自明的。
更新链表的要点是: