Python에서 lru_cache의 사용과 실현에 대한 상세한 설명

컴퓨터 소프트웨어 분야에서 캐시(Cache)는 다음에 이 데이터에 더 빨리 접근할 수 있도록 일부 데이터를 메모리에 저장하는 것을 가리킨다. 이것은 전형적인 공간으로 시간을 바꾸는 예이기도 하다.일반적으로 캐시에 사용되는 메모리 공간은 고정되어 있으며, 더 많은 데이터가 캐시를 필요로 할 때, 캐시된 일부 데이터를 제거한 후에 새로운 캐시 데이터를 넣어야 한다.어떤 데이터를 삭제해야 하는지는 캐시 변환 정책과 관련이 있습니다. LRU (Least Recently Used, 최근에 가장 적게 사용) 는 흔히 볼 수 있는 방법이자 Python에서 제공하는 캐시 변환 정책입니다.
다음은 간단한 예시를 통해 파이썬의 lru_cache는 어떻게 사용합니까?

def factorial(n):
  print(f"  {n}  ")
  return 1 if n <= 1 else n * factorial(n - 1)

a = factorial(5)
print(f'5! = {a}')
b = factorial(3)
print(f'3! = {b}')

위의 코드는 함수factorial을 정의하여 n의 곱셈을 계산하고 함수가 호출될 때 n의 값을 출력합니다.그리고 각각 5와 3의 곱셈을 계산하고 결과를 출력합니다.위의 코드를 실행하면 다음과 같이 출력합니다
계산 5의 곱하기
계산 4의 곱하기
계산 3 의 계승
계산 2의 곱하기
계산 1의 곱하기
5! = 120
계산 3 의 계승
계산 2의 곱하기
계산 1의 곱하기
3! = 육
보시다시피factorial(3)의 결과는factorial(5)을 계산할 때 이미 계산되었지만 뒤에는 다시 계산되었다.이런 중복 계산을 피하기 위해서, 우리는 함수factorial을 정의할 때 lru_를 추가할 수 있다cache 장식기, 아래와 같이

import functools
#   lru_cache  ， 
@functools.lru_cache()
def factorial(n):
  print(f"  {n}  ")
  return 1 if n <= 1 else n * factorial(n - 1)

코드를 다시 실행하려면 다음과 같이 입력하십시오.
계산 5의 곱하기
계산 4의 곱하기
계산 3 의 계승
계산 2의 곱하기
계산 1의 곱하기
5! = 120
3! = 육
보시다시피 이번에factorial(3)을 호출할 때 해당하는 출력을 출력하지 않았습니다. 즉factorial(3)은 캐시에서 직접 읽은 결과로 캐시가 효력이 발생했음을 증명합니다.
피lru_che 수식된 함수는 같은 매개 변수에 호출될 때 후속 호출은 캐시에서 결과를 직접 읽는 것이지 실제 함수를 실행하지 않습니다.다음은 파이썬 내부에서 어떻게 lru_를 실현하는지 원본 코드를 깊이 있게 살펴보겠습니다.캐치의글을 쓸 때 파이썬의 최신 발행판은 3.9이기 때문에 여기에서 사용하는 것은 Python 3.9 소스 원본의 주석을 보존하고 있다.

def lru_cache(maxsize=128, typed=False):
  """Least-recently-used cache decorator.
  If *maxsize* is set to None, the LRU features are disabled and the cache
  can grow without bound.
  If *typed* is True, arguments of different types will be cached separately.
  For example, f(3.0) and f(3) will be treated as distinct calls with
  distinct results.
  Arguments to the cached function must be hashable.
  View the cache statistics named tuple (hits, misses, maxsize, currsize)
  with f.cache_info(). Clear the cache and statistics with f.cache_clear().
  Access the underlying function with f.__wrapped__.
  See: http://en.wikipedia.org/wiki/Cache_replacement_policies#Least_recently_used_(LRU)
  """

  # Users should only access the lru_cache through its public API:
  #    cache_info, cache_clear, and f.__wrapped__
  # The internals of the lru_cache are encapsulated for thread safety and
  # to allow the implementation to change (including a possible C version).
  
  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

이 코드에는 다음과 같은 몇 가지 관건이 있다
키워드 매개변수
maxsize는 캐시 용량을 나타냅니다. 만약에 None이 용량을 표시하는 데 제한이 없다면, typed는 매개 변수 형식을 구분하는지 여부를 나타냅니다. 주석에서도 설명합니다. 만약에 typed==True라면 f(3)와 f(3.0)는 서로 다른 함수 호출로 여겨집니다.
24행 기준 분기
하면, 만약, 만약...cache의 첫 번째 매개 변수는 호출 가능합니다. wrapper로 바로 돌아갑니다. 즉, lru_cache는 파라미터가 없는 장식기로서 이것은 Python 3.8에서만 볼 수 있는 특성이다. 즉, Python 3.8과 그 후의 버전에서 우리는 아래의 방식으로 lru_를 사용할 수 있다.cache, 프로그래머가 lru_를 사용하는 것을 방지하기 위해서일 수도 있습니다cache할 때 괄호를 넣는 것을 잊어버리다.

import functools
#   lru_cache  ，
#  
@functools.lru_cache
def factorial(n):
  print(f"  {n}  ")
  return 1 if n <= 1 else n * factorial(n - 1)

