Strukture podataka valja shvatiti kao zbirke vrijednosti, a ova dva termina se često koriste i na engleskom (data structure i collection). Upotrebe ovog koncepta su višestruke. Ponekad se neka vrijednost po svojoj prirodi sastoji od više pod-vrijednosti. Spomenuli smo već tekst koji je zapravo “niz znakova”, a možemo tome dodati i kojekakve složene vrijednosti poput datuma (tri cijela broja: dan, mjesec i godina) ili osobnog imena (dva niza znakova: ime i prezime1).
Uz to, ponekad želimo provesti istu radnju na više objekata iste vrste. Na primjer, recimo da želimo promijeniti kodnu stranicu svih tekstualnih datoteka u nekom direktoriju: Prvo nam je potreban popis svih putanja do datoteka koje planiramo procesirati (što je najčešće jednostavno popis tekstualnih nizova), a zatim za svaku putanju usnimavamo datoteku i zapisujemo tekst u drugu datoteku koja ima drugačiju kodnu stranicu. Također, kad radimo s računalnim podacima, na primjer podacima o knjigama ili o računima s blagajni, po prirodi stvari radimo sa strukturama podataka. Kako bi uopće počeli raditi sa spomenutim konceptima potrebno nam je prvo usvojiti neke osnove vezane uz strukture podataka.
Postoje posebne vrste vrijednosti koje služe upravo strukturiranju drugih vrijednosti odnosno koje nam omogućuju da okupljamo vrijednosti bilo koje vrste u zbirke vrijednosti. Vrlo je korisno proučiti dvije osnovne vrste struktura u Pythonu: popis (list) i rječnik (dict). Učenjem ovih koncepata približavamo se i temeljima razmjene podataka u mnogim web uslugama. Tome možemo dodati i skup (set) koji se nešto manje koristi od popisa i rječnika, ali je u nekim slučajevima vrlo korisna struktura.
Popis je niz objekata u kojem se svaki objekt može identificirati putem indeksa pozicije na kojoj se nalazi. Već smo vidjeli da je string zapravo popis znakova, ali ovo je poseban slučaj popisa koji dozvoljava samo tekstualne znakove kao članove. Najčešće korištena struktura pomoću koje se implementira popis bilo kojih vrsta vrijednosti u Pythonu je list. Ovako definiran popis se može mijenjati i vjerojatno je najčešće korištena struktura podataka u Python programima. Pogledajmo kako možemo stvoriti popis i dohvatiti neki element iz njega.
>>> boje = ["crvena", "zelena", "plava"] # popis definiramo uglatim zagradama
>>> print(boje)
["crvena", "zelena", "plava"]
# elemente dohvaćamo uglatim zagradama i indeksom pozicije
# # indeksi počinju od 0, odnosno prvi element popisa se nalazi na indeksu 0
>>> prva_boja = boje[0]
>>> print(prva_boja)
crvena
Primjer je prikazao najjednostavniji način stvaranja popisa. Zarezom odvojeni objekti unutar uglatih zagrada stvaraju popis. Vrijedi napomenuti i da unutar popisa, kao i u ostalim zagradama u Pythonu, možemo dodavati nove retke radi preglednosti. Na primjer:
>>> boje_a = ["crvena", "zelena", "plava"] # popis definiramo uglatim zagradama
# popis boje_b identičan je popisu boje_a, samo je raspisan drugačije
>>> boje_b = [ "crvena", "zelena", "plava" ]
>>> boje_a == boje_b
True
Mogućnost pisanja struktura u više redaka je korisna za osiguranje preglednosti kod većih struktura (na primjer, popisa s 10 i više elemenata).
Također, većina struktura pruža način kako dohvatiti neki individualni objekt koji se u njoj nalazi. U mnogim slučajevima to je i poanta korištenja Uglate zagrade odmah nakon imena neke varijable u Pythonu (i mnogim drugim jezicima) označavaju upravo to: dohvati objekt(e) iz strukture podataka putem vrijednosti u uglatim zagradama. Kod popisa je to indeks, odnosno cijeli broj koji označava poziciju elementa u popisu, gdje je indeks prvog objekta 0, a zadnji je jednak broju objekata u popisu -1. Drugim riječima, validni indeksi za popis od četiri objekta su 0, 1, 2 u 3. Obzirom da su adrese u popisu jasno definiran raspon brojeva, kao indekse možemo koristiti i negativne brojeve i raspone brojeva:
>>> boje = ["crvena", "zelena", "plava", "žuta", "ljubičasta"]
# dohvati drugu boju iz popisa, odnosno boju na indeksu 1
>>> druga_boja = boje[1]
>>> print(druga_boja)
zelena
# dohvati zadnju boju iz popisa
>>> zadnja_boja = boje[-1]
>>> print(zadnja_boja)
ljubičasta
# dohvati raspon vrijednosti iz popisa
>>> neke_boje = boje[1:4] # dohvaća vrijednosti pod indeksima 1, 2 i 3
>>> print(neke_boje)
["zelena", "plava", "žuta"]
# kod raspona indeksa, vrijednost prvog indeksa je uvijek
# uključena u rezultat, a zadnja nije
# ukoliko ispustimo zadnji indeks u rasponu, to znači "odaberi do kraja"
>>> sve_osim_prve = boje[1:]
>>> sve_osim_prve
["zelena", "plava", "žuta", "ljubičasta"]
# ukoliko ispustimo prvi indeks u rasponu, to znači "odaberi od početka"
>>> sve_osim_zadnje = boje[:-1]
>>> sve_osim_zadnje
["crvena", "zelena", "plava", "žuta"]
Jedan od problema sa strukturama podataka je što je riječ o apstraktnim konceptima za koje je pri prvom susretu teško prikazati praktične primjere. Ipak, kako bismo se barem približili praksi pogledajmo kako dobiti popis članova nekog direktorija:
>>> import os
>>> os.listdir('c:/test')
['dat_a.pdf', 'dat_b.docx', 'dat_c.txt', 'dir_a', 'dir_b']
Primjer prikazuje kako dobiti popis članova nekog direktorija odnosno popis stringova koji su imena datoteka i pod-direktorija u nekom direktoriju. U prikazanom slučaju na disku c postoji direktorij test koji sadrži tri datoteke (dat_a.pdf, dat_b.docx i dat_c.txt) i dva poddirektorija (dir_a i dir_b). Jednostavno dobiti popis članova nekog direktorija, kao što vidimo, nije teško. Ipak, dok je samo po sebi jasno kako bi ovakav popis mogao biti koristan, ima još puno posla kako bi s ovime mogli učiniti nešo konkretno: razlikovati datoteke od direktorija, izraditi pune putanje od imena, razlikovati različite vrste datoteka, pristupati sadržaju datoteke i slično. Drugim riječima, problem prvog dodira sa strukturama podataka je što su one vrlo važne za programiranje gotovo bilo čega, ali primjeri koji bi prikazali njihovu praktičnu uporabu su često preopširni ili prekompleksni za prvi susret. Ovaj dio skripte će se, stoga, usredotočiti na jednostavne apstraktne primjere rada sa strukturama podataka, a njihova praktična uporaba će se prikazati u kasnijim većim primjerima koji rade nešto konkretno ili zabavno.
listKao i kod tzv. primitivnih vrsti vrijednosti u Pythonu (int, float, bool, str), nazivi struktura vrijednosti su također i funkcije s kojima možemo druge objekte pretvarati u tu strukturu. Funkcija list prima jedan parametar i raščlanjuje poslanu vrijednost na sastavne elemente te vraća rezultat kao popis.
Pogledajmo primjere:
U zadnjoj liniji prijašnjeg primjera vidimo grešku koja se javlja kada pokušamo pretvoriti u popis nešto što se ne da raščlaniti na sastavne djelove. U ovom slučaju radi se o cijelom broju. Kao što vidimo, poruka kaže “objekt vrste int nije iterativan”. Sjetimo se, kada je vrijednost “iterativna”, to znači da se po njoj ne može prebirati što je upravo zahtjev da bi se nešto moglo pretvoriti u popis. Vrijednost moramo moći “izlistati”.
Najjednostavnija promjena popisa je promjena vrijednosti koja se nalazi na nekom indeksu. Pogledajmo primjer:
>>> boje = ["crvena", "zelena", "plava"]
>>> boje[1] = "ljubičasta" # postavi drugi element popisa na vrijednost "ljubičasta"
>>> print(boje)
["crvena", "ljubičasta", "plava"]
Ostale promjene popisa se provode putem metoda koje pruža vrsta vrijednosti list. Ovih metoda nema puno i većina ih provodi relativno jednostavne i očekivanje radnje. Pogledajmo koje su to:
append - dodaj novi član na kraj popisa
clear - obriši sve članove popisa, odnosno isprazni popis
copy - napravi neovisnu kopiju popisa u memoriji
extend - proširi popis svim članovima drugog popisa
insert - ubaci novi član u popis na određeni indeks
pop - izbaci zadnji član iz popisa ili izbaci član na nekom indeksu
remove - izbaci prvi član koji je pronađen u popisu
reverse - obrni redoslijed članova popisa
sort - sortiraj popis
Pogledajmo primjere:
>>> boje = ["crvena", "zelena", "plava"]
# dodaj vrijednost na kraj popisa
>>> boje.append("žuta")
>>> print(boje)
["crvena", "zelena", "plava", "žuta"]
# proširi popis svim vrijednostima iz drugog popisa
>>> druge_boje = ["crna", "bijela"]
>>> boje.extend(druge_boje)
>>> print(boje)
["crvena", "zelena", "plava", "žuta", "crna", "bijela"]
# ubaci vrijednost na određeni indeks
>>> boje.insert(2, "zelena")
>>> print(boje)
["crvena", "zelena", "zelena", "plava", "žuta", "crna", "bijela"]
# dohvati i izbaci zadnju vrijednost u popisu
>>> zadnja_boja = boje.pop()
>>> print(zadnja_boja)
bijela
>>> print(boje)
["crvena", "zelena", "zelena", "plava", "žuta", "crna"]
# dohvati i izbaci vrijednost u popisu na nekom indeksu
>>> boje = ["crvena", "zelena", "zelena", "plava", "žuta", "crna"]
>>> peta_boja = boje.pop(4)
>>> print(peta_boja)
žuta
>>> print(boje)
["crvena", "zelena", "zelena", "plava", "crna"]
# izbaci PRVU pronađenu vrijednost
>>> boje.remove("zelena")
>>> print(boje)
["crvena", "zelena", "plava", "crna"]
# sortiraj popis
>>> boje.sort()
>>> print(boje)
["crna", "crvena", "plava", "zelena"]
Uz navedene metode za promjene popisa, postoje i neke koje služe informiranju o članovima popisa:
index - dohvati prvi indeks na kojem se nalazi neki objekt ili javi grešku ukoliko taj objekt nije u popisu
count - prebroji koliko se puta neki vrijednost pojavljuje u popisu
Petlja “za svaki”, naravno, normalno radi s popisima.
>>> boje = ["crvena", "zelena", "plava"]
>>> for boja in boje: print(boja)
Rezultat:
crvena zelena plava
Uz navedeno, često je korisno prebirati po indeksima, a ne po vrijednostima popisa. U tu svrhu, vrlo nam je korisna funkcija range. Ta funkcija služi stvaranju niza brojeva od nekog početnog do nekog završnog. Pogledajmo primjere:
>>> r = range(2, 10)
>>> print(r)
range(2, 10) # range nije popis!
>>> print(list(r)) # ali bilo koji range možemo pretvoriti u popis
[2, 3, 4, 5, 6, 7, 8, 9]
>>> r = range(0, 5)
>>> print(list(r))
[0, 1, 2, 3, 4]
>>> r = range(5) # ako pošaljemo samo jedan broj, smatra se da je početni broj 0
>>> print(list(r))
[0, 1, 2, 3, 4]
>>> boje = ["crvena", "zelena", "zelena", "plava", "crna"]
>>> broj_boja = len(boje)
>>> for i in range(broj_boja): print("Na indeksu", i, "nalazi se", boje[i])
Na indeksu 0 nalazi se crvena
Na indeksu 1 nalazi se zelena
Na indeksu 2 nalazi se zelena
Na indeksu 3 nalazi se plava
Na indeksu 4 nalazi se crna
Kao što vidimo, funkcija range posebno je korisna za generiranje validnih indeksa za popis. Kao i kod indeksa popisa, ova funkcija uključuje prvu vrijednost, a zadnju ne. Na primjer, range(0, 4) generira brojeve 0, 1, 2 i 3. Ukoliko traženi brojevi počinju od 0, funkcija range se može pozvati sa samo jednim parametrom koji označava do kojeg broja se generira. Ovo nam omogućuje da ukoliko želimo generirati sve validne indekse za neki popis to možemo učiniti jednostavnim izrazom range(len(neki_popis)).
Osim definiranja minimuma i maksimuma, range prima i opcionalni treći parametar: korak (eng. step). Ovaj parametar je zadan na 1 i definira pomak između dva broja koja se generiraju funkcijom range. Navedeno je možda teže shvatiti kroz definiciju nego kroz primjer pa pogledajmo jedan:
Do sada smo radili samo s popisom vrste list, ali to nije jedina vrsta popisa. Glavna distinkcija između popisa u Pythonu ovisi o tome da li je popis promjenjiv ili nepromjenjiv. list je, kao što smo vidjeli iz primjera, promjenjiv popis. Postoji i nepromjenjivi popis koji se naziva tuple. Dohvaćanje elemenata iz obje vrste popisa je identično, ali tuple se ne definira kroz uglate već kroz oble zagrade, a u mnogim slučajevima se može pisati i bez zagrada.
Kao što vidimo, razlika između prikazane dvije vrste popisa je u tome što je list moguće mijenjati, a tuple ne. Sve što možemo raditi s popisom vrste tuple, dakle, vrijedi i za popise vrste list, ali list pruža mogućnost promjena u popisu, a tuple ne. Pokušaj dodavanja nove vrijednosti u list je, na primjer, normalan postupak, a pokušaj dodavanja nove vrijednosti u tuple javlja grešku jer je tuple nepromjenjiv. S druge strane, dohvaćanje vrijednosti putem indeksa funkcionira identično i za list i za tuple.
Dok je “popis” relativno jednostavan koncept, kada bismo se dublje skoncentrirali na popis kao strukturu podataka u odnosu na računalo, vidjeli bismo da postoje različite implementacije istog koncepta koje se razlikuju u efikasnosti i mogućnostima. Neke implementacije, na primjer, su visoko efikasne, ali ne dopuštaju nikakve promjene. Kod implementacija koje omogućuju promjene, različite radnje mogu biti različito efikasne (u računalnom žargonu “različito koštaju”) ovisno o načinu implementacije popisa. Pythonov list, na primjer, je visoko efikasan u dodavanju nove vrijednosti na kraj popisa kao i u izbacivanju te vrijednosti, ali neefikasan u dodavanju vrijednosti na početak popisa ili izbacivanja vrijednosti s početka popisa. Da situacija bude još gora, dodavanje odnosno izbacivanje vrijednosti je tim manje efikasno čim ima više objekata u popisu nakon objekta koji se dodaje ili izbacuje.
Ukoliko želimo efikasno dodavati i izbacivati vrijednosti iz sredine popisa, Python ima uključenu i treću implementaciju popisa koja je dostupna iz modula collections i zove se deque. Zašto onda ne bismo uvijek koristili deque? Zato jer za dodatne mogućnosti uvijek postoji cijena pa je tako popis vrste deque manje memorijski efikasan od popisa vrste list. U svakom slučaju, modul collections, kao što ime kaže, donosi dodatne strukture podataka koje su specijaliziranije u naravi od osnovnih struktura koje se prikazuju u ovom poglavlju i uglavnom su njihove varijante.
Osim spomenutih posebnih metoda koje dozvoljava struktura list, postoje i dva općenita pitanja koja često želimo postaviti bilo kojoj strukturi podataka. Ta pitanja su:
Koliko ima vrijednosti u nekoj strukturi?
Da li neka struktura sadrži neki određeni objekt?
Broj objekata u nekoj strukturi podataka često se naziva i “duljinom” te strukture. Python funkcija len vraća upravo taj broj.
>>> boje = ["crvena", "zelena", "plava"]
>>> n_boja = len(boje)
>>> print(n_boja)
3
len je funkcija koja radi na svim vrstama objekata za koje je pitanje “Koliko ima elemenata (tj. podobjekata) u ovom objektu?” validno. Ako pitanje nije validno, odnosno objekt koji je poslan kao parametar ga ne podržava, len javlja grešku.
Kao što je za očekivati, poziv funkcije len s cijelim brojem kao parametrom javlja grešku koju možemo čitati kao “cijeli brojevi nemaju broj elemenata”. len teksta, međutim, vraća vrijednost jer je kod teksta to “broj znakova”.
Također, postoji univerzalan način provjere da li se neka vrijednost nalazi u određenoj zbirci vrijednosti i to putem operatora in. Pogledajmo primjere:
>>> if "š" in "Krešimir":
print('"Krešimir" sadrži "š".')
"Krešimir" sadrži "š".
>>> boje = ["crvena", "zelena", "zelena", "plava", "crna"]
>>> "zelena" in boje
True
>>> "žuta" in boje
False
Rječnik je skup “ključ: vrijednost“ parova. Za razliku od popisa, rječnik nema značajan redoslijed objekata, već svaki objekt koji se pohranjuje kao vrijednost ima vlastiti ključ odnosno “šifru” ili “ime” po kojem ga se može dohvatiti. Rječnik se definira vitičastim zagradama i s dvotočkom kao znakom koji razgraničuje ključeve od vrijednosti. Pogledajmo primjer:
>>> data = {"boja": "plava", "visina": 30} # rječnik s dva elementa # svaki element se sastoji od ključa # i vrijednosti koja mu je pridružena
>>> print(data["boja"])
plava
>>> print(data["visina"])
30
Rječnik je vrlo intuitivna struktura za opis nekog predmeta odnosno za strukturiranje metapodataka. Na primjer, metapodaci ugrađeni u neku glazbenu datoteku mogli bi se prikazati kao:
track_data = {
"artist": "Monty Python",
"title": "Lumberjack Song",
"album": "Monty Python Sings",
"year": 1989
}
Osim toga, rječnik je, kao što ime kaže, koristan i za “prevođenje” vrijednosti. Pogledajmo doslovan primjer. Recimo da dobivamo podatke poput varijable “track_data” u primjeru niže iz neke vanjske usluge i želimo prevesti ključeve (odnosno nazive polja) na neke naše nazive.
python
Prikazan kod ispisuje:
{
"album": "Monty Python Sings",
"godina": 1989,
"naslov": "Lumberjack Song",
"umjetnik": "Monty Python"
}
Također, primijetimo da prebiranje po rječniku s petljom for prebire po ključevima. Što ako želimo prebirati po vrijednostima ili po ključevima i vrijednostima odjednom?
python Prebiranje po vrijednostima rječnikalisting:dict_values for value in track_data.values(): # prebire po vrijednostima print(value)
Rezultat:
python 1989 Lumberjack Song Monty Python Sings Monty Python
Redoslijed vrijednosti po kojima se prebire za razliku od liste nije konzistentan. U drugom prebiranju, redoslijed ispisanih vrijednosti može biti drugačiji. Drugim riječima, adresa vrijednosti nije određena pozicijom već imenom. Radi toga je često korisno i prebirati po ključevima i vrijednostima odjednom. Pogledajmo kako:
for key, value in track_data.items(): # prebire po (ključ, vrijednost) parovima print(key, value)
Rezultat:
year 1989 title Lumberjack Song album Monty Python Sings artist Monty Python
Funkcija dict služi stvaranju rječnika. Kao i sve ostale funkcije koje označavaju vrstu vrijednosti, poziv bez parametara stvara prazan rječnik.
>>> d = dict() # isto što i d = {}
>>> print(d)
{}
Poziv na dict s imenovanim parametrima stvara novi rječnik s tim parametrima kao ključevima.
d = dict(a=1, b=2)
print(d)
{'a': 1, 'b': 2}
dict može primiti i popis parova, odnosno popis popisa gdje svaki pod-popis ima dva člana: ključ i vrijednost.
popis_parova = [
["a", 1],
["b", 2],
["c", 1]
]
d = dict(popis_parova)
print(d)
popis_parova = list(d.items()) # popis parova možemo i dohvatiti iz rječnika
print(popis_parova)
{'a': 1, 'b': 2, 'c': 1}
[['a', 1], ['b', 2], ['c', 1]]
Skup je implementacija matematičkog koncepta skupa: zbirka jedinstvenih vrijednosti bez značajnog redoslijeda. U smislu onoga što već znamo o Pythonu, skup možemo shvatiti kao samo ključeve rječnika bez pridruženih vrijednosti.
>>> s = set()
>>> s.add(1)
>>> print(s)
1
>>> s.add(2)
>>> print(s)
1, 2
>>> s.add(2) # skup već sadrži vrijednost 2 pa nema promjene
>>> print(s)
1, 2
Skup je rjeđe korištena struktura od popisa i rječnika, ali je vrlo korisna u nekim slučajevima.
Kao i u matematici, skup se označava vitičastim zagradama. Razlika od rječnika je što se skup ne sastoji od “ključ: vrijednost” parova, već od individualnih elemenata. Nažalost, obzirom da se vitičaste zagrade koriste i za rječnik i za skup, prazan skup moramo definirati pomoću funkcije set. Kada želimo definirati skup postojećih vrijednosti, možemo koristiti i vitičaste zagrade. Pogledajmo neke primjere definicije skupova:
>>> s = {} # pažnja! prazan rječnik
>>> print(s)
{}
>>> s = set() # prazan skup
>>> print(s)
set()
>>> s = "a", "b", "c" # skup s članovima
>>> print(s)
"a", "c", "b"
>>> s = set("ana") # napravi skup od elemenata vrijednosti (npr, tekst)
>>> print(s)
{"a", "n"}
>>> s = set(["ana"]) # napravi skup od elemenata popisa
>>> print(s)
{"ana"}
>>> d = {"a": 1, "b": 2, "c": 1} # definiraj neki rječnik
>>> set(d) # ključevi rječnika kao skup
{"a", "c", "b"}
>>> set(d.values()) # sve različite vrijednosti u rječniku
{1, 2}
Za razliku od popisa i rječnika, skup ne pruža način dohvata neke odabrane vrijednosti iz zbirke. Drugim riječima, vrijednosti u skupu ne možemo jednoznačno adresirati jer vrijednosti nemaju niti konzistentan redoslijed (pa ne možemo koristiti poziciju neke vrijednosti kao indeks) niti se vrijednosti mogu identificirati putem kakvog ključa. Zašto bismo onda prikupljali vrijednosti u skupove? Skupovi omogućuju matematičke operacije sa skupovima poput unije, presjeka i razlike, odnosno operacije koje su vrlo korisne u radu s podacima. Pogledajmo primjere:
>>> a.intersection(b) # ili a & b
{"c", "b"}
>>> a & b # isto što i a.intersection(b)
{"c", "b"}
>>> a.union(b) # ili a | b
{"a", "d", "c", "b"}
>>> a.difference(b) # ili a - b
{"a"}
>>> b.difference(a) # ili b - a
{"d"}
Također, svojstvo skupa da sadrži samo različite vrijednosti je često korisno. Sljedeći primjer prikazuje kako ga možemo jednostavno iskoristiti da prebrojimo sve jedinstvene vrijednosti u nekoj zbirci vrijednosti.
>>> boje = ["crvena", "plava", "crvena", "zelena", "plava"]
>>> skup_boja = set(boje)
>>> print("N boja:", len(boje))
N boja: 4
>>> print("N različitih boja:", len(skup_boja))
N različitih boja: 3
Prikazane strukture podataka izvrsan su prvi susret s temom i već samo prikazani koncepti nas opunumoćuju ne samo u programiranju već i u općenitom radu s podacima kao i u razumijevanju vezane tematike. U idućem poglavlju je upravo riječ o osnovama korištenja ovih struktura za obradu podataka.
Osobna imena mogu imati još djelova i upravljanje podacima o osobnim imenima je vrlo kompleksno, ali najjednostavniji slučaj nam je ovdje dovoljno dobar primjer. ↩