3.1. Liste i drugi spremnici

3.1.1. Liste

Liste su središnji objekti programiranja u Sageu i Pythonu. Srodne su poljima (array) iz standardnih programskih jezika (C, Fortran), ali imaju bitno više svojstava. Elementi lista mogu biti praktički bilo koji objekti.

sage: t1 = [1, 3, 5, 7, 9, 11]; t1
[1, 3, 5, 7, 9, 11]
sage: t2 = [sin, cos, tan]; t2
[sin, cos, tan]
sage: t3 = [[], ["jedan"], t1]; t3
[[], ['jedan'], [1, 3, 5, 7, 9, 11]]

Liste se mogu npr. zbrajati, množiti i mjeriti im se duljina:

sage: print t1+t2
[1, 3, 5, 7, 9, 11, sin, cos, tan]
sage: 7*[3]
[3, 3, 3, 3, 3, 3, 3]
sage: print len(t1)
6

Kako je Python objektno orijentirani računalni jezik, mnoge operacije se izvode putem tzv. metoda objekta, a to su objektu pridružene funkcije koje se pozivaju sintaksom objekt.metoda(). I liste su objekti pa imaju niz metoda (vidi popis), od kojih je daleko najvažnija metoda append() koja služi za dodavanje elemenata na kraj liste:

sage: t1.append(13); t1
[1, 3, 5, 7, 9, 11, 13]

Pojedinim elementima liste se pristupa pomoću indeksiranja, gdje prvi element liste ima indeks 0, drugi ima indeks 1 itd. Pojedine elemente možemo promijeniti običnim pridruživanjem pomoću znaka jednakosti:

sage: t1[1] = "tri"
sage: print t1
[1, 'tri', 5, 7, 9, 11, 13]

Ukoliko želimo pristupiti većem broju elemenata od koristi su tzv. rezovi liste (engl. slice). Općenita sintaksa reza je lista[početak:kraj:korak], gdje je početak uključen u rez, a kraj nije:

sage: t1[2:6]
[5, 7, 9, 11]
sage: t1[2:6:2]
[5, 9]

Ukoliko rez ide od samog početka ili sasvim do kraja liste, odgovarajuće indekse možemo izostaviti:

sage: t1[2:]
[5, 7, 9, 11, 13]

Negativni indeksi nam omogućuju da brojimo od kraja liste ...

sage: t1[-2:]   # zadnja dva elementa
[11, 13]

... a negativan korak da rez ide unatrag tj. da se izvrne redosljed elemenata:

sage: t1[::-1]  # lista natraške
[13, 11, 9, 7, 5, 'tri', 1]

Zadatak 1

Promijenite u gornjoj listi t1 element "tri" (ne element s indeksom=3!) natrag u broj 3, ali ne eksplicitnom upotrebom indeksa 1, već tako da “pronađete” indeks elementa "tri"``pomoću metode ``index(). (Nije dozvoljeno upotrijebiti znamenku 1).

Za konstrukciju liste cijelih brojeva, vrlo je korisna funkcija range(početak, kraj, korak) gdje treba imati na umu da će konstruirana lista početi s elementom početak, ali će završiti s elementom kraj-1.

sage: range(3)  # rezultira listom od tri elementa
[0, 1, 2]

Za konstrukciju liste realnih brojeva, vidi dolje odjeljak NumPy polja.

3.1.2. Obuhvaćanje liste

U praksi je kirurško mijenjanje pojedinih elemenata liste, kao u gornjem zadatku, vrlo rijetko. Listama se u pravilu rukuje kao cjelinama i najčešće se djeluje na sve njihove elemente. U standardnim računalnim jezicima u tu svrhu se koriste petlje, ali u Pythonu je najelegantnije koristiti tzv. obuhvaćanje liste (engl. list comprehension ):

sage: [n+1 for n in t1]
[2, 4, 6, 8, 10, 12, 14]

Kombiniranjem obuhvaćanja liste s funkcijom range() možemo konstruirati najrazličitije liste. Npr. lista od pet slučajnih brojeva se može konstruirati ovako:

sage: [random() for k in range(5)]
[0.24117853317222127, 0.4504912135031752, 0.28942549153153674,
     0.86208567873778, 0.09328097538429081]

Često se javlja potreba za izborom elemenata liste koji zadovoljavaju neki kriterij. To se može izvesti obuhvaćanjem liste uz dodatni uvijet:

sage: t5 = range(1, 11)
sage: [n for n in t5 if is_even(n)]    # izbor parnih elemenata
[2, 4, 6, 8, 10]

Ovdje smo koristili funkciju is_even() koje je jedna iz velike porodice tzv. predikata. Predikat je termin iz matematičke logike koji označava funkciju koja poprima isključivo vrijednosti True ili False. Većina predikata definiranih u Sageu počinje s is_ (jer odgovaraju na pitanje “da li je ...”). Ispišimo ih (Koristimo prvo funkciju dir() koja ispisuje imena svih trenutno poznatih objekata i, drugo, to da su stringovi kao liste znakova pa možemo koristiti rezove na njima):

