Želite li unaprediti svoj programerski alat dodavanjem struktura podataka? Napravite prve korake već danas i naučite o strukturama podataka u Python-u.
Kada se upoznajete sa novim programskim jezikom, ključno je razumeti osnovne tipove podataka i ugrađene strukture podataka koje jezik nudi. U ovom vodiču posvećenom strukturama podataka u Python-u, istražićemo sledeće:
- Prednosti upotrebe struktura podataka
- Ugrađene strukture podataka u Python-u, kao što su liste, torke, rečnici i skupovi
- Implementacije apstraktnih tipova podataka kao što su stekovi i redovi.
Započnimo!
Zašto su strukture podataka korisne?
Pre nego što pređemo na različite strukture podataka, pogledajmo kako njihova upotreba može biti od pomoći:
- Efikasna obrada podataka: Pravilan izbor strukture podataka značajno doprinosi efikasnijoj obradi podataka. Na primer, ukoliko je potrebno čuvati kolekciju stavki istog tipa podataka – uz konstantno vreme pretrage i čvrstu povezanost – niz je idealan izbor.
- Bolje upravljanje memorijom: U većim projektima, za skladištenje identičnih podataka, određena struktura podataka može biti memorijski efikasnija od druge. Na primer, u Python-u se i liste i torke mogu koristiti za čuvanje kolekcija podataka istog ili različitih tipova. Međutim, ako znate da kolekciju nećete menjati, torke su bolji izbor jer zauzimaju manje memorije u odnosu na liste.
- Organizovaniji kod: Upotreba odgovarajuće strukture podataka za određenu funkcionalnost doprinosi boljoj organizaciji vašeg koda. Drugi programeri koji čitaju vaš kod očekivaće upotrebu specifičnih struktura podataka, u zavisnosti od željenog ponašanja. Na primer: ako vam je neophodno mapiranje ključ-vrednost sa konstantnim vremenom pretrage i umetanja, rečnik je optimalna struktura.
Liste
Kada vam je potrebno kreirati dinamičke nizove u Python-u – od intervjua za kodiranje do uobičajenih slučajeva upotrebe – liste su prva struktura podataka koju treba uzeti u obzir.
Python liste su kontejnerski tipovi podataka koji su promenljivi i dinamički, što omogućava dodavanje i uklanjanje elemenata sa liste direktno, bez potrebe za kreiranjem kopije.
Pri korišćenju Python lista:
- Indeksiranje u listu i pristup elementu na određenom indeksu se izvršava u konstantnom vremenu.
- Dodavanje elementa na kraj liste je operacija konstantnog vremena.
- Umetanje elementa na određenom indeksu je operacija linearnog vremena.
Na raspolaganju je set metoda lista koji omogućava efikasno obavljanje uobičajenih zadataka. Primer koda u nastavku ilustruje kako se ove operacije izvršavaju na primeru liste:
>>> nums = [5,4,3,2] >>> nums.append(7) >>> nums [5, 4, 3, 2, 7] >>> nums.pop() 7 >>> nums [5, 4, 3, 2] >>> nums.insert(0,9) >>> nums [9, 5, 4, 3, 2]
Python liste podržavaju i sečenje i testiranje članstva pomoću operatora `in`:
>>> nums[1:4] [5, 4, 3] >>> 3 in nums True
Struktura podataka liste nije samo fleksibilna i jednostavna, već omogućava i skladištenje elemenata različitih tipova podataka. Python takođe ima posebnu strukturu podataka niza za efikasno skladištenje elemenata istog tipa. Više o tome saznaćemo u nastavku vodiča.
Torke
U Python-u, torke su još jedna popularna ugrađena struktura podataka. Slične su Python listama po tome što se može vršiti indeksiranje u konstantnom vremenu, kao i sečenje. Međutim, torke su nepromenljive, tako da ih nije moguće menjati direktno. Sledeći primer koda ilustruje navedeno na primeru torke `nums`:
>>> nums = (5,4,3,2) >>> nums[0] 5 >>> nums[0:2] (5, 4) >>> 5 in nums True >>> nums[0] = 7 # nije važeća operacija! Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: 'tuple' object does not support item assignment
Dakle, kada želite kreirati nepromenljivu kolekciju i omogućiti njenu efikasnu obradu, torke su pravi izbor. Ukoliko je potrebna promenljiva kolekcija, preporučuje se upotreba liste.
📋 Saznajte više o sličnostima i razlikama između Python lista i torki.
Nizovi
Nizovi su manje poznate strukture podataka u Python-u. Slični su Python listama u smislu operacija koje podržavaju, poput indeksiranja u konstantnom vremenu i umetanja elemenata na određenom indeksu u linearnom vremenu.
Međutim, ključna razlika između lista i nizova je u tome što nizovi čuvaju elemente jednog tipa podataka. Zbog toga su čvrsto povezani i efikasniji u pogledu memorije.
Za kreiranje niza, koristi se konstruktor `array()` iz ugrađenog modula `array`. Konstruktor `array()` prihvata string koji specificira tip podataka elemenata i same elemente. Ovde kreiramo `nums_f`, niz brojeva sa pokretnim zarezom:
>>> from array import array
>>> nums_f = array('f',[1.5,4.5,7.5,2.5])
>>> nums_f
array('f', [1.5, 4.5, 7.5, 2.5])
Moguće je indeksiranje u niz (slično kao kod Python lista):
>>> nums_f[0] 1.5
Nizovi su promenljivi, pa je moguće vršiti izmene:
>>> nums_f[0]=3.5
>>> nums_f
array('f', [3.5, 4.5, 7.5, 2.5])
Ali nije moguće izmeniti element tako da bude drugog tipa podataka:
>>> nums_f[0]='zero' Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: must be real number, not str
Stringovi
U Python-u, stringovi su nepromenljive kolekcije Unicode karaktera. Za razliku od programskih jezika kao što je C, Python nema poseban tip podataka za pojedinačne karaktere. Prema tome, karakter je zapravo string dužine jedan.
Kao što je već navedeno, string je nepromenljiv:
>>> str_1 = 'python' >>> str_1[0] = 'c' Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: 'str' object does not support item assignment
Python stringovi podržavaju sečenje i poseduju set metoda za njihovo formatiranje. Sledi nekoliko primera:
>>> str_1[1:4] 'yth' >>> str_1.title() 'Python' >>> str_1.upper() 'PYTHON' >>> str_1.swapcase() 'PYTHON'
⚠ Važno je zapamtiti da sve navedene operacije vraćaju kopiju stringa i ne menjaju originalni string. Ukoliko vas zanima više, pogledajte vodič o string operacijama u Python-u.
Skupovi
U Python-u, skupovi su kolekcije jedinstvenih i heširanih stavki. Moguće je izvršavanje uobičajenih skupovnih operacija, kao što su unija, presek i razlika:
>>> set_1 = {3,4,5,7}
>>> set_2 = {4,6,7}
>>> set_1.union(set_2)
{3, 4, 5, 6, 7}
>>> set_1.intersection(set_2)
{4, 7}
>>> set_1.difference(set_2)
{3, 5}
Skupovi su po podrazumevanoj postavci promenljivi, što omogućava dodavanje novih i izmenu postojećih elemenata:
>>> set_1.add(10)
>>> set_1
{3, 4, 5, 7, 10}
📚 Čitanje o skupovima u Python-u: Kompletan vodič sa primerima koda
FrozenSetovi
Ukoliko vam je potreban nepromenljiv skup, možete koristiti `frozenset`. `frozenset` je moguće kreirati iz postojećih skupova ili drugih iterabilnih objekata.
>>> frozenset_1 = frozenset(set_1)
>>> frozenset_1
frozenset({3, 4, 5, 7, 10, 11})
Pošto je `frozenset_1` zamrznuti skup, doći će do greške ukoliko pokušate da dodate elemente (ili ga na drugi način izmenite):
>>> frozenset_1.add(15) Traceback (most recent call last): File "<stdin>", line 1, in <module> AttributeError: 'frozenset' object has no attribute 'add'
Rečnici
Python rečnik funkcioniše slično heš mapi. Rečnici se koriste za čuvanje parova ključ-vrednost. Ključevi rečnika moraju biti hešibilni, što znači da se heš vrednost objekta ne menja.
Moguće je pristupanje vrednostima pomoću ključeva, umetanje novih stavki i uklanjanje postojećih u konstantnom vremenu. Za navedene operacije postoje odgovarajuće metode rečnika.
>>> favorites = {'book':'Orlando'}
>>> favorites
{'book': 'Orlando'}
>>> favorites['author']='Virginia Woolf'
>>> favorites
{'book': 'Orlando', 'author': 'Virginia Woolf'}
>>> favorites.pop('author')
'Virginia Woolf'
>>> favorites
{'book': 'Orlando'}
OrderedDict
Iako Python rečnik obezbeđuje mapiranje ključ-vrednost, on je inherentno neuređena struktura podataka. Od Python-a 3.7, redosled umetanja elemenata se čuva, ali se to može eksplicitno postići korišćenjem `OrderedDict` iz modula `collections`.
Kao što je prikazano, `OrderedDict` čuva redosled ključeva:
>>> from collections import OrderedDict
>>> od = OrderedDict()
>>> od['first']='one'
>>> od['second']='two'
>>> od['third']='three'
>>> od
OrderedDict([('first', 'one'), ('second', 'two'), ('third', 'three')])
>>> od.keys()
odict_keys(['first', 'second', 'third'])
Defaultdict
Greške povezane sa ključevima su česte pri radu sa Python rečnicima. U situacijama kada pokušate pristupiti ključu koji ne postoji u rečniku, naići ćete na izuzetak `KeyError`.
Međutim, korišćenjem `defaultdict` iz modula `collections`, ovaj problem se rešava na izvorni način. Kada pokušate pristupiti ključu koji ne postoji u rečniku, ključ se dodaje i inicijalizuje sa podrazumevanom vrednošću specificiranom u podrazumevanoj fabrici.
>>> from collections import defaultdict >>> prices = defaultdict(int) >>> prices['carrots'] 0
Stekovi
Stek je struktura podataka po principu „poslednji ušao-prvi izašao“ (LIFO). Na steku se mogu obavljati sledeće operacije:
- Dodavanje elemenata na vrh steka: `push` operacija
- Uklanjanje elemenata sa vrha steka: `pop` operacija
Primer koji ilustruje funkcionisanje operacija `push` i `pop` na steku:
Kako implementirati stek koristeći listu
U Python-u, struktura podataka steka se može implementirati koristeći Python listu.
Operacija na listi | Ekvivalentna operacija na steku
—|—
Dodavanje na kraj liste pomoću metode `append()` | `push` na vrh steka
Uklanjanje i vraćanje poslednjeg elementa pomoću metode `pop()` | `pop` sa vrha steka
Primer koda u nastavku ilustruje kako se može emulirati ponašanje steka pomoću Python liste:
>>> l_stk = [] >>> l_stk.append(4) >>> l_stk.append(3) >>> l_stk.append(7) >>> l_stk.append(2) >>> l_stk.append(9) >>> l_stk [4, 3, 7, 2, 9] >>> l_stk.pop() 9
Kako implementirati stek koristeći deque
Drugi način za implementaciju steka je upotreba `deque` iz modula `collections`. `deque` predstavlja dvostrani red i podržava dodavanje i uklanjanje elemenata sa oba kraja.
Za emulaciju steka, moguće je:
- dodavati elemente na kraj pomoću `append()`, i
- uklanjati poslednji dodati element pomoću `pop()`.
>>> from collections import deque >>> stk = deque() >>> stk.append(4) >>> stk.append(3) >>> stk.append(7) >>> stk.append(2) >>> stk.append(9) >>> stk deque([4, 3, 7, 2,9]) >>> stk.pop() 9
Redovi
Red je struktura podataka po principu „prvi ušao-prvi izašao“ (FIFO). Elementi se dodaju na kraj reda i uklanjaju sa početka reda (glavni kraj reda), kao što je prikazano:
Struktura podataka reda se može implementirati pomoću `deque`:
- dodavanje elemenata na kraj reda korišćenjem `append()`
- korišćenje metode `popleft()` za uklanjanje elementa sa početka reda
>>> from collections import deque >>> q = deque() >>> q.append(4) >>> q.append(3) >>> q.append(7) >>> q.append(2) >>> q.append(9) >>> q.popleft() 4
Gomile
U ovom odeljku biće reči o binarnim gomilama, sa fokusom na minimalne gomile.
Minimalna gomila je kompletno binarno stablo. Razmotrimo šta tačno znači kompletno binarno stablo:
- Binarno stablo je struktura podataka u vidu stabla, gde svaki čvor ima najviše dva podređena čvora, i gde je svaki čvor manji od svojih potomaka.
- Termin „kompletno“ znači da je stablo potpuno popunjeno, sa mogućim izuzetkom poslednjeg nivoa. Ukoliko je poslednji nivo delimično popunjen, onda se popunjava sa leva na desno.
Zato što svaki čvor ima najviše dva podređena čvora, i ispunjava uslov da je manji od svog deteta, koren je minimalni element u minimalnoj gomili.
Primer minimalne gomile:
U Python-u, modul `heapq` pomaže pri konstrukciji gomila i obavljanju operacija nad njima. Uvezimo potrebne funkcije iz `heapq`:
>>> from heapq import heapify, heappush, heappop
Ukoliko imate listu ili neki drugi iterabilni objekat, moguće je konstruisati gomilu pozivom `heapify()`:
>>> nums = [11,8,12,3,7,9,10] >>> heapify(nums)
Indeksiranje prvog elementa omogućava proveru da li je to minimalni element:
>>> nums[0] 3
Sada, ukoliko se doda element u gomilu, čvorovi će biti preuređeni tako da zadovoljavaju uslov minimalne gomile.
>>> heappush(nums,1)
Pošto je dodata vrednost 1 (1 < 3), `nums[0]` sada vraća 1, koji je sada minimalni element (i osnovni čvor).
>>> nums[0] 1
Uklanjanje elemenata iz minimalne gomile se vrši pozivom funkcije `heappop()`, kao što je prikazano:
>>> while nums: ... print(heappop(nums)) ...
# Output 1 3 7 8 9 10 11 12
Maksimalne gomile u Python-u
Sada kada je minimalna gomila razjašnjena, možete li pretpostaviti kako se može implementirati maksimalna gomila?
Pa, implementacija minimalne gomile se može konvertovati u maksimalnu gomilu množenjem svakog broja sa -1. Negirani brojevi raspoređeni u minimalnu gomilu su ekvivalentni originalnim brojevima raspoređenim u maksimalnu gomilu.
U Python implementaciji, elementi se mogu pomnožiti sa -1 prilikom dodavanja u gomilu korišćenjem `heappush()`:
>>> maxHeap = [] >>> heappush(maxHeap,-2) >>> heappush(maxHeap,-5) >>> heappush(maxHeap,-7)
Osnovni čvor – pomnožen sa -1 – biće maksimalni element.
>>> -1*maxHeap[0] 7
Prilikom uklanjanja elemenata iz gomile, koristi se `heappop()` i množi se sa -1 radi vraćanja originalne vrednosti:
>>> while maxHeap: ... print(-1*heappop(maxHeap)) ...
# Output 7 5 2
Prioritetni redovi
Završićemo diskusiju učenjem o strukturi podataka prioritetnog reda u Python-u.
Znamo da se u redu elementi uklanjaju istim redosledom kojim su ušli u red. Međutim, prioritetni red obrađuje elemente prema prioritetu – što je veoma korisno za aplikacije poput planiranja. Stoga, u bilo kom trenutku se vraća element sa najvišim prioritetom.
Za definisanje prioriteta mogu se koristiti ključevi. U ovom slučaju će se koristiti numeričke težine za ključeve.
Kako implementirati prioritetne redove koristeći Heapq
Sledi implementacija prioritetnog reda korišćenjem `heapq` i Python liste:
>>> from heapq import heappush,heappop >>> pq = [] >>> heappush(pq,(2,'write')) >>> heappush(pq,(1,'read')) >>> heappush(pq,(3,'code')) >>> while pq: ... print(heappop(pq)) ...
Prilikom uklanjanja elemenata, red prvo obrađuje element sa najvišim prioritetom (1, ‘read’), zatim (2, ‘write’), i na kraju (3, ‘code’).
# Output (1, 'read') (2, 'write') (3, 'code')
Kako implementirati prioritetne redove koristeći PriorityQueue
Za implementaciju prioritetnog reda, može se koristiti i klasa `PriorityQueue` iz modula `queue`. Ova klasa takođe interno koristi gomilu.
Sledi ekvivalentna implementacija prioritetnog reda korišćenjem `PriorityQueue`:
>>> from queue import PriorityQueue >>> pq = PriorityQueue() >>> pq.put((2,'write')) >>> pq.put((1,'read')) >>> pq.put((3,'code')) >>> pq <queue.PriorityQueue object at 0x00BDE730> >>> while not pq.empty(): ... print(pq.get()) ...
# Output (1, 'read') (2, 'write') (3, 'code')
Sumiranje
U ovom vodiču ste naučili o različitim ugrađenim strukturama podataka u Python-u. Takođe su pregledane raznovrsne operacije koje ove strukture podataka podržavaju – kao i ugrađene metode za iste.
Zatim su razmotrene druge strukture podataka kao što su stekovi, redovi i prioritetni redovi – kao i njihova Python implementacija korišćenjem funkcionalnosti iz modula `collections`.
Nakon ovoga, preporučuje se da pogledate listu Python projekata namenjenih početnicima.