Forum: Python Fibonacci

Forum huvudsida -> Programmering -> Python Fibonacci

Sidor: 1

Till botten

Osthus 22:41 - 27:e Juni 2009 | Post #1
Medlem
Inlägg: 7


Skicka PM 		Hej!

Jag håller på och programmerar i Python, och nu håller jag på med rekursiva funktioner. Enklare rekursiva funktioner förstår jag, som t.ex:

def factorial(n):
if n == 0:
return 1
else:
return n
  • factorial(n-1)

Men jag förstår verkligen inte hur man tänka i fibonacci funktionen.

def fibonacci(n):
    if n == 0 or n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

Det är ju ett annorlunda tänk när det är två funktionskall direkt på varandra.
Skulle vara tacksam om någon förklarade hur det fungerade.


ozamosi 00:49 - 28:e Juni 2009 | Post #2
Administratör
Inlägg: 1129


Skicka PM 		Ur prestandasynpunkt är den fibonacci-funktionen Helt Horribel. Men frånsett detEUR

Funktionell programmering betyder, på någon slags flumromantisk nivå, att man skriver regler istället för instruktioner. Fibonacci-tal tas fram genom att man tar summan av de tidigare talen, med specialfallet att serien börjar med två ettor (eller en etta och en tvåa, beroende på implementation). Det går alltså att skriva på följande vis:

fibonacci (0) = 1
fibonacci (1) = 1
fibonacci (2) = fibonacci (1) + fibonacci (0)
fibonacci (3) = fibonacci (2) + fibonacci (1)
fibonacci (4) = fibonacci (3) + fibonacci (2)
...
fibonacci (n) = fibonacci (n - 1) + fibonacci (n - 2)

Det går att se i ovastående "tabell" att fibonacci (4) kan, i flera steg, skrivas om som en summa av massor med ettor, vilket är vad din kod gör. På samma sätt kan fibonacci-talet för samtliga positioner tas fram.

-------------------------
Ljusblå


Osthus 01:23 - 28:e Juni 2009 | Post #3
Medlem
Inlägg: 7


Skicka PM 		Tack för så snabbt svar! Jag tror att jag förstår nu. =) Men varför är den dålig ur prestanda synvinkel? Vad för funktion bör man använda istället?


ozamosi 03:30 - 28:e Juni 2009 | Post #4
Administratör
Inlägg: 1129


Skicka PM 		Jag skapar följande fibonacci2:
  1. def fibonacci(n):
  2.     a, b = 1, 1
  3.     while (n > 1):
  4.         a, b = b, a + b
  5.         n -= 1
  6.     return b

Det här är den första versionen jag skrev, och det är säkert möjligt att göra ytterligare småförbättringar på den, men eftersom jag bara vill peka på algoritmisk prestanda skiter jag i det.

Koden är inte rekursiv, utan iterativ. Den skapar två temporära variabler, a och b, i vilka de första talen i talserien lagras. Sedan kör jag en loop, och för varje varv stoppar jag det nuvarande talet i a, och nästa tal i b. När n nått 1 har vi kört rätt antal varv, så då returneras b.

Sedan mäter jag lite. Jag bestämde mig för att ta min variant och testa för varje tiopotens, tills det börjar ta "lagom" med tid. Jag valde sedan tal i den funktionella varianten sådana att de ungefär matchade min iterativa variant. Följande kod är ful, men fungerar för mina syften:
  1. fibonacci1 = '''
  2. def fibonacci(n):
  3.     if n == 0 or n == 1:
  4.         return 1
  5.     else:
  6.         return fibonacci(n-1) + fibonacci(n-2)
  7. '''
  8. fibonacci2 = '''
  9. def fibonacci(n):
  10.     a, b = 1, 1
  11.     while (n > 1):
  12.         a, b = b, a + b
  13.         n -= 1
  14.     return b
  15. '''
  16.  
  17. import timeit
  18.  
  19. def do_timeit (iterative, functional):
  20.     t1 = timeit.Timer (stmt='fibonacci(%i)' % (iterative,), setup=fibonacci2)
  21.     t2 = timeit.Timer (stmt='fibonacci(%i)' % (functional,), setup=fibonacci1)
  22.     print "Iterative (%i): %f, functional (%i): %f" % \
  23.         (iterative, t1.timeit (number=1), functional, t2.timeit (number=1),)
  24.  
  25. do_timeit (1, 1)
  26. do_timeit (10, 4)
  27. do_timeit (100, 9)
  28. do_timeit (1000, 14)
  29. do_timeit (10000, 22)
  30. do_timeit (100000, 30)

