Lru_cache(functools에서)는 어떻게 작동합니까?
특히 재귀적 코드를 사용할 때는 엄청난 개선이 있습니다.lru_cache캐시는 빠르게 처리되어야 하는 데이터를 저장하고 컴퓨터가 재계산되지 않도록 하는 공간이라는 것을 이해합니다.
Python의 기능 lru_cachefunctools에서 내부적으로 작동합니까?
구체적인 답을 찾고 있는데, 파이썬의 다른 부분처럼 사전을 사용하나요?은 합니까?return 가치?
파이썬이 사전 위에 많이 구축되어 있다는 것은 알고 있지만, 이 질문에 대한 구체적인 답을 찾을 수 없었습니다.
그functools소스 코드는 https://github.com/python/cpython/blob/master/Lib/functools.py 에서 사용할 수 있습니다.
lru_cache를 사용합니다._lru_cache_wrapper패턴이 는(인수 패턴이 있는 장식가)입니다.cache함수의 반환 값을 저장하는 컨텍스트의 사전입니다(모든 장식된 함수는 고유한 캐시 딕트를 가집니다).사전 키는 다음을 사용하여 생성됩니다._make_key인수에서 함수를 추출합니다.아래에 몇 가지 대담한 설명이 추가되었습니다.
# 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
LRU 캐시용 Python 3.9 소스 코드: https://github.com/python/cpython/blob/3.9/Lib/functools.py#L429
Fib 코드 예제
@lru_cache(maxsize=2)
def fib(n):
if n == 0:
return 0
if n == 1:
return 1
return fib(n - 1) + fib(n - 2)
LRU Cache 데코레이터는 일부 기본 케이스를 확인한 다음 래퍼 _lru_cache_wrapper로 사용자 함수를 래핑합니다.래퍼 내부에서는 캐시에 항목을 추가하는 논리, 즉 순환 대기열에 새 항목을 추가하는 논리, 순환 대기열에서 항목을 제거하는 논리가 발생합니다.
def lru_cache(maxsize=128, typed=False):
...
if isinstance(maxsize, int):
# Negative maxsize is treated as 0
if maxsize < 0:
maxsize = 0
elif callable(maxsize) and isinstance(typed, bool):
# The user_function was passed in directly via the maxsize argument
user_function, maxsize = maxsize, 128
wrapper = _lru_cache_wrapper(user_function, maxsize, typed, _CacheInfo)
wrapper.cache_parameters = lambda : {'maxsize': maxsize, 'typed': typed}
return update_wrapper(wrapper, user_function)
elif maxsize is not None:
raise TypeError(
'Expected first argument to be an integer, a callable, or None')
def decorating_function(user_function):
wrapper = _lru_cache_wrapper(user_function, maxsize, typed, _CacheInfo)
wrapper.cache_parameters = lambda : {'maxsize': maxsize, 'typed': typed}
return update_wrapper(wrapper, user_function)
return decorating_function
는 lru_cache를 .maxsize(when negative)를 추가합니다.CacheInfo마지막으로 래퍼를 추가하고 데코레이터 문서 및 기타 세부 정보를 업데이트합니다.
lru_cache_message
Lru Cache 래퍼에는 부기 변수가 거의 없습니다.
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래퍼는 작업을 수행하기 전에 잠금을 획득합니다.
몇 가지 중요한 변수 - 루트 목록에는 다음을 준수하는 모든 항목이 포함되어 있습니다.
maxsize할은 자기 가치입니다. 뿌리를 기억하는 중요한 개념은 자기 참조 그 자체입니다.(root[:] = [root, root, None, None])이전(0) 및 다음(1) 위치에서
3개의 높은 수준
첫 번째 경우는, 언제.
maxsize즉, 기능이 을 의미합니다. 사용자 기능을 .0입니다. 즉, 캐시 기능이 없음을 의미합니다. 래퍼는 캐시 기능 없이 사용자 기능을 래핑합니다.래퍼는 캐시 누락 횟수를 증가시키고 결과를 반환합니다.def wrapper(*args, **kwds): # No caching -- just a statistics update nonlocal misses misses += 1 result = user_function(*args, **kwds) return result두 번째 경우.언제
maxsize섹션에서는 캐시에 .섹션에서는 캐시에 저장할 요소의 수에 제한이 없습니다.그래서 래퍼는 캐시(사전)에서 키를 확인합니다.키가 있으면 래퍼가 값을 반환하고 캐시 적중 정보를 업데이트합니다.그리고 키가 누락되면 래퍼는 사용자가 전달한 인수로 사용자 함수를 호출하여 캐시를 업데이트하고 캐시 누락 정보를 업데이트한 후 결과를 반환합니다.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세 번째 경우는, 언제.
maxsize는 기본값(128) 또는 사용자가 전달한 정수 값입니다.다음은 실제 LRU 캐시 구현입니다.스레드 세이프 방식으로 래퍼에 있는 전체 코드입니다.캐시에서 읽기/쓰기/삭제 작업을 수행하기 전에 래퍼가 RLock을 가져옵니다.
LRU 캐시
캐시의 값은 4개 항목의 목록으로 저장됩니다(루트 기억).첫 번째 항목은 이전 항목에 대한 참조, 두 번째 항목은 다음 항목에 대한 참조, 세 번째 항목은 특정 기능 호출에 대한 키, 네 번째 항목은 결과입니다. 인수 1의 입니다.
[[[...], [...], 1, 1], [[...], [...], 1, 1], None, None])에 [...]는 자기(목록)입니다.첫 번째 검사는 캐시 적중입니다."예"인 경우 캐시의 값은 4개의 값 목록입니다.
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마지막으로 캐시 적중 정보를 증분하고 결과를 반환합니다.캐시 누락일 경우, 누락 정보를 업데이트하고 코드에서 세 가지 경우를 확인합니다.세 가지 작업은 모두 RLock을 획득한 후에 수행됩니다.다음 순서로 소스 코드의 세 가지 경우 - 잠금 키를 획득한 후 캐시가 가득 찼으며 캐시가 새 항목을 가져올 수 있습니다.예를 들어, 캐시가 가득 차지 않고, 캐시가 가득 차 있고, 잠금을 획득한 후에 캐시에서 키를 사용할 수 있는 순서를 따릅니다.
캐시가 가득 차지 않을 때
...
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)
꽉 차지 의 ""를 합니다.
result(link = [last, root, key, result])루트의 이전 참조, 루트, 키 및 계산된 결과를 포함합니다.다음 의 맨 (링크).
root[PREV] = link항목이 ().last[NEXT]=link합니다.cache[key] = link).마지막으로, 캐시가 가득 찼는지 확인합니다.
cache_len() >= maxsize and cache_len = cache.__len__ is declared in the top를 를 full로 을 클릭하고 상태를 full로 설정합니다., 의 첫 번째 값을 하면 fib의 첫 값을 합니다.
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]
캐시가 가득 찬 경우
...
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키와 결과를 업데이트합니다. - 그런 다음 이전 루트 다음 항목을 새 루트(
root=oldroot[NEXT]새 키 및합니다().oldkey = root[KEY] and oldresult = root[RESULT]) . - None(으로 설정합니다.
root[KEY] = root[RESULT] = None). - 키의 합니다(캐시에이항삭목제키의전서삭(▁delete캐▁the)).
del cache[oldkey]합니다.cache[key] = oldroot). - fibonacci 예제의 경우, 캐시가 가득 찼을 때 키는
2은 트루값입니다.[[[[...], [...], 1, 1], [...], 0, 0], [[...], [[...], [...], 0, 0], 1, 1], None, None]블록의 는 그고블끝에있새뿌는리로운는록입니다.[[[[...], [...], 0, 0], [...], 2, 1], [[...], [[...], [...], 2, 1], 0, 0], None, None]와 같이 키 보는바 같이 키와 시키▁as1로 대체되었습니다.2.
잠금을 획득한 후 캐시에 키가 나타날 때.
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
키가 캐시에 나타나면 잠금을 획득한 후 다른 스레드가 값을 대기열에 넣었을 수 있습니다.그래서 할 일이 별로 없어요, 포장지는 결과를 반환합니다.
마지막으로, 코드는 결과를 반환합니다.캐시 누락 부분을 실행하기 전에 코드 업데이트 캐시가 정보를 누락하고 make_key 함수를 호출합니다.
참고: 중첩된 목록 들여쓰기를 수행할 수 없으므로 형식 지정에서 답변이 다소 적게 보일 수 있습니다.
당신은 여기서 소스 코드를 확인할 수 있습니다.
기본적으로 두 가지 데이터 구조, 즉 사전 함수 매개변수를 결과에 매핑하는 것과 연결된 목록을 사용하여 함수 호출 내역을 추적합니다.
캐시는 기본적으로 다음을 사용하여 구현됩니다. 이는 매우 자명합니다.
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
......
언급URL : https://stackoverflow.com/questions/49883177/how-does-lru-cache-from-functools-work
'programing' 카테고리의 다른 글
| Terraform은 모듈에 따라 달라집니다. (0) | 2023.05.04 |
|---|---|
| Python에서 stdout 및 stderr을 로거로 리디렉션하는 방법 (0) | 2023.05.04 |
| 중단점은 현재 적중되지 않습니다.Silverlight 응용 프로그램에서 이 문서에 대한 기호가 로드되지 않았습니다. (0) | 2023.05.04 |
| 윈도우 개발 기계를 사용하여 아이폰용으로 개발하려면 어떻게 해야 합니까? (0) | 2023.04.29 |
| Windows에서 npm 런타임 스크립트를 위한 셸을 설정하는 방법 (0) | 2023.04.29 |