sage: [p for p in dir() if p[:3]=='is_']
['is_2_adic_genus', 'is_32_bit', 'is_64_bit', 'is_AbelianGroup',
'is_AbelianGroupElement', 'is_AbelianGroupMorphism',
         <... odrezan ispis ...>
'is_odd', 'is_optimal_id', 'is_pAdicField', 'is_pAdicRing',
'is_package_installed', 'is_power_of_two', 'is_prime', 'is_prime_power',
'is_pseudoprime', 'is_square', 'is_squarefree', 'is_triangular_number']

Zadatak 2

Konstruirajte listu svih prim-brojeva manjih od 100. Koliko ima prim-brojeva manjih od \(10^4, 10^5, 10^6, \ldots\)? Usporedite rezultate (i brzinu njegovog dobivanja) s ugrađenom funkcijom prime_pi().

Napomena

Mjerenje vremena potrebnog da se izvrši neka ćelija izvodi se stavljanjem %time u prvi red, a prekid računa koji traje predugo izvodi se putem izbornika Action pa Interrupt ili pritiskom na tipku Escape.

%time
sage: factor(2923003274661805836407421649242809468366377451741)
1208925819614629174706189 * 2417851639229258349412369
CPU time: 2.80 s,  Wall time: 2.94 s

Zadatak 3

Izračunajte funkciju \(\pi(x)\) (broj prim-brojeva manjih od x) za \(x=10^{10}\) statističkom metodom: Izaberite uzorak od n slučajnih cijelih brojeva između 1 i x i testirajte koliko ima prim-brojeva među njima. Iz tog udjela odredite \(\pi(x)\). Kolika veličina uzorka vam treba da bi relativna greška prema prime_pi(10^10) razumno često pala ispod 1%?

Zadatak 4

Kreirajte listu od 100 slučajnih brojeva iz intervala [0, 10), a zatim u toj listi ostavite samo brojeve koji se za manje od 0.02 razlikuju od cijelog broja. Naputak: Testirajte abs(x-round(x)).

3.1.3. Ostali spremnici

Osim lista, postoje i drugi spremnici (containers) za objekte. Kao prvo tu su tzv tuplovi (tuple) koji “izvana” izgledaju isto kao liste samo u okruglim zagradama.

sage: tpl = (1, 3, 5, 7)
sage: tpl[3]
7

Glavna razlika prema listama je da su tuplovi nepromjenjivi. Nije moguće niti promijeniti neki njihov element niti im dodati nove:

sage: tpl[3] = 2
Traceback (most recent call last):
...
TypeError: 'tuple' object does not support item assignment

Razlika u upotrebi između tuplova i lista je da su tuplovi obično heterogeni strukturirani skupovi u kojima pojedina mjesta u tuplu nose različita značenja, dok su liste obično homogeni skupovi istovrsnih objekata. Npr, koordinate neke točke je prirodno staviti u tupl (x, y), a ne u listu [x,y], ali niz točaka je prirodno staviti u listu takvih tuplova [(x1, y1), (x2, y2), ...].

Kad varijablama pridružujemo vrijednosti iz kraćih lista ili tuplova zgodno je koristiti tehniku raspakiravanja

sage: x, y, z = (1, 2, 3)
sage: print "Norma vektora  = %f" % sqrt(x**2 + y**2 + z**2)
Norma vektora  = 3.741657

Raspakiravanje se često koristi kod procesiranja listi čiji su elementi liste ili tuplovi. U slijedećem primjeru pretvaramo listu 2D kartezijevih vektora u listu njihovih normi. Vidimo kako možemo kombinirati raspakiravanje po unutarnjoj s obuhvaćanjem 2D liste po vanjskoj dimenziji:

sage: [sqrt(x**2 + y**2) for x,y in [(1,2), (3,4), (5,6), (7,8)]]
[sqrt(5), 5, sqrt(61), sqrt(113)]

Zadatak 5

Koristeći raspakiravanje tuplova u kombinaciji s obuhvaćanjem liste pretvorite ovu listu vektora

\[{\rm tt} = [(r_1, \theta_1), (r_2, \theta_2), \ldots ]\]

sage: tt = [(2.23, 1.11), (5.0, 0.93), (7.81, 0.88), (10.63, 0.85)]

iz 2D polarnog sustava u kartezijev:

\[[(x_1, y_1), (x_2, y_2), \ldots ]\]

Nakon toga transformirajte nastalu listu kartezijevih vektora u listu kartezijevih vektora s cjelobrojnim koordinatama, zaokruživanjem vrijednosti x i y koordinata pomoću funkcije round().

