Podcast o Dynamické dátové štruktúry a algoritmy

Kapitoly

Od chaosu k poriadku

Stromy a ich vetvy

Prechádzky stromami

Huffmanovo kúzlo

Grafy a sociálne siete

Zoznamy, polia a množiny

Čas sú peniaze... a operácie

Súboj triediacich titánov

Hľadanie ihly v kope sena

Zhrnutie a na záver

Přepis

Filip: Predstavte si študenta, volajme ho Martin. Pripravuje sa na veľký test z dejepisu – desiatky dátumov, udalostí, kráľov a zmlúv. Jeho poznámky sú jeden obrovský, chaotický dokument. Všetko je tam, ale nájsť súvislosť medzi bitkou pri Moháči a nástupom Habsburgovcov mu trvá večnosť. Martin je stratený.

Sofia: A presne tu prichádza na scénu niečo, čo znie strašne technicky, ale v skutočnosti je to Martinov záchranca — dátové štruktúry. Počúvate Studyfi Podcast.

Filip: Dátové štruktúry? Znie to ako niečo pre programátorov, nie pre študenta s dejepisom. Čo to vlastne je?

Sofia: V podstate je to len super organizovaný spôsob, ako ukladať informácie, aby sme v nich vedeli rýchlo a ľahko nájsť to, čo potrebujeme. Namiesto jedného dlhého zoznamu si Martin mohol svoje poznámky usporiadať napríklad ako strom. Zaujíma ťa, ako by to vyzeralo?

Filip: Určite! Potrebujem vedieť, ako sa Martin dostal z toho chaosu.

Sofia: Dobre, tak si predstav strom. Úplne hore je koreň, povedzme „Stredoveká Európa“. Z neho vyrastajú vetvy ako „Francúzsko“, „Anglicko“, „Uhorsko“. Každá z týchto vetiev má ďalšie menšie vetvičky – kráľov, dôležité udalosti a tak ďalej.

Filip: Aha! Takže ak chce nájsť niečo o Ľudovítovi XIV., ide rovno na vetvu „Francúzsko“ a nemusí prechádzať celé anglické dejiny.

Sofia: Presne tak! Strom je hierarchická dátová štruktúra. Tvorí ho súvislý acyklický graf. To znie zložito, ale znamená to len to, že medzi ľubovoľnými dvoma bodmi existuje cesta a nie sú tam žiadne cykly, ktoré by ťa viedli dookola.

Filip: Takže ako keby neexistovala cesta z vetvičky „Ľudovít XIV.“ naspäť ku koreňu „Stredoveká Európa“ okrem tej, ktorou prišiel. Rozumiem. A čo tie pojmy ako rodič a potomok?

Sofia: Jednoduché. „Francúzsko“ je potomkom „Stredovekej Európy“, a zároveň je rodičom pre „Ľudovíta XIV.“. Je to ako rodokmeň. A najpoužívanejší typ je binárny strom, kde každý rodič môže mať maximálne dvoch potomkov – ľavého a pravého. To sa skvele hodí na rozhodovanie a triedenie!

Filip: Takže ak by sme triedili čísla, všetky menšie by išli naľavo a väčšie napravo?

Sofia: Presne! Tomu sa hovorí binárny vyhľadávací strom. Všetky prvky v ľavom podstrome sú menšie ako koreň a všetky v pravom sú väčšie. To extrémne zrýchľuje vyhľadávanie.

Filip: To znie super efektívne. Ale čo ak vkladám čísla postupne, napríklad 1, 2, 3, 4, 5?

Sofia: Dobrá otázka! Vtedy sa nám strom zvrhne na jednu dlhú, nevyváženú vetvu. V podstate sa z neho stane obyčajný zoznam a strácame všetky výhody. Hľadanie potom trvá rovnako dlho, ako keby sme prechádzali zoznam od začiatku do konca.

Filip: A to je zlé. Existuje na to nejaké riešenie?

Sofia: Samozrejme, existujú takzvané vyvážené stromy, napríklad AVL stromy, ktoré sa po každom vložení alebo odstránení prvku samy „preorganizujú“, aby si udržali nízku výšku a efektívne vyhľadávanie s časovou zložitosťou O(log n).

Filip: Dobre, strom máme postavený. Ako v ňom ale systematicky prečítame všetky údaje? Nemôžem len tak skákať z vetvy na vetvu.

Sofia: Na to máme presne stanovené postupy, ktorým hovoríme prechádzanie stromu. Najznámejšie sú tri: Preorder, Inorder a Postorder.

Filip: To znie ako nejaké zaklínadlá.

Sofia: Trochu. Ale je to logické. Pri Preorder prechádzaní najprv spracuješ koreň, potom celý ľavý podstrom a nakoniec pravý podstrom. Je to ako keby si robil zoznam obsahu knihy – najprv názov kapitoly, potom jej podkapitoly.

Filip: Okej, to dáva zmysel. A čo Inorder?

Sofia: Inorder ide na to inak. Najprv prejde celý ľavý podstrom, potom spracuje koreň a až potom pravý podstrom. A vieš, čo je na tom super? Ak máš binárny vyhľadávací strom, Inorder ti vráti všetky prvky pekne usporiadané od najmenšieho po najväčší.

