Dlaczego cache to najbardziej użyteczny dekorator Pythona

Python jest znany ze swojej prostoty i wielu przydatnych zasobów. Nie tylko jest ich wiele w pythonowej społeczności, ale również dużo wewnątrz standardowych bibliotek Pythona. Jednym z najbardziej przydatnych jest dekorator cache, służy on do cache’owania wartości. 

To wszystko jest również częścią jednego z najbardziej pomocnych modułów (tak w Pythonie nazywa się biblioteki), jakim jest functools. Jeśli chcesz dowiedzieć się, co jeszcze może zaoferować ten moduł, sprawdź dokumentację.

Jak wygląda to przyspieszenie? Problem

Do przetestowania dekoratora potrzebujemy bardzo prostego problemu, abyśmy lepiej zrozumieli, co się dzieje. W tym celu stworzymy funkcję rekuencyjną (pętlę), która będzie wywoływać się wielokrotnie. Spróbujemy obliczyć silnię pewnej liczby.

Silnia liczby całkowitej dodatniej n jest zdefiniowana jako iloczyn tej liczby z każdą liczbą całkowitą aż do 1. Na przykład, silnia 4 to 4×3×2×1, co jest równe liczbie 24

Tutaj kod:

def factorial(n):
    return n * factorial(n-1) if n else 1

Jest to dość prosta rekurencja, która sama wywołuje się za każdym razem. Po prostu mnoży n przez wynik silni, używając n - 1, aż osiągnie 1.

Teraz musimy to uruchomić i określić jak długo to potrwa. W tym celu użyjemy kolejnego zasobu z Pythona, jest to moduł timeit. Jak sama nazwa wskazuje, używamy go do pomiaru czasu w celu określenia, jak długo trwa uruchomienie czegoś.

import timeit
import sys
sys.setrecursionlimit(5000)
def factorial(n):
    return n * factorial(n-1) if n else 1

if __name__ == '__main__':
    print(timeit.timeit("factorial(10)", setup="from __main__ import factorial"))

Nie zagłębiając się zbytnio w szczegóły działania timeit, zasadniczo ustawia on punkt początkowy na 0 i pokazuje, ile czasu potrzeba na wykonanie.

Mamy również import modułu sys, który ma za zadanie zwiększyć liczbę rekurencji, które możemy wykonać. Domyślnie jest to 1000. Nie powinno się używać tego w rzeczywistym kodzie, a raczej tylko dla celów testowych.

Wywołajmy teraz metodę, prosząc o obliczenie silni liczby 10, nie interesuje nas sam wynik, a czas. Pytając o silnię liczby 10, zobaczmy, ile czasu nam to zajmie:

Dość szybko, nie ma tu wiele do poprawy, dlatego zmieńmy naszą silnię z 10 na 100 i zobaczmy, jak długo to potrwa:

Cóż, różnica jest tu dość wyraźna, prawda? Pójdźmy jeszcze dalej i spróbujmy z 1000!

Chyba mamy zwycięzcę? 

Moc i siła dekoratora cache

Teraz dodajmy po prostu dekorator do naszej metody i zobaczmy jeszcze raz, jak się zachowa. Potrzebujemy w tym celu modułu functools, aby zaimportować metodę cache’a. Wiedz, że musimy użyć Python 3, aby móc z niego korzystać.

Tak właśnie powinien wyglądać kod:

import timeit
from functools import cache
import sys
sys.setrecursionlimit(5000)
@cache
def factorial(n):
    return n * factorial(n-1) if n else 1

if __name__ == '__main__':
    print(timeit.timeit("factorial(100)", setup="from __main__ import factorial"))

Okey, spróbujmy uruchomić to jeszcze raz, ale nie będziemy już zaczynać od 10, a od 100:

No dobra, domyślam się, że użycie dekoratora cache wiele nam tutaj mówi, prawda? Różnica jest po prostu zdumiewająca. Jeszcze tylko jeden test, teraz z 1000, który trwał dość długo.

Wyszliśmy od tego:

A skończyliśmy na tym:

Ogromna różnica.

Skąd tak duża różnica?

Odpowiedź nie jest zbyt skomplikowana, ten dekorator używa techniki do optymalizacji zwanej memoize (spamiętywanie).

To co tutaj widzimy, to przechowywanie kosztownych wyników wywołań funkcji, w tym przypadku dlatego, że rekurencja używa tego do “cache’owania” i nie oblicza ponownie tego, co już obliczyła, zmniejszając przy tym drastycznie ilość nakładu pracy, aby uzyskać odpowiedź.

Oryginał tekstu w języku angielskim przeczytać można tutaj.