Dynamic Programming met Python. Deel 1: fibonacci.

Sunday 27 March 2011, 21:45:00 | python

Interessante voorbeelden van Dynamic Programming met Python.

Wat is Dynamic Programming?

Wikipedia beschrijft het als a method for solving complex problems by breaking them down into simpler subproblems. Oftewel: als we een bepaald ingewikkeld probleem moeten oplossen, kunnen we dat doen door het op te delen in kleinere, simpelere, problemen. Deze lossen we dan per stuk eenmalig op. Meestal betekent dat dat we dan uiteindelijk minder inspanning kwijt zijn, omdat het vaak gebeurt dat die kleinere problemen vaker voorkomen (in dezelfde of vergelijkbare vorm). Merk op dat b.v. mergesort niet beschouwd wordt als een dynamic programming problem, omdat de deelproblemen veel simpeler zijn als het hoofdprobleem (het samenvoegen van twee reeksen van getallen is triviaal ten opzichte van de sorteer actie zelf).

Wat is een Dynamic Programming Language?

Dit heeft niet direct iets te maken met Dynamic Programming. Wikipedia beschrijft het als a class of high-level programming languages that execute at runtime many common behaviors that other languages might perform during compilation, if at all. Oftewel: een dynamic programming language heeft directe ondersteuning om dingen zoals onderstaande tijdens runtime te kunnen doen:

Ook zijn veel dynamic programming languages dynamically typed. Let op: dat is iets anders als weakly typed of stringly typed!

Python is een prachtig voorbeeld van dit alles. En na het bekijken van een aantal presentaties van PyCon 2011 ( →Pycon 2011 presentaties) leek het me leuk om een aantal inspirerende voorbeelden op een rijtje te zetten. Sommigen vallen onder dynamic programming, anderen misschien meer onder dynamic programming language, maar eingelijk doet het er niet zoveel toe. Wat er wel toe doet is dat het goeie voorbeelden zijn van dingen die je niet of nauwelijks voor elkaar kan krijgen in een ouderwetse (of gewone, zo je wilt) taal zoals Java of C#.

Deel 1 volgt hieronder en gaat over Fibonacci getallen.

deel 1: de Fibonacci reeks.

De Fibonacci reeks is wiskundig gedefinieerd als een reeks getallen waarbij elk volgend getal de som is van zijn twee voorgangers, en 0 en 1 zijn de eerste twee getallen in de reeks: 0, 1, 1, 2, 3, 5, 8, 13, ...

Een directe simplistische vertaling hiervan naar code is als volgt:

def fib(n):
    if n==0:
        return 0
    if n==1:
        return 1
    return fib(n-2) + fib(n-1)

Dit werkt prima zolang n erg klein blijft. Maar zodra n in de buurt van 40 komt ontploft de boel. Wat hij namelijk doet is dat fib(40) gesplitst wordt in fib(38) en fib(39). Vervolgens wordt fib(39) weer opgesplitst in fib(37) en fib(38) maar daarbij wordt niet gebruik gemaakt van de waarde van fib(38) die daarnet al berekend was. Dit waaiert uit tot een enorme recursieve berekening waar gigantische hoeveelheden sommaties vele keren opnieuw bepaald worden, en wat resulteert in een functie call die niet meer eindigt voordat je kleinkinderen met pensioen gaan.

functools.lru_cache - de 1-regelige oplossing

Door 1 regel code toe te voegen wordt het een heel ander verhaal:

from functools import lru_cache

@lru_cache(maxsize=200)
def fib(n):
    if n==0:
        return 0
    if n==1:
        return 1
    return fib(n-2) + fib(n-1)

Bovenstaande variatie is nu in staat om zelfs fib(1000) binnen enkele ogenblikken op je scherm te toveren (een reusachtig getal van 209 cijfers). Wat hier gebeurt is dat er gebruik is gemaakt van zogenaamde memoization van de fib functie. Memoization is een vaak toegepaste vorm van dynamic programming. In dit voorbeeld gebruik je een tabel (cache) om tussentijdse resultaten in op te slaan zodat je die later niet nog een keer helemaal hoeft te berekenen. In Python is het een oneliner omdat de lru_cache decorator de fib functie zodanig aanpast dat er een transparante wrapper omheen komt te zitten die resultaten in een lru-cache bewaart. Je kunt het ook zelf uitprogrammeren in een handvol regels maar de kans is groot dat je dan te maken krijgt met een cache zonder maximum grootte en dat is niet zo'n goede eigenschap als je in een long running process (server) zit. De lru_cache decorator is onderdeel van de standard library en dus: gebruik 'm!

Bottom line: met 1 regel code is een functie die aanvankelijk al bij kleine getallen geen resultaten meer kan opleveren (in acceptabele tijd) omgetoverd tot eentje die dynamic programming toepast om het in enkele milliseconden te klaren. Zonder dat we ook maar één regel code in de functie zelf aan hoefden te passen.

Alternatieve oplossing: bottom-up

Bovenstaande was interessant (en vaak al voldoende!) maar voor dit specifieke probleem (fibonacci getallen) zijn nog wel betere oplossingen te verzinnen. Een slimme implementatie van het algoritme werkt niet top-down (wat we hierboven deden met de recursieve functie), maar bottom-up: bereken eerst de kleine getallen in de reeks en bouw daarop voort om de grotere getallen te bepalen. Een implementatie daarvan staat hieronder. Er bestaat zelfs een O(1) wiskundige formule waarmee in 1 stap een bepaald getal uit de reeks berekend kan worden. Maar dat is vals spelen ;-)

def fib(n):
    if n==0:
        return 0
    prev,cur = 0,1
    for i in range(n-1):
        prev,cur = cur,prev+cur
    return cur

(ondanks dat het niet de O(1) formule is, is deze iteratieve variant toch in staat om binnen een fractie van een seconde fib(10000) te bepalen, een getal van 2090 cijfers)

En voor de volledigheid de generator die een oneindige lijst fibonacci getallen kan genereren:

def fibs():
    prev,cur = 0,1
    while True:
        yield prev
        prev,cur = cur,prev+cur