Daljnji spremnici koji nam stoje na raspolaganju su skupovi (set ), koji su skupovi različitih(!) objekata i s kojima možemo raditi standardne stvari poput unije, presjeka, komplementa ...

sage: s1 = set([10, 9, 10, 8, 7, 7, 7, 4]); s1
{4, 7, 8, 9, 10}

(Uočite da se duplikati automatski izbacuju.)

sage: s1.union(t1)
{1, 3, 4, 5, 7, 8, 9, 10, 11, 13}
sage: s1.intersection(t1)
{7, 9}
sage: s1.difference(t1)
{4, 8, 10}

Zadnji, vrlo važan, spremnik kojeg ćemo spomenuti je rječnik (engl. dictionary ). Riječ je o preslikavanju key -> value, gdje je value bilo koji objekt, a key može biti tipično broj ili string (premda su i druge stvari dopustive kao key, npr tuplovi).

sage: d1 = {'a':1, 'c':3, 'b':2}; d1
{'a': 1, 'b': 2, 'c': 3}
sage: d2 = {1: sin, 2: cos, 3: tan}; d2
{1: sin, 2: cos, 3: tan}
sage: d3 = {'ime': 'pero', 'prezime': 'peric', 'spol': 'M'}; d3
{'ime': 'pero', 'prezime': 'peric', 'spol': 'M'}

Redosljed elemenata u rječniku nema značenja. Pristup pojedinim elementima rječnika je moguć “indeksiranjem” pomoću ključa:

sage: d1['c']
3

Na isti način je moguće dodavati nove elemente u rječnik:

sage: d2[5] = log

sage: d2.keys()
[1, 2, 3, 5]

Iteriranje po rječniku ne daje elemente već samo ključeve:

sage: [it for it in d2]
[1, 2, 3, 5]

sage: [d2[n](1.) for n in d2.keys()]
[0.841470984807897, 0.540302305868140, 1.55740772465490, 0.000000000000000]

Zadatak 6

Izračunajte (iteriranjem po rječniku, a ne ručno!) prosjek godina ljudi iz slijedećeg rječnika (rezultat treba biti decimalni broj):

sage: ages = {'john' : 74, 'paul': 71, 'george': 71, 'ringo': 73}

Za kraj, i stringove možemo interpretirati kao liste znakova i tretirati ih kao takve

sage: s1 = 'Samobor'
sage: s1[-3:]
'bor'

3.1.4. NumPy polja

Obične liste se rabe za razne namjene, uključujući simboličke račune, ali za numeriku su pogodnija tzv. NumPy polja. NumPy (Numerical Python) je modul za python namjenjen baratanju s multidimenzionalnim brojčanim poljima kakva se često sreću u svim područjima znanosti. Riječ je o velikom modulu koji nije automatski prisutan u Pythonu ili Sageu, već ga treba učitati pomoću naredbe import

sage: import numpy as np

Ovdje se istovremeno s učitavanjem uvodi skraćeno ime np. Svi objekti i funkcije NumPy modula sada su dostupni kao np.<ime objekta>.

Numpy polja su u računalu zapisana u neprekinutom slijedu memorijskih lokacija što omogućuje brži pristup no zbog toga svi elementi polja moraju biti istog tipa (integer, float, complex ...).

sage: a = np.array(range(1,11)); a   # konverzija obične liste u NumPy polje
array([ 1,  2,  3,  4,  5,  6,  7,  8,  9, 10])

Vidimo da je NumPy polje ispisano na drugačiji način nego obična lista, ali za razlikovanje tih dviju objekata izgled ispisa nije pouzdani kriterij. Neke operacije, poput print, ispisuju NumPy polje da izgleda kao obična lista

sage:: print a
[1 2 3 4 5 6 7 8 9 10]

Ako postoji dvojba, možemo ispitati tip objekta komandom type()

sage: type(a)
<type 'numpy.ndarray'>

Pri konstrukciji NumPy polja izbor tipa objekata je automatski, ali moguće ga je i odrediti opcionalnim argumentom dtype:

sage: b = np.array(range(1,11), dtype=np.float64); print b
[  1.   2.   3.   4.   5.   6.   7.   8.   9.  10.]

Tip objekata u NumPy polju je zapisan u dtype atributu polja [1].

sage: a.dtype
dtype('int64')
sage: b.dtype
dtype('float64')

Numpy polja imaju dosta više metoda od običnih lista ...

