3-1-Liste-S
system:sage


<h2>3.1 Liste i drugi kontejneri</h2>
<p>Liste su važan dio Sage-a i pythona. Srodne su poljima (array) iz standardnih programskih jezika (C, Fortran), ali imaju bitno vi&scaron;e svojstava. Elementi liste mogu biti praktički bilo koji objekti.</p>

{{{id=1|
t1 = [1, 3, 5, 7, 9, 11]; print t1
t2 = [sin, cos, log]; print t2
t3 = [[], ["jedan"], t1]; t3
///
}}}

<p>Već smo ranije upoznali pristupanje elementima liste pomoću indeksiranja i mogućnost da na taj način promijenimo pojedine elemente liste:</p>

{{{id=3|
print t1[1]
t1[1] = "tri"
print t1[1]
///
}}}

<p>Ukoliko želimo pristupiti većem broju elemenata od koristi su tzv. <em>rezovi</em> liste (engl. <em>slice</em>). Općenita sintaksa je <span style="font-family: courier new,courier;">lista[početak:kraj:korak]</span>, gdje je "početak" uključen u rez, a "kraj" nije:</p>

{{{id=4|
print t1[2:6]
t1[2:6:2]
///
}}}

<p>Ukoliko rez ide od početka ili do kraja liste, odgovarajuće indekse možemo izostaviti:</p>

{{{id=75|
t1[2:]
///
}}}

<p>Negativni indeksi nam omogućuju da brojimo od kraja liste ...</p>

{{{id=78|
t1[-2:]   # zadnja dva elementa
///
}}}

<p>... a negativan korak da rez ide unatrag:</p>

{{{id=79|
t1[::-1]  # lista natraške
///
}}}

<p>Za traženje indeksa nekog elementa liste, ubacivanje elemenata u liste i slične operacije stoje na raspolaganju metode lista:</p>

{{{id=5|
dir(t1)[-9:]
///
}}}

<p>Ovdje smo koristili funkciju dir() koja daje listu atributa nekog objekta (uključujući njegove metode). Samo zadnjih 9 je trenutno zanimljivo. (Inaće, dir() bez argumenta daje popis svih trenutno definiranih imena.)</p>

{{{id=94|
print len(dir())
dir()[:12]
///
}}}

<p>Osim count() i index(), sve ostale metode mijenjaju listu.</p>

{{{id=6|
t2 = t2[:-1]; t2   # micanje zadnjeg elementa
///
}}}

{{{id=84|
t1
///
}}}

<p><span id="cell_outer_10"><span id="cell_outer_5">&diams; </span></span><strong>Zadatak 3.1.1</strong>:Izbri&scaron;ite u gornjoj listi t1 treći element (ne element s indeksom=3!)&nbsp; i dodajte na kraj jo&scaron; dva elementa, brojeve 13 i 15. Ispi&scaron;ite novonastalu listu, a zatim element 'tri' zamijenite s brojem 3, koristeći metodu index().</p>

<p>Ukoliko treba transformirati sve elemente liste, najelegantnije je koristiti <em>obuhvaćanje liste</em> (engl. <em>list comprehension</em>):</p>

{{{id=91|
[n+1 for n in t1]
///
}}}

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

{{{id=10|
t5 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[n for n in t5 if is_even(n)]    # izbor parnih elemenata
///
}}}

<p>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&scaron;imo ih (koristimo činjenicu da su stringovi kao liste znakova pa možemo koristiti rezove na njima):</p>

{{{id=93|
[p for p in dir() if p[:3]=='is_']
///
}}}

<p>Ovakve liste su pogodne za simboličke račune, ali za numeriku su efikasnija numpy polja koja smo već dosta koristili u pro&scaron;lom poglavlju. Ona su zapisana u neprekinutom slijedu memorijskih lokacija &scaron;to omogućuje brži pristup no zbog toga je nužno unaprijed deklarirati koji tip objekata su elementi (integer, float, complex ...) i svi elementi moraju biti istog tipa.</p>

{{{id=12|
import numpy as np   # uvođenje skraćenice za ime modula
///
}}}

{{{id=13|
a = np.array(t5); print a   # konverzija obične liste u numpy polje
b = np.array([2., 2.5, 3, 3.5]); print b
///
}}}

<p>Očitavanje tipa objekata u numpy polju:</p>

{{{id=98|
print a.dtype
b.dtype
///
}}}

<p>Pri konstrukciji numpy polja izbor tipa objekata je automatski, ali moguće ga je i odrediti opcionalnim argumentom dtype:</p>

{{{id=99|
c = np.array(t5, dtype=np.float64); print c
///
}}}

<p>Numpy polja imaju dosta vi&scaron;e metoda od običnih lista:</p>

{{{id=14|
dir(a)[-66:]
///
}}}

<p>(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.).</p>

{{{id=18|
b=a.reshape(2,5); print b
///
}}}

{{{id=19|
b.shape  # "oblik" polja - broj redaka i stupaca
///
}}}

<p>Pristupanje pojedinom elementu vi&scaron;edimenzionalnog polja je moguće očitim indeksiranjem a[i][j]..., ali je efikasnije koristiti skraćeno indeksiranje: a[i, j, ...]:</p>

{{{id=15|
b[1,1] = 42.
///
}}}

{{{id=17|
print b
///
}}}

{{{id=21|
print a
///
}}}

<p>Pažnja: radi efikasnosti, rezovi kroz numpy polja ne kopiraju originalne elemente već samo daju pokazivače na ista mjesta u memoriji (vidi gore element '42' koji se pojavio i u listi a). Obične liste nemaju takvo pona&scaron;anje:</p>

{{{id=22|
t5 = t1[2:4]; t5
///
}}}

{{{id=24|
t5[0] = 'novi'; print t5
t1
///
}}}