Python 3.8 이전 버전에서 위의 코드를 실행하면 오류가 발생합니다. TypeError: Expected maxsize to be an integer or None.
lru_cache의 구체적인 논리는_lru_cache_래퍼 함수에서 이루어진 것은 마찬가지입니다. 원본 코드를 열거하고 주석을 보존합니다.

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
  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

  if maxsize == 0:

    def wrapper(*args, **kwds):
      # No caching -- just a statistics update
      nonlocal misses
      misses += 1
      result = user_function(*args, **kwds)
      return result

  elif maxsize is None:

    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

  else:

    def wrapper(*args, **kwds):
      # Size limited caching that tracks accesses by recency
      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
          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
        misses += 1
      result = user_function(*args, **kwds)
      with lock:
        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
        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
        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)
      return result

  def cache_info():
    """Report cache statistics"""
    with lock:
      return _CacheInfo(hits, misses, maxsize, cache_len())

  def cache_clear():
    """Clear the cache and cache statistics"""
    nonlocal hits, misses, full
    with lock:
      cache.clear()
      root[:] = [root, root, None, None]
      hits = misses = 0
      full = False

  wrapper.cache_info = cache_info
  wrapper.cache_clear = cache_clear
  return wrapper

함수가 시작되는 곳 2~14행은 관건적인 변수를 정의하고,

hits와misses는 각각 캐시 적중과 적중이 없는 횟수

를 나타낸다

root 양방향 순환 체인표의 두결점, 각 노드는 전방향 바늘, 후방향 바늘, 키와 키에 대응하는result를 저장하는데 그 중에서 키는_make_키 함수는 매개 변수에 따라 계산된 문자열에 따라result는 수식된 함수가 주어진 매개 변수에서 되돌아오는 결과입니다.루트는 데이터 키와result를 저장하지 않습니다.

cache는 캐시 데이터를 실제로 저장하는 곳으로 유형은dict입니다.캐치의 키도_make_키 함수는 매개 변수에 따라 계산된 문자열이고value는 키에 대응하는 양방향 순환 체인표의 노드를 저장합니다.

다음은 maxsize에 따라 wrapper를 정의합니다.

maxsize==0, 사실 캐시가 없으면 함수 호출마다 명중하지 않고 명중하지 않은 횟수misses 더하기 1.

maxsize is None, 캐시 크기를 제한하지 않습니다. 함수 호출이 적중하지 않으면 적중 횟수misses가 1을 추가하지 않습니다. 그렇지 않으면 적중 횟수hits가 1을 추가합니다.

캐시의 크기를 제한하려면 LRU 알고리즘에 따라cache, 즉 42~97줄의 코드를 업데이트해야 한다.

캐시 적중 키의 경우 적중 노드를 양방향 순환 체인 테이블의 끝으로 이동하고 결과(47~58줄)

로 되돌려줍니다.

여기는 사전에 쌍방향 순환 체인 테이블의 조합 데이터 구조를 추가하여 O(1)의 시간 복잡도로 주어진 노드를 삭제하는 것을 실현했다.

명중되지 않고 캐시가 가득 차면 가장 오랫동안 사용하지 않은 노드 (root의 다음 노드) 를 삭제하고 체인 테이블의 끝에 새 노드를 추가해야 합니다.실현 중인 최적화가 있습니다. 현재 루트의 키와result를 새로운 값으로 직접 교체하고 루트의 다음 노드를 새로운 루트로 설정합니다. 이렇게 하면 양방향 순환 체인 테이블 구조는 루트의 다음 노드를 삭제하고 새 노드를 체인 테이블의 끝에 추가하는 것과 같지만 노드를 삭제하고 추가하는 작업(68~88줄)을 피할 수 있습니다

.

적중하지 않고 캐시가 가득 차지 않으면 새 노드를 양방향 순환 체인 테이블의 끝에 직접 추가합니다(root[PREV]. 여기가 마지막이라고 생각하지만 코드 주석에 적힌 것은 시작입니다)(89~96줄)

마지막으로 wrapper에 두 개의 속성 함수 추가cache_info 및 cache_clear , cache_info 현재 캐시의 적중력 통계,cache_clear는 캐시를 비우는 데 사용됩니다.위의 곱셈과 관련된 코드는 마지막에factorial을 실행합니다.cache_info(), 출력

CacheInfo(hits=1, misses=5, maxsize=128, currsize=5)

factorial(5)을 처음 실행할 때 명중되지 않았기 때문에misses=5, 두 번째factorial(3)을 실행할 때 캐시가 명중되었기 때문에hits=1.
마지막으로 설명해야 할 것은 여러 개의 키워드 파라미터가 있는 함수에 대해 두 번의 호출 함수 키워드 파라미터가 들어오는 순서가 다르면 서로 다른 호출로 여겨지고 캐시에 명중되지 않는다는 것이다.또한,lru_cache 장식의 함수는list와 같은 가변 형식의 매개 변수를 포함할 수 없습니다. 왜냐하면hash를 지원하지 않기 때문입니다.
요약하자면, 이 글은 우선 캐시의 개념을 소개한 다음에Python에서 lru_를 보여주었다cache의 사용 방법, 마지막으로 원본을 통해 Python에서 lru_ 분석cache의 실현 디테일.
파이썬에서 lru_cache의 사용과 실현에 대한 상세한 설명은 여기까지입니다.cache 내용은 저희의 이전 글을 검색하거나 아래의 관련 글을 계속 찾아보세요. 앞으로 많이 사랑해 주세요!