sage: dir(a)[-66:]
['all', 'any', 'argmax', 'argmin', 'argsort', 'astype', 'base', 'byteswap',
'choose', 'clip', 'compress', 'conj', 'conjugate', 'copy', 'ctypes',
'cumprod', 'cumsum', 'data', 'diagonal', 'dtype', 'dump', 'dumps', 'fill',
'flags', 'flat', 'flatten', 'getfield', 'imag', 'item', 'itemset',
'itemsize', 'max', 'mean', 'min', 'nbytes', 'ndim', 'newbyteorder',
'nonzero', 'prod', 'ptp', 'put', 'ravel', 'real', 'repeat', 'reshape',
'resize', 'round', 'searchsorted', 'setfield', 'setflags', 'shape', 'size',
'sort', 'squeeze', 'std', 'strides', 'sum', 'swapaxes', 'take', 'tofile',
'tolist', 'tostring', 'trace', 'transpose', 'var', 'view']

... no zbog efikasnosti implementacije nema upravo onih metoda koje imaju obične liste. To je zato jer je npr. umetanje elementa u listu vrlo “skupa” operacija koja uključuje brisanje i pisanje svih elemenata koji u memoriji dolaze nakon tog mjesta umetanja. Ako želimo raditi takve stvari upotreba NumPy polja nam ionako neće donijeti nikakve prednosti i treba koristiti obične liste. (Za konverziju NumPy liste u običnu koristimo funkciju list().)

Jedno od vrlo korisnih svojstava NumPy lista je da se većina matematičkih operacija prirodno distribuira po elementima liste (obične liste nemaju to svojstvo):

sage: xs = np.linspace(1,10,3); xs
array([  1. ,   5.5,  10. ])
sage: xs + 1
array([  2. ,   6.5,  11. ])
sage: sin(xs)
array([ 0.84147098, -0.70554033, -0.54402111])

NumPy liste mogu biti i višedimenzionalne, no i one su u memoriji računala zapisane u jednodimenzionalnom (1D) slijedu memorijskih adresa. Stoga je preoblikovanje elemenata 1D NumPy u 2D polje proizvoljnog oblika računalno “jeftina” operacija, koja može biti od koristi

sage: b=a.reshape(2,5); print b
[[ 1  2  3  4  5]
 [ 6  7  8  9 10]]

sage: b.shape  # "oblik" polja - broj redaka i stupaca
(2, 5)

Pristupanje pojedinom elementu višedimenzionalnog polja je moguće očitim indeksiranjem a[i][j]..., ali je efikasnije koristiti skraćeno indeksiranje: a[i, j, ...]:

sage: b[1,1] = 42.

sage: print b
[[ 1  2  3  4  5]
 [ 6 42  8  9 10]]

Pažnja: radi efikasnosti, preoblikovanja i rezovi kroz NumPy polja ne kopiraju originalne elemente već samo manipuliraju pokazivačima na ista mjesta. Tako se npr. ova netom načinjena zamjena u listi b odražava i u listi a čijim preoblikovanjem je lista b nastala:

sage: print a
[ 1  2  3  4  5  6 42  8  9 10]

Obične liste nemaju takvo ponašanje:

sage: t5 = t1[2:4]; t5    # t1 je obična lista
[5, 7]

sage: t5[0] = 'novi'; print t5
['novi', 7]
sage: t1
[1, 3, 5, 7, 9, 11, 13]

Inače, rezovi kroz dvodimenzionalne NumPy liste su elegantan način ekstrakcije redaka ili stupaca:

sage: print b[:,1]
[ 2  42]

Ukoliko trebamo liste realnih (float) brojeva, možemo koristiti NumPy inačicu funkcije range() (sintaksa je ista kao za range())

sage: np.arange(2., 9.9, 1.1)
array([ 2. ,  3.1,  4.2,  5.3,  6.4,  7.5,  8.6,  9.7])

Funkcija np.range() je pogodna kad želimo specificirati korak liste. Kad želimo specificirati broj elemenata liste koristimo funkciju np.linspace().

sage: np.linspace(0, 10, 5)
array([  0. ,   2.5,   5. ,   7.5,  10. ])

Za daljnje detalje o NumPy poljima, vidi NumPy Tutorial.

Zadatak 7

Za spajanje dvije jednako duge 1D liste u 2D listu (zapravo listu tuplova) koristimo naredbu zip:

sage: xs = [11, 12, 13, 14, 15]
sage: ys = [-1, -2, -3, -4, -5]
sage: points = zip(xs, ys); points
[(11, -1), (12, -2), (13, -3), (14, -4), (15, -5)]

Rastavite listu points natrag na originalne dvije 1D liste i to dvjema različitim metodama:

1. Dva obuhvaćanja liste points (ova metoda nema veze s NumPy-em)
2. Dva reza kroz listu points, koju prvo pretvorite u NumPy polje pomoću np.array.

Footnotes

[1]

Atributi objekta su sve ono čemu se pristupa operatorom točkice .. Ranije spomenute metode su atributi koji se mogu pozivati kao funkcije. dtype je atribut koji je naprosto tip elementa polja. Za bolje razumijevanje svega ovog dobro je pročitati nešto o objektno-orijentiranom programiranju u Pythonu.