Modulen timeit gör vad namnet antyder: den tar tid på kod. Först sparar jag sträng-motsvarigheter till funktionerna. Jag skickar dessa till setup-argumentet till Timer-konstruktorn, så att koden finns tillgänglig i timeit-miljön. Sedan skickar jag ett anrop till koden setup-argumentet genererade som det argumentet som ska benchmarkas. På sista rraden i do_timeit-funktionen genomför jag den faktiska körningen av koden, och skriver ut resultatet.

Eftersom jag för varje körning bara kör varje test en gång (number=1 till timeit-funktionen) varierar testen lite beroende på körning: beroende på vad datorn pysslade med i övrigt kan den iterativa eller den funktionella varianten vara lite före, men oftast ligger de ungefär lika. Jag bestämde mig för att värdera sömn över att sitta och vänta på att datorn kör samma kod om och om igen.

Jag får det här resultatet:
  1. Iterative (1): 0.000006, functional (1): 0.000004
  2. Iterative (10): 0.000012, functional (4): 0.000013
  3. Iterative (100): 0.000096, functional (9): 0.000116
  4. Iterative (1000): 0.001093, functional (14): 0.001256
  5. Iterative (10000): 0.022836, functional (22): 0.028970
  6. Iterative (100000): 1.252999, functional (30): 1.365112

Tidsenheten är sekunder.

Problemet med den funktionella koden är att varje gång den anropas, anropar den sig själv två gånger, och det tar därmed i krokarna av dubbelt så lång tid att räkna ut ett visst tal, som det tog att räkna ut talet innan (tar det en sekund att räkna ut tal n och en halv sekund att räkna ut tal n-1 tar n+1 en och en halv sekund, och n+2 två och en halv sekund)

Den gör det dessutom på ett korkat sätt: för att räkna ut t ex functional (5), måste räkna ut functional (4) och functional (3). Och för att räkna ut functional (4) måste den räkna ut functional (3) igen. Dessutom måste den räkna ut functional (2), som också måste räknas ut för att få fram functional (3) EUR" som alltså räknas ut två gångerEUR Samma funktion med samma argument körs alltså om och om igen.

Funktionen jag skrev räknar bara ut alla tal 1 gång. Tidsskillnaden mellan att räkna ut tal 3 och tal 2 är lika stor som tidsskillnaden mellan att räkna ut tal 100 000 och tal 100 001: ett varv i loopen (i teorin iaf EUR" efter en stund blir talen Väldigt Stora, och då blir additionerna långsammare, så då börjar loopen gå långsammare. Det 100 000:e talet är trots allt 20 899 siffror långt).

Slutsatsen du ska dra är inte att funktionell programmering är långsamt. Slutsatsen du ska dra är att fibonacci-serien är ett dåligt exempel på när man behöver funktionell programmering, vilket gör det lite underhållande att det oftast används som ett standardexempel på när funktionell programmering är bra.

Skälet till att jag alls nämnde det här är att jag nyligen läste en artikel som tog upp just det här.

-------------------------
Ljusblå

Senast redigerad 10:17 - 28:e Juni 2009


Osthus 13:52 - 28:e Juni 2009 | Post #5
Medlem
Inlägg: 7


Skicka PM 		Det var nästan lite för tungt att plöja igenomSmiley Tack ändå!


Sidor: 1

Forum huvudsida -> Programmering -> Python Fibonacci
Atom feed

Du får inte posta i den här tråden | Till toppen