Dynamic Programming in Python v1

Hier ein Beispiel wann man am besten dem Paradigma dynamisch Programmieren folgen sollte.
Angenommen wir wollen mit Python Faktor berechnungen durchführen, dann könnte wir das so oder ähnlich realisieren

Here an example for a use case of when to use dynamic programming.
As example I want to show how it works with calculating the factorial number in python.

def factorial_without_cache(num: int):
    if num <= 1:
        return 1
    else:
        return num * factorial_without_cache(num - 1)

Mit timeit überprüfen wir die Dauer der aktuellen umsetzung.

With timeit I will check the duration for the current function

timeit('[factorial_without_cache(i) for i in range(1, 20)]', globals=globals())
15.266374646002077

Und nun wollen wir das dynamische Programmieren benuzen hierfür können wir in Python ganze einfach lru_cache aus dem packet functools verwenden

And now let's use dynamic programming in Python for this we use lru_cache from functools

# maxsize => max values not memory size
@lru_cache(maxsize=1024)
def factorial_with_cache(num: int):
    if num <= 1:
        return 1
    else:
        return num * factorial_with_cache(num - 1)

Dann wollen wir uns doch mal das Ergebnis anschauen.

Let's check the result

timeit('[factorial_with_cache(i) for i in range(1, 20)]', globals=globals()) 
1.356531012999767

Wie wir sehen können sind wir deutlich schneller, aber woran liegt das??
Die Lösung ist einfach wie genial mit lru_cache berechnen wir nämlich nur Werte dir wir noch nicht im Cache haben.

Wow, we are so much faster but how is this possible??
The solution is easy and genius lru_cache we calculate only for values which are not in the cache.

[factorial_with_cache(i) for i in range(1, 2048)]
factorial_with_cache.cache_info()
CacheInfo(hits=2046, misses=2047, maxsize=1024, currsize=1024)


Link: lru_cache docs

02 Mai. 20
Zurück

© 2017 - 2020 FtC-Webdev