Rekurzív és egyéb algoritmusok

Dinamikus programozás

Két fontos gondolat a rekurzióról.

rekurzió: ld.rekurzió

"Ahhoz, hogy megértsük a rekurziót, először meg kell értenünk a rekurziót."

A faktoriális, még egyszer

Ezt már ismerjük előző félébvől, de nem árt átismételni.

In [34]:
def factorial(n):
    if n <= 1:
        return 1
    else:
        return n * factorial(n-1)
print factorial(10)    
3628800

Fibonacci-sorozat

A rekurzió egy változata. A Fibonacci számokat fogjuk kiszámolni. Ha szeretnénk megmérni, hogy pontosan mennyi ideig tart egy lépés, a time modul van segítségünkre. A time.time() hívás az aktuális időt adja vissza, tehát ha lekérjük a hívás előtt és után, akkor (elég pontosan, kvantummechanika, ugye) megkapjuk a köztük eltelt időt a kettő különbségeként. Még egy érdekes adalék: a fibonacci.counter a fibonacci-nak mint függvényobjektumnak a tagváltozója. Minden egyes hváskor megnöveljük a változót, azaz megszámoljuk vele a függvényhívások számát. Ez sok esetben triviális, rekurzív függvények esetén viszont egyáltalán nem az.

In [45]:
import time
def fibonacci(n):
    fibonacci.counter += 1
    if n <= 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)
fibonacci.counter = 0    
start = time.time()
print fibonacci(35)
print time.time() - start
print fibonacci.counter
14930352
9.43899989128
29860703

Ez így rettenetesen lassú, a századik Fibonacci-számot ki sem merem számoni ezzel a függvénnyel. Inkább úgy oldjuk meg, hogy fokozatosan felépítjük a listát. Kezdem az [1,1] listával, a nulladik és az első Fibonacci számmal. Amíg a lista n+1 hosszú nem lesz, mindig hozzáadom az utolsó két elemének az összegét.

In [36]:
import time
def fibonacci(n):
    f = [1,1]
    for i in range(n-1):
        f.append(f[-1] + f[-2])
    return f[-1]    
start = time.time()
print fibonacci(1000)
print time.time() - start
70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501
0.00100016593933

Sejtettük, hogy gyorsabb.

Partíciók

Mire jó még a rekurzió? Először is matematikailag érdekes (?) kérdéseket is ki lehet számolni. Pl. hányféleképp bontható fel egy pozitív egész szám pozitív egészek összegére, ha az összeadandók sorrendje is számít? Figyeljük meg, hogyan is működik egy jól nevelt rekurzív függvény:

  • Először mindig a megállási feltételt írjuk meg, azaz az egyszerű esetet. A feladat szempontjából most ez az n=0, illetve az n=1
  • Figyeljünk, hogy mivel térünk vissza! A sums most listák listájával, az n pozitív egész összes partíciójával tér vissza. Egy lista az összeadandókat tartalmazza egy rögzített sorrendben.

Az ötlet a követlező: mivel számít a sorrend, legyen az első elem i (i megy n-től 1-ig). Ezután pedig elég legenerálni az n-i összes partícióját és konkatenálni az egyelemű [i] listával egyenként.

In [37]:
def sums(n):
    if n == 0:
        return [[]]
    if n == 1:
        return [[1]]
    else:
        sumlist = []
        for i in range(1,n+1):
            L = [i]
            for l in sums(n-i):
                sumlist.append(L + l)
    return sumlist
for s in sums(4):
    print " + ".join(str(x) for x in s)
1 + 1 + 1 + 1
1 + 1 + 2
1 + 2 + 1
1 + 3
2 + 1 + 1
2 + 2
3 + 1
4

Vajon mi a helyzet akkor, ha a sorrend nem számít? Talán egy házi feladatban még visszatérünk a kérdésre.

Keresés

Lineáris keresés

Generáljunk először egy nagy listát véletlen számokkal!

In [38]:
import random
L = [random.randint(0, 10000000) for i in range(10000000)]
print L[:100]
L[-1]
[139543, 8709661, 977229, 3441983, 5537456, 6568002, 4648961, 7580713, 2608001, 3602605, 4294864, 8862449, 4700388, 9290723, 5092708, 1108981, 9889492, 8124260, 1800677, 2345387, 2793870, 7114859, 1536912, 9423730, 8721820, 7921116, 710659, 6090382, 4048499, 6158247, 4444187, 7296173, 1043954, 6482026, 6657593, 5803184, 6071535, 2390768, 1585207, 9644166, 2701576, 9766559, 5948554, 9528499, 7182543, 8806202, 8585234, 8831679, 9572698, 5262664, 237257, 1575729, 6754777, 4882371, 428683, 6387879, 3082242, 2475444, 1158106, 9307583, 7218511, 7187005, 2408485, 534905, 5966190, 4175848, 5559586, 5692565, 3955135, 4666019, 2598106, 4410880, 2023263, 3038191, 125163, 540577, 145958, 8655639, 7531506, 1540174, 5976822, 5614196, 4395780, 1454305, 3712706, 6478866, 548288, 2046901, 2360962, 8079977, 2818662, 3915748, 2677504, 2169761, 4839702, 6066211, 5280183, 418155, 5745620, 7398424]
Out[38]:
3718110

