введение
LRU (наименее недавно использованный) — широко используемый алгоритм в стратегии замены кеша. Когда очередь кеша заполнена, когда в очередь добавляется новый элемент, элемент необходимо удалить из существующей очереди.Стратегия LRU заключается в удалении элемента, к которому последний раз обращались, чтобы освободить место для нового элемента.
Изучаю Python 3.6functools.lru_cacheВ исходниках можно найти, что он реализует кэширование LRU через двусвязный список плюс словарь. Давайте изучим реализацию этой функции инструмента.
заявление
Прежде чем погрузиться в функцию, мы можем посмотреть на ее общее использование. Разумное использование кеша может эффективно сократить количество долгих вызовов функций, тем самым значительно повысив общую эффективность.
Посмотрите на классический пример, рекурсивную реализацию функции Фибоначчи:
def fibonacci(n):
if n == 0:
return 0
if n == 1:
return 1
return fibonacci(n - 1) + fibonacci(n - 2)
Очевидно, что во время вызова происходит множество повторяющихся вычислений. Итак, мы можем добавитьlru_cacheДекоратор кэширует уже вычисленные данные, улучшая рекурсивную версию функции Фибоначчи:
@lru_cache()
def fibonacci(n):
if n == 0:
return 0
if n == 1:
return 1
return fibonacci(n - 1) + fibonacci(n - 2)
Когда N = 32, вы можете сравнить время вычислений следующих двух версий, и вы увидите, что улучшение эффективности вычислений поразительно:
fibonacci(32) = 2178309
# 没有加缓存的递归版本
Elapsed time: 1497.54ms
# 添加缓存的递归版本
Elapsed time: 0.16ms
Конечно, на самом деле у нас есть лучший способ реализации функции Фибоначчи (временная сложность O(n)), пример выглядит следующим образом:
def fibonacci_fast(n):
a, b = 0, 1
for _ in range(n):
a, b = a + b, a
return a
Вроде сбился, значит быстро переходим к делу и шпионимlru_cacheКак реализован кэш LRU.
Реализация кэша LRU
Глядя на исходный код, можно увидеть, что кэш LRU находится в функции_lru_cache_wrapperреализовано в. В этом разделе изучается только то, как в нем реализован LRU, поэтому из приведенного ниже исходного кода удален посторонний код.
def _lru_cache_wrapper(user_function, maxsize, typed, _CacheInfo):
# 所有 LRU 缓存元素共享的常量:
sentinel = object() # 特殊标记，用来表示缓存未命中
make_key = _make_key # 根据函数参数生成缓存 key
#
# ---------------------------------
# | PREV | DATA(KEY+RESULT) | NEXT|
# ---------------------------------
#
PREV, NEXT, KEY, RESULT = 0, 1, 2, 3 # 链表各个域
# 存放 key 到 node 的映射
cache = {}
full = False
cache_get = cache.get
lock = RLock() # 链表更新不是线程安全的，所以需要加锁
root = [] # 关键：环形双向链表
# 根节点两侧分别是访问频率较高和较低的节点
root[:] = [root, root, None, None] # 初始根节点（相当于一个空的头节点）
def wrapper(*args, **kwds):
nonlocal root, full
key = make_key(args, kwds, typed)
with lock:
link = cache_get(key)
if link is not None: # 缓存命中
# 将被访问的节点移动到环形链表的前面（即 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
return result
# 缓存未命中，调用用户函数生成 RESULT
result = user_function(*args, **kwds)
with lock:
if key in cache:
# 考虑到此时锁已经释放，而且 key 已经被缓存了，就意味着上面的
# 节点移动已经做了，缓存也更新了，所以此时什么都不用做。
pass
elif full: # 新增缓存结果，移除访问频率低的节点
# 下面的操作是使用 root 当前指向的节点存储 KEY 和 RESULT
oldroot = root
oldroot[KEY] = key
oldroot[RESULT] = result
# 接下来将原 root 指向的下一个节点作为新的 root，
# 同时将新 root 节点的 KEY 和 RESULT 清空，这样
# 使用频率最低的节点结果就从缓存中移除了。
root = oldroot[NEXT]
oldkey = root[KEY]
oldresult = root[RESULT]
root[KEY] = root[RESULT] = None
del cache[oldkey]
cache[key] = oldroot
else: # 仅仅新增缓存结果
# 新增节点插入到 root 节点的前面
last = root[PREV]
link = [last, root, key, result]
last[NEXT] = root[PREV] = cache[key] = link
full = (len(cache) >= maxsize)
return result
return wrapper
В соответствии с приведенным выше исходным кодом мы разделим его на следующие узлы для анализа состояния кэша LRU (состояние связанного списка):
- начальное состояние
- Добавлены кешированные результаты (место кеша не заполнено)
- Добавлены кешированные результаты (место кеша заполнено)
- кеш хитов
начальное состояние кэша
В начальном состоянии,cacheпусто, и есть корневой указатель на себя, схема выглядит следующим образом:
Добавлены кешированные результаты (место не заполнено)
Далее добавляем в кеш несколько узлов К1, К2, К3, К4, соответствующий статус связанного списка иcacheСтатус показан на следующем рисунке:
Добавлены кешированные результаты (полное пространство)
На данный момент мы предполагаем, что кеш заполнен. Когда нам нужно добавить новый узел K5, нам нужно «удалить» узел K1 из исходного связанного списка. Обновленная схема выглядит следующим образом:
попадание в кеш
Предполагая, что в это время кеш достигает K2, узел K2 будет найден, и значение узла будет возвращено.В то же время круговой связанный список будет скорректирован, чтобы переместить K2 в правую сторону от корневого узла. (т. е. в начале связанного списка) Обновленная схема выглядит следующим образом:
Суммировать
functools.lru_cacheОн умело использует циклический двусвязный список для реализации кэша LRU.Перемещая узел в начало очереди при попадании в кэш, он косвенно записывает недавно часто посещаемые узлы. Когда пространство кеша заполнено, узел в конце кольцевой очереди с наименьшей частотой совпадений будет автоматически «удален», тем самым освобождая место для новых узлов кеша.
Ссылаться на
Уведомление об авторских правах
- Эта статья написанаChristopher Lопубликовать, принятьCreative Commons Attribution-NonCommercial-ShareAlike 4.0 Международная лицензияЛицензия. Убедитесь, что вы понимаете лицензионное соглашение иперепечатыватьзаявление о времени.
- Постоянная ссылка на эту статью:blog.Chris cab.com/coding-life….