O listama i o rekurziji
Baratanje listama
Pridruživanje i kopiranje lista
Pridruživanjem liste novoj varijabli, ta varijabla postaje samo drugi naziv iste liste:
[1, 2.00000000000000, 'tri', 3/2, 'zadnji element'] [1, 2.00000000000000, 'tri', 3/2, 'zadnji element'] [1, 2.00000000000000, 'tri', 3/2, 'zadnji element'] [1, 2.00000000000000, 'tri', 3/2, 'zadnji element'] |
[1, 2.00000000000000, 300, 3/2, 'zadnji element'] [1, 2.00000000000000, 300, 3/2, 'zadnji element'] |
... rekosmo, samo drugi naziv:
[1, 2.00000000000000, 300, 3/2, 'zadnji element'] [1, 2.00000000000000, 300, 3/2, 'zadnji element'] |
Nova se lista—istoga sadržaja—dobiva kopiranjem:
[1, 2.00000000000000, 300, 3/2, 'zadnji element'] [1, 2.00000000000000, 300, 3/2, 'zadnji element'] |
[1, 2.00000000000000, 300, 3/2, 'zadnji element'] [1, 2.00000000000000, 300, 3/2, 'zadnji element'] [1, 2.00000000000000, 300, 3.1415926535897932385, 'zadnji element'] [1, 2.00000000000000, 300, 3/2, 'zadnji element'] [1, 2.00000000000000, 300, 3/2, 'zadnji element'] [1, 2.00000000000000, 300, 3.1415926535897932385, 'zadnji element'] |
Za ugniježđene liste treba upotrijebiti funkciju deepcopy():
[1, 2.00000000000000, 'a', 3/2, 'zadnji element'] [1, 2.00000000000000, 'a', 3/2, 'zadnji element'] |
[1, 2.00000000000000, 'tri', 3/2, 'zadnji element'] [1, 2.00000000000000, 'tri', 3/2, 'zadnji element'] [1, 2.00000000000000, 'tri', 3/2, 'zadnji element'] [1, 2.00000000000000, 'tri', 3/2, 'zadnji element'] |
[1, 2.00000000000000, 'tri', 3/2, 'zadnji element'] [1, 2.00000000000000, 'tri', 3/2, 'zadnji element'] [1, 2.00000000000000, 'tri', 3/2, 'pet'] [1, 2.00000000000000, 'tri', 3/2, 'zadnji element'] [1, 2.00000000000000, 'tri', 3/2, 'zadnji element'] [1, 2.00000000000000, 'tri', 3/2, 'pet'] |
Tvorba lista i dodavanje komponenata
.append() — dodavanje komponente na kraj liste:
0 [] 1 [1] 2 [1, 8] 3 [1, 8, 27] 4 [1, 8, 27, 64] 5 [1, 8, 27, 64, 125] 6 [1, 8, 27, 64, 125, 216] 0 [] 1 [1] 2 [1, 8] 3 [1, 8, 27] 4 [1, 8, 27, 64] 5 [1, 8, 27, 64, 125] 6 [1, 8, 27, 64, 125, 216] |
[1, 8, 27, 64, 125, 216] [1, 8, 27, 64, 125, 216] |
sažeta tvorba liste (list comprehension):
[1, 8, 27, 64, 125, 216] [1, 8, 27, 64, 125, 216] |
[13, 13, 13, 13, 13, 13, 13, 13, 13, 13] [13, 13, 13, 13, 13, 13, 13, 13, 13, 13] |
|
[0, 2, 4, 6, 8] [0, 2, 4, 6, 8] |
.extend() — dodavanje liste na kraj liste:
[1, 8, 27, 64, 125, 216] [1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, 1331, 1728] [1, 8, 27, 64, 125, 216] [1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, 1331, 1728] |
[1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, 1331, 1728, 2197, 2744, 3375, 4096] [1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, 1331, 1728, 2197, 2744, 3375, 4096] |
[-64, -27, -8, -1, 0, 1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, 1331, 1728, 2197, 2744, 3375, 4096] [-64, -27, -8, -1, 0, 1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, 1331, 1728, 2197, 2744, 3375, 4096] |
... pribrojnici se pritom ne mijenjaju:
[1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, 1331, 1728, 2197, 2744, 3375, 4096] [1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, 1331, 1728, 2197, 2744, 3375, 4096] |
.insert() — umetanje komponente na određeno mjesto u listi:
[-1, 1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, 1331, 1728, 2197, 2744, 3375, 4096] [-1, 1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, 1331, 1728, 2197, 2744, 3375, 4096] |
.pop() — uklanjanje komponente s određenoga mjesta u listi:
27 27 |
[-1, 1, 8, 64, 125, 216, 343, 512, 729, 1000, 1331, 1728, 2197, 2744, 3375, 4096] [-1, 1, 8, 64, 125, 216, 343, 512, 729, 1000, 1331, 1728, 2197, 2744, 3375, 4096] |
Funkcije map(), reduce() i filter()
Funkcija map()
... ako je f funkcija jedne varijable, a lista l ima komponente l0,l1,…,ln−1, rezultat poziva map (f, l) nova je lista [f(l0),f(l1),…,f(ln−1)].
[1, 2, 3, 4, 5, 6, 7, 8, 9] [1, 2, 3, 4, 5, 6, 7, 8, 9] |
|
[1, 8, 27, 64, 125, 216, 343, 512, 729] [1, 8, 27, 64, 125, 216, 343, 512, 729] |
... isto, primjenom petlje for:
[1, 8, 27, 64, 125, 216, 343, 512, 729] [1, 8, 27, 64, 125, 216, 343, 512, 729] |
... isto, primjenom sažete tvorbe liste:
[1, 8, 27, 64, 125, 216, 343, 512, 729] [1, 8, 27, 64, 125, 216, 343, 512, 729] |
... štoviše:
[1, 8, 27, 64, 125, 216, 343, 512, 729] [1, 8, 27, 64, 125, 216, 343, 512, 729] |
Neimenove funkcije (lambda–funkcije)
<function <lambda> at 0x7f94ac22d5f0> <function <lambda> at 0x7f94ac22d5f0> |
27 27 |
5 5 |
map() i lambda
[1, 8, 27, 64, 125, 216, 343, 512, 729] [1, 8, 27, 64, 125, 216, 343, 512, 729] |
[13, 13, 13, 13, 13, 13, 13, 13, 13] [13, 13, 13, 13, 13, 13, 13, 13, 13] |
Ako je f funkcija dviju varijabli i ako su a=[a0,a1,…,an−1] i b=[b0,b1,…,bn−1] dvije liste s jednakim brojem komponenata, onda je rezultat poziva map (f, a, b) lista [f(a0,b0),f(a1,b1),…,f(an−1,bn−1)].
[10, 10, 10, 10, 10, 10, 10, 10, 10] [10, 10, 10, 10, 10, 10, 10, 10, 10] |
... isto, primjenom petlje:
[1, 2, 3, 4, 5, 6, 7, 8, 9] [9, 8, 7, 6, 5, 4, 3, 2, 1] [10, 10, 10, 10, 10, 10, 10, 10, 10] [1, 2, 3, 4, 5, 6, 7, 8, 9] [9, 8, 7, 6, 5, 4, 3, 2, 1] [10, 10, 10, 10, 10, 10, 10, 10, 10] |
[0, -7/9, -11/4, -45/7, -38/3, -23, -81/2, -217/3, -140] [0, -7/9, -11/4, -45/7, -38/3, -23, -81/2, -217/3, -140] |
(Domaća zadaća: napišite funkciju something() primjenom sažetih tvorbi lista i primjenom petlji for :o)
Funkcija reduce()
... umjesto petlje
45 45 |
... to jest
... možemo primijeniti funkciju
45 45 |
... općenito, neka su f funkcija dviju varijabli, l=[l0,l1,…,ln−1] i x0 broj; rezultat r poziva reduce (f, l, x0) izračunava se na sljedeći način:
Duljina vektora v: v=‖v‖=√n−1∑i=0v2i
|
25 25 |
(7, 24) (7, 24) |
25 25 |
25 25 |
Drugi oblik poziva funkcije reduce() — bez trećega parametra:
45 45 |
... što je, primjenom petlje,
45 45 |
... dakle, za funkciju f dviju varijabli i l=[l0,l1,…,ln−1], rezultat r poziva reduce (f, l) izračunava se na sljedeći način:
Skalarni umnožak vektora u i v: s=u⋅v=n−1∑i=0uivi
|
(1, 2, -11, 3/2, 6, -1/2, 5, 1/2, 0, 2) (2/3, 0, -11, -1, -1, 1, -2/3, 4, 0, -15/2) (1, 2, -11, 3/2, 6, -1/2, 5, 1/2, 0, 2) (2/3, 0, -11, -1, -1, 1, -2/3, 4, 0, -15/2) |
292/3 292/3 |
292/3 292/3 |
292/3 292/3 |
Funkcija filter()
... ako su p relacijska ili logička funkcija (takozvani predikat — funkcija čije su vrijednosti True ili False) i l lista, onda je rezultat poziva filter (p, l) nova lista koja sadrži one komponente li liste l za koje je p(li)= True.
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19] [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] |
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19] [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] |
... isto, primjenom petlje:
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19] [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] |
... isto, primjenom sažete tvorbe liste:
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19] [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] |
Rekurzivne funkcije
Neformalno, funkcija koja poziva samu sebe naziva se rekurzivnom funkcijom.
Strože i potpunije, definicija rekurzivne funkcije sastavljena je od dva dijela:
Izračunavanje cjelobrojne potencije
„Naivni” algoritam
n>0
xn=x×x×⋯×x⏟n−1puta
složenost algoritma: O(n) množenja
Rješenje pomoću petlje
|
8 8 |
81 81 |
-524288 -524288 |
95367431640625 95367431640625 |
Rješenje pomoću rekurzije
rekurzivni dio: xn=x×xn−1
temeljni dio: x1=x
|
8 8 |
81 81 |
-524288 -524288 |
95367431640625 95367431640625 |
Učinkovitiji algoritam
nparan:xn=x2n/2=xn/2×xn/2=(xn/2)2n/2paran:xn=x2⋅2⋅n/4=(xn/4×xn/4)×(xn/4×xn/4)=(xn/4)2×(xn/4)2=((xn/4)2)2n=2k:xn=x2k=(⋯(x2)2⋯)2⏟kputaxnneparan:xn=x×(x(n−1)/2)2
složenost algoritma: O(log2n) množenja/kvadriranja
|
8 8 |
81 81 |
-524288 -524288 |
95367431640625 95367431640625 |
4 4 |
4 4 |
... i još neke sitnice
n=0
x≠0:x0=1x=0:nedefinirano∗
∗ hmm ... prisjetite se napomene u predavanju 11.
n<0
n=−m za m>0, pa je xn=x−m=1xm=(1x)m
|
1 1 |
NaN NaN |
1/524288 1/524288 |
1.90734863281250e-6 1.90734863281250e-6 |
1/95367431640625 1/95367431640625 |
1.04857600000000e-14 1.04857600000000e-14 |
|