Keressünk meg benne egy elemet, írjuk ki, hogy hanyadik a sorban, de ne használjuk az in kifeejezést!

In [39]:
import time
start = time.time()
for i in range(len(L)):
    if L[i] == 1:
        print i
        break
end = time.time()
print end - start
412411
2.56100010872

Természetesen ennél gyorsabb lehetőség nincs. Kivéve, ha a listánk rendezett. Az ötlet a következő. Először megnézzük, hogy nagyobb-e, mint a középső elem. Ha igen, akkor a lista felső felében kell keresnünk, ha nem, az alsóban. Ismételgetve az előző lépést, a lista hosszát felezgetve, gyorsan eljutunk a keresett számig.

In [40]:
L = sorted(L)
In [41]:
import time
a = 0
b = len(L)
num = 940048
start = time.time()
while b > a + 1:
    if num < L[(a+b) / 2]:
        b = (a+b)/2
    else:
        a = (a+b)/2
end = time.time()
print L[a:b]
print end - start
[940048]
0.00200009346008

Az aktuális lista mindig az L[a:b], így akkor kell megállnunk, mikor b > a + 1. Természetesen ez sincs ingyen, bár látjuk, hogy mennyivel gyorsabb, ugyanis a listát rendezve kell tárolni, a rendezés pedig sok idő.

Listák rendezése

A biztos módszer, ha a Pythonra bízzuk, illetve tanultuk már a buborékrendezést. A bináris kereséshez hasonló a quicksort, vagy gyorsrendezés. Ez tényleg gyors az esetek jelentős részében (norvég tudósok vizsgálták már, hogy van-e az eseteknek jelentős része; arra jutottak, hogy az esetek jelentős részében van). Ugyanakkor nem tudjuk teljesen kontrollálni.

Vesszük a rendezetlen lista egyik elemét, mondjuk az elsőt. A listát szétbontjuk két részre: azokra, akik kisebbek a kiválasztott elemnél, illetve azokra, akik nem, majd ismételjük a lépést (rekurzió, ismét). Ha a lista egyelemű vagy üres, akkor egyszerűen visszaadjuk. A visszaadott listákat összafűzzük.

In [42]:
import random, time
L = [random.randint(0, 10000000) for i in range(1000000)]

def qsort(l):
    if len(l) <= 1:
        return l
    e = l[0]
    lesser = []
    greater = []
    for i in l[1:]:
        if i < e:
            lesser.append(i)
        else:
            greater.append(i)      
    return qsort(lesser) + [e] + qsort(greater)    
start = time.time()
L = qsort(L)
end = time.time()
print end - start
9.21799993515

Vajon hogyan függ a futásidő a lista hosszától?

In [43]:
import random, time, math
L = [random.randint(0, 10000000) for i in range(1000000)]
start = time.time()
qsort(L[:10000])
print (time.time() - start) / math.log(10000) /10000
qsort(L[:100000])
print (time.time() - start) / math.log(100000) / 100000
qsort(L[:1000000])
print (time.time() - start) / math.log(1000000) / 1000000
5.97153048827e-07
7.217972997e-07
7.86652073763e-07

Látjuk, hogy az algoritmusunk nagyjából $n\log(n)$ ideig fut. Ez helytálló, de természetesen nem garantált. A lépésszámot $O(f(n))$-nel szoktuk jelölni.

Algoritmusokról és hatékonyságukról bővebben az Algoritmuselmélet tárgyban lesz szó.

Állapotgépek

Egy klasszikus probléma: olvassunk be egy szöveget karakterenként, majd számoljuk meg benne az ly betűket. Figyelembe kell vennünk a dupla, lly betűt is, pl. a gally szóban.

Megoldás. Definiálunk egy s állapotot, ami alaphelyzetben 0, viselkedése pedig a következő. Ha

  • a következő betű l és s=0, akkor s=1;
  • a következő betű l és s=1, akkor s=2;
  • a következő betű y és s=1 vagy s=2, akkor megjegyezzük, hogy találtunk egyet és s=0;
  • minden egyéb esetben s=0
In [44]:
sample="gally lyuk alma folyam"
s = 0
counter = 0
for i in sample:
    if i == 'l':
        if s <= 1:
            s += 1
        else:
            s = 0
    elif i == 'y' and (s == 1 or s == 2):
        counter += 1
        s = 0
print counter    
3

Az állapotgép gyakorlatilag egy véges automata, legalábbis a matematikusok így hívják. A gép következő állapota függ az aktuális állapottól (s) és a bemenettől (ez a következő betű).

Alapvetően állapotgépeket szövegfelismerésre használnak, pl. a Python fordítója is egy ilyen állapotgép, persze sokkal bonyolultabb.

In [ ]: