Как работает кэш Lru (из functools)?

Особенно при использовании рекурсивного кода есть значительные улучшения с lru_cache. Я понимаю, что кэш-это пространство, в котором хранятся данные, которые должны быть обработаны быстро и спасают компьютер от повторного вычисления.

Как работает Python lru_cache от functools работают внутренне?

Я ищу конкретный ответ, использует ли он словари, как и остальные Python? Сохраняет ли он только значение return?

Я знаю, что Python сильно построен однако, помимо словарей, я не смог найти конкретного ответа на этот вопрос. Надеюсь, кто-то сможет упростить этот ответ для всех пользователей на StackOverflow.

2 2
python python-3.x numpy caching lru

2 ответа:

Источник функций доступен здесь: https://github.com/python/cpython/blob/3.6/Lib/functools.py

Lru_cache decorator имеет словарь cache (в контексте - каждая декорируемая функция имеет собственный Cache dict), где он сохраняет возвращаемое значение вызываемой функции. Ключ словаря генерируется с помощью функции _make_key в соответствии с аргументами. Добавлено несколько жирных комментариев: 

# one of decorator variants from source:
def _lru_cache_wrapper(user_function, maxsize, typed, _CacheInfo):
    cache = {}                                # RESULTS SAVES HERE
    # ...
    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:            # ALREADY CALLED WITH PASSED ARGUMENTS
            hits += 1
            return result                     # RETURN SAVED RESULT
                                              # WITHOUT ACTUALLY CALLING FUNCTION
        result = user_function(*args, **kwds) # FUNCTION CALL - if cache[key] empty
        cache[key] = result                   # SAVE RESULT
        misses += 1
        return result
3

Вы можете проверить исходный кодздесь .

По существу, он использует две структуры данных, словарь , отображающий параметры функции в ее результат, и связанный список для отслеживания истории вызовов функций.

Кэш, по существу, реализован с использованием следующих элементов, что довольно само собой разумеющееся.

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