<p>Za daljnje detalje o numpy poljima, vidi <a href="http://www.scipy.org/Tentative_NumPy_Tutorial">ovdje</a>.</p>

<h3>Konstruiranje lista</h3>

<p>Za konstrukciju liste cijelih brojeva najkorisnija je funkcija range():</p>

{{{id=25|
range(-5, 15, 3)
///
}}}

<p>range() radi samo sa cijelim brojevima ...</p>

{{{id=26|
range(2., 7.5, 1.5)
///
}}}

<p>... pa ukoliko trebamo liste realnih (float) brojeva, možemo ili dijeliti ove cijele s nekom odabranom realnom konstantom, ili koristiti numpy inačicu funkcije range() koja se zove arange() ...</p>

{{{id=28|
np.arange(2., 9.9, 1.1)
///
}}}

<p>... koju po potrebi možemo i konvertirati natrag u običnu listu funkcijom list():</p>

{{{id=30|
list(_)
///
}}}

<p>Kombiniranjem funkcije range() i idioma obuhvaćanja liste možemo kreirati kompleksne stvari. Npr. lista simboličkih izraza:</p>

{{{id=31|
[x^n/factorial(n)  for n in range(1,6)]
///
}}}

<p><span id="cell_outer_29"><span id="cell_outer_10"><span id="cell_outer_5">&diams; </span></span><strong>Zadatak 3.1.2</strong>:</span>Konstruirajte listu svih prim-brojeva manjih od 100. Koliko ima prim-brojeva manjih od $10^4, 10^5, 10^6, \ldots$? Usporedite rezultat (i brzinu njegovog dobivanja) s ugrađenom funkcijom prime_pi(), te slijedećom aproksimacijom (koja je sadržaj slavnog teorema o prim-brojevima)</p>
<p>$$</p>
<p>\pi(x) = \int_{2}^{x} \frac{dx}{ln(x)}</p>
<p>$$</p>
<p>Inaće, mjerenje vremena potrebnog da se izvr&scaron;i neka ćelija izvodi se stavljanjem "%time" u prvi red:</p>

{{{id=119|
%time
factor(2923003274661805836407421649242809468366377451741)
///
}}}

<p>(Prekid računa koji traje predugo izvodi se putem menija Action-&gt;Interrupt ili pritiskom na tipku "Escape".)</p>


<p><span id="cell_outer_29"><span id="cell_outer_10"><span id="cell_outer_5">&diams; </span></span><strong>Zadatak 3.1.3</strong>:</span> 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&nbsp;&nbsp; i&nbsp; testirajte koliko ima prim-brojeva među njima. Iz tog udjela odredite $\pi(x)$. Kolika veličina uzorka vam treba da bi relativna gre&scaron;ka prema prime_pi(10^10) razumno često pala ispod 1%?</p>


<h3>Ostali kontejneri</h3>
<p>Osim lista postoje i drugi "kontejneri" za objekte. Kao prvo tu su već u pro&scaron;lom poglavlju spominjani tuple-ovi. Glavna razlika prema listama (osim očite razlike da liste idu u uglate, a tuplovi u okrugle zagrade) je da su tuplovi nepromjenjivi - nije moguće promijeniti neki njihov element ili im dodati nove. Ukoliko je to iz nekog razloga nužno treba konstruirati novi tupl:</p>

{{{id=127|
tpl = (1, 3, 5, 7)
tpl[3] = 2
///
}}}

{{{id=128|
tpl[:2] + (2,) + tpl[3:]
///
}}}

<p>Ali to je rijetko potrebno. Naime, osim ove razlike u promjenjivosti glavna razlika 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), ...].</p>

<p>Daljnji kontejneri koji nam stoje na raspolaganju su <em>skupovi</em> (engl. <em>set</em>), koji su skupovi različitih(!) objekata i s kojima možemo raditi standardne stvari poput unije, presjeka, komplementa ...</p>

{{{id=50|
s1 = set([10, 9, 10, 8, 7, 7, 7, 4]); s1
///
}}}

<p>(Uočite da se duplikati automatski izbacuju.)</p>

{{{id=53|
print s1.union(l1)
print s1.intersection(l1)
s1.difference(l1)
///
}}}

<p>Zadnji, vrlo važan, kontejner kojeg ćemo spomenuti je <em>riječnik</em> (engl. <em>dictionary</em>). Riječ je o preslikavanju key-&gt;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).</p>

{{{id=131|
d1 = {'a':1, 'c':3, 'b':2}; print d1
d2 = {1: sin, 2: cos, 3: log}; print d2
d3 = {'ime': 'pero', 'prezime': 'peric', 'spol':'M'}; d3
///
}}}

<p>Redosljed elemenata u riječniku nema značenja. Pristup pojedinim elementima riječnika je moguć "indeksiranjem" pomoću ključa:</p>

{{{id=139|
d1['c']
///
}}}

<p>Na isti način je moguće dodavati nove elemente u riječnik:</p>

{{{id=136|
d2[5] = tan
///
}}}

{{{id=135|
d2.keys()
///
}}}

<p>Iteriranje po riječniku ne daje elemente već samo ključeve:</p>

{{{id=141|
[it for it in d2]
///
}}}

{{{id=134|
[d2[n](1.) for n in d2.keys()]
///
}}}

<p><span id="cell_outer_57"><span id="cell_outer_29"><span id="cell_outer_10"><span id="cell_outer_5">&diams; </span></span><strong>Zadatak 3.1.4</strong>:</span></span> (Nema veze s riječnicima.) Pronađite najveći dvoznamenkasti broj $k$ za koji je $m=2^k - 1$ prost broj. Ispi&scaron;ite broj $m$ u dekadskom i binarnom sustavu:</p>

{{{id=142|

///
}}}