Почему lru_cache медленнее, чем кеш, реализованный в виде словаря для следующего калькулятора Фибоначчи? - PullRequest
Новая
       11

Почему lru_cache медленнее, чем кеш, реализованный в виде словаря для следующего калькулятора Фибоначчи?

0 голосов
/ 12 декабря 2018

Ниже приведены две рекурсивные функции, которые используют памятку.cache_fibonacci использует словарь кеша, а lru_cache_fibonacci использует декоратор Python lru_cache.Почему последний такой медленный? 

from functools import lru_cache

cache=dict()    
def cache_fibonacci(n):
    return helper_fibonacci(n)

def helper_fibonacci(n):
    if n in cache:
        #Cache already exists
        return cache[n]
    if n==1:
        value=0
    elif n==2:
        value=1
    else:
        #Cache not set
        a=helper_fibonacci(n-1)
        b=helper_fibonacci(n-2)
        value=a+b
    cache[n]=value
    return value

@lru_cache(maxsize=1024)
def lru_cache_fibonacci(n):
    if n==1:
        return 0
    if n==2:
        return 1 
    else:
        a=rec_fibonacci(n-1)
        b=rec_fibonacci(n-2)
        return a+b

Выходные данные времени выполнения:

Кэшируемое рекурсивное время = 1.4781951904296875e-05

LRU Кэшированное рекурсивное время = 0.14490509033203125

1 Ответ

0 голосов
/ 17 мая 2019

Политика кэширования LRU: исключить наименее использованный в последнее время.Как нам этого добиться?Ну, это зависит от фактического алгоритма, но суть заключается в следующем. 

Every node/key has an age bit. 
When you access a key x, either get or put, you reset its age to 0.

Почему?Потому что x был последним использованным, и мы обозначаем это, устанавливая его возраст равным 0, указывая, что это похоже на ключ новорожденного.Более поздний, чем другие.

Но нам нужно сделать еще один шаг здесь. 

Increment everyone's age except the one you recently accessed.

Это сделано для того, чтобы показать, что все остальные, кроме x , теперь старшечем их последний возраст.

Все, что остается выселить (если размер нарушен), это выселить ключ, возраст которого самый высокий.В вашем случае это будет 1025-й ключ. 

In summary, it is the increment-all op that's really costly to implement.

Попробуйте увеличить размер кэша, и вы заметите лучшее время выполнения.Тем не менее, это всегда будет меньше, чем диктат.Реализация Dict () в Python - это хеш-таблица.

...