Filip: Wow, takže to je vlastne automatické triedenie! To je šikovné. A čo ten posledný, Postorder?

Sofia: Postorder si necháva prácu s koreňom na úplný koniec. Najprv spracuje ľavý podstrom, potom pravý a až úplne nakoniec samotný koreň. To sa hodí napríklad vtedy, keď potrebuješ najprv spracovať všetky závislosti, a až potom hlavnú úlohu.

Filip: Stromy teda nie sú len na organizáciu, ale aj na triedenie. Na čo ešte sa používajú?

Sofia: Používajú sa napríklad pri kompresii dát. Počul si už o Huffmanovom kóde?

Filip: Matne. Niečo s efektívnym ukladaním textu?

Sofia: Presne. Základná myšlienka je geniálne jednoduchá: znaky, ktoré sa v texte vyskytujú často, napríklad písmeno 'a' alebo 'e', dostanú kratší kód. Znaky, ktoré sú zriedkavé, ako 'q' alebo 'x', dostanú dlhší kód.

Filip: Takže šetríme miesto na najčastejších znakoch. Ako to ale funguje v praxi?

Sofia: Na vytvorenie kódu sa používa špeciálny binárny strom, Huffmanov strom. Najprv zistíme frekvenciu všetkých znakov. Každý znak je na začiatku samostatný lístok stromu. Potom postupne spájame dva vrcholy s najmenšou frekvenciou do nového, spoločného vrcholu. Opakujeme to, kým nám nevznikne jeden kompletný strom.

Filip: A kde je ten kód?

Sofia: Kód vznikne prechádzaním stromu od koreňa ku každému lístku. Dohodneme sa, že cesta doľava znamená 0 a cesta doprava znamená 1. Kód pre písmeno 'a' je potom postupnosť núl a jednotiek na ceste od koreňa k lístku 'a'. A keďže žiadny kód nie je začiatkom iného kódu, vieme správu jednoznačne dekódovať.

Filip: Hovorila si, že strom je špeciálny typ grafu. Čo je teda graf vo všeobecnosti?

Sofia: Predstav si mapu miest a ciest medzi nimi. Mestá sú vrcholy a cesty sú hrany. To je graf. Matematicky je to dvojica G=(V,E), kde V je množina vrcholov a E je množina hrán, ktoré ich spájajú. Grafy reprezentujú vzťahy medzi objektmi.

Filip: A sú rôzne typy, však? Cesta medzi Bratislavou a Trnavou funguje oboma smermi.

Sofia: Áno, to je neorientovaný graf. Hrany nemajú smer. Ale predstav si Instagram. To, že ty sleduješ nejakú celebritu, neznamená, že ona sleduje teba.

Filip: To teda rozhodne nie. Čiže to je orientovaný graf?

Sofia: Presne! Spojenie má smer. Z vrcholu A vedie hrana do vrcholu B, ale naspäť viesť nemusí. Používa sa to pri sociálnych sieťach, závislostiach úloh, alebo napríklad pri jednosmerkách v meste.

Filip: A ako sa v takom grafe nestratíme? Ako ho vieme celý prejsť?

Sofia: Na to máme dva hlavné algoritmy. Prvý je DFS, čiže prehľadávanie do hĺbky. To je ako ísť v bludisku stále doľava. Ideš po jednej ceste tak hlboko, ako sa len dá, a až keď narazíš na slepú uličku, vrátiš sa a skúsiš inú odbočku.

Filip: A ten druhý?

Sofia: Druhý je BFS, prehľadávanie do šírky. To je ako hodiť kameň do vody. Najprv preskúmaš všetkých priamych susedov, potom susedov tvojich susedov, a tak ďalej, vrstvu po vrstve. Je to super na nájdenie najkratšej cesty medzi dvoma vrcholmi.

Filip: Dobre, stromy a grafy sú super na zložité vzťahy. Ale čo niečo jednoduchšie? Ako by som si uložil len zoznam nákupu?

Sofia: Na to by ti stačil spájaný zoznam. Namiesto toho, aby boli položky uložené v pamäti za sebou ako v poli, každý prvok je samostatný uzol, ktorý obsahuje dáta a odkaz na ďalší prvok. Je to ako reťaz.

Filip: Takže viem ľahko pridať alebo odobrať článok reťaze bez toho, aby som musel všetko posúvať.

Sofia: Presne tak. Je to veľmi flexibilné. Existuje aj dvojito spájaný zoznam, kde každý uzol ukazuje aj na predchádzajúci prvok, takže sa vieš pohybovať oboma smermi. A dokonca cyklický, kde posledný prvok ukazuje späť na prvý – to sa hodí napríklad v hrách.

Filip: A čo množiny? V matematike množina nemôže mať duplicitné prvky. Ako to funguje v informatike?

Sofia: Úplne rovnako. Množina je abstraktný dátový typ, ktorý obsahuje neusporiadané prvky bez opakovania. Implementovať ju môžeme rôzne. Napríklad pomocou poľa, ale pri vkladaní musíme vždy skontrolovať, či tam prvok už nie je.

Filip: To znie pomaly pri veľkých množinách.

Sofia: Aj je. Preto sa často používajú už spomínané binárne vyhľadávacie stromy, lebo v nich sa duplicita odhalí veľmi rýchlo. Alebo, ak pracujeme s malým rozsahom čísel, môžeme použiť bitový vektor. Je to pole bitov, kde každý index reprezentuje jedno číslo. Ak je bit na indexe 5 nastavený na 1, znamená to, že číslo 5 je v množine. Ak je 0, tak nie je.

Filip: To je geniálne! Operácie ako prienik alebo zjednotenie množín musia byť potom bleskurýchle.

Sofia: Sú. Je to len o logických operáciách s bitmi. Každá štruktúra má svoje výhody a nevýhody. Kľúčové je vybrať si tú správnu pre daný problém. Či už je to Martinov chaos v poznámkach, alebo plánovanie najkratšej trasy pre doručovateľa. Všetko je to o správnej organizácii dát.

Filip: A tým sme uzavreli statické polia. Ale čo ak nevieme, koľko dát budeme mať? To znie ako problém.

Sofia: Presne tak, Filip. A na to máme dynamické dátové štruktúry. Ich veľkosť sa môže meniť za behu programu. Môžeme prvky pridávať, odoberať... ako lego!

Filip: Takže sú flexibilnejšie. Ale ako si vybrať tú správnu štruktúru alebo algoritmus?

Sofia: Tu prichádza na rad efektivita. Sledujeme, ako sa mení čas behu, keď zväčšujeme vstup. Hovoríme tomu asymptotická zložitosť, najčastejšie ju označujeme ako 'Veľké O'.

Filip: 'Veľké O'? To znie dôležito. Čo to znamená?

Sofia: Predstav si to ako hodnotenie rýchlosti. O(1) je superrýchle, konštantné. O(n) je lineárne – rastie priamo s dátami. Ale napríklad O(n²) je už dosť pomalé pri veľkých vstupoch. Tam sa algoritmus poriadne zapotí.

Filip: Rozumiem. A okrem času je dôležitá aj pamäť, však?

Sofia: Áno, to je pamäťová zložitosť. Niektoré algoritmy, takzvané 'in-place', potrebujú len minimum extra pamäte, čo je skvelé.

Filip: Poďme na konkrétne príklady. Často počujem o triediacich algoritmoch. Ktoré sú tie najznámejšie?

Sofia: Dvaja hlavní rivali sú Merge Sort a Quick Sort. Obidva fungujú na princípe 'rozdeľ a panuj'.

Filip: Rozdeľ a panuj? To znie ako nejaká stratégia z historického filmu.

Sofia: V podstate áno. Rozdelia problém na menšie, vyriešia ich a potom výsledky spoja. Merge Sort je veľmi stabilný a predvídateľný. Jeho zložitosť je vždy O(n log n).

Filip: A Quick Sort? Je naozaj taký 'quick'?

Sofia: V priemere áno, je extrémne rýchly. Ale má jednu slabinu. V najhoršom prípade môže jeho zložitosť klesnúť až na O(n²).

Filip: Takže v najhoršom prípade je Quick Sort... nie až taký Quick?

Sofia: Presne tak si to môžeš pamätať! Navyše potrebuje menej pamäte ako Merge Sort, preto sa často používa na triedenie v pamäti.

Filip: Dobre, triedenie máme. A čo vyhľadávanie? Ako nájsť jeden prvok v miliónoch?

Sofia: Na to je geniálna technika zvaná hašovanie. Je to ako mať čarovnú skrinku. Dáš jej kľúč a ona ti okamžite povie, kde je tvoj prvok uložený.

Filip: Okamžite? To znie ako O(1), tá superrýchla zložitosť.

Sofia: Takmer! Hašovacia funkcia prepočíta kľúč na index v tabuľke. Jediný problém môžu byť kolízie – keď dva rôzne kľúče ukážu na to isté miesto.

Filip: A čo potom?

Sofia: To riešime napríklad reťazením. Na tej pozícii jednoducho vytvoríme krátky zoznam prvkov. Je to elegantné a stále veľmi rýchle.

Filip: Perfektné. Takže od premenných, cez objekty až po zložité algoritmy... prešli sme si toho naozaj veľa. Dnešok bol skvelým zakončením.

Sofia: Súhlasím. Kľúčové je nebáť sa zložitosti a vedieť si vybrať správny nástroj pre daný problém. Či už je to rýchly Quick Sort alebo magické hašovanie.

Filip: Presne tak. Dúfam, že vám naša séria pomohla pochopiť základy programovania. Sofia, ďakujem ti veľmi pekne za všetky vysvetlenia.

Sofia: Aj ja ďakujem, Filip. Bola to radosť. A vám, milí poslucháči, držíme palce pri vašom programátorskom dobrodružstve!

Filip: Majte sa krásne a dopočutia nabudúce pri ďalšom podcaste od Studyfi!