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

Kapitoly

Mýtus o najrýchlejšom algoritme

Časová a pamäťová zložitosť

Flexibilné spájané zoznamy

Merge Sort: Poriadkumilovný pedant

Quick Sort: Rýchly hazardér

Súboj titanov: Kedy ktorý použiť?

Skratka k rýchlosti: Hašovanie

Grafy - mapy vzťahov

Strom je špeciálny graf

Prechádzka korunami stromov

Praktické využitie a vyhľadávanie

Záverečné zhrnutie

Přepis

Filip: Väčšina študentov si myslí, že pri triedení dát je najlepší vždy ten najrýchlejší algoritmus. Znie to logicky, však? No v skutočnosti… to vôbec nie je pravda. Niekedy je ten zdanlivo pomalší algoritmus oveľa lepšou voľbou.

Tereza: Presne tak, Filip! Je to jeden z najväčších mýtov v informatike. Rýchlosť nie je všetko.

Filip: Vitajte pri Studyfi Podcast, kde búrame presne takéto mýty a pomáhame vám uspieť na skúškach.

Filip: Dobre, Tereza, tak poďme na to. Ak nie je najdôležitejšia len rýchlosť, čo ešte musíme sledovať?

Tereza: Sledujeme dve hlavné veci: časovú a pamäťovú zložitosť. Predstav si, že máš upratať izbu. Časová zložitosť je, ako dlho ti to bude trvať. A pamäťová zložitosť je, koľko ďalších krabíc potrebuješ na dočasné odloženie vecí, kým upratuješ.

Filip: Tomu rozumiem. Čiže niektoré algoritmy sú rýchle, ale urobia obrovský neporiadok – potrebujú veľa pamäte.

Tereza: Presne! Tento „čas“ a „neporiadok“ meriame pomocou takzvanej O notácie. Napríklad O(n) znamená, že čas rastie priamo úmerne s počtom prvkov. O(n²) je už oveľa horšie – tam čas rastie kvadraticky. A potom je tu O(log n), čo je super rýchle.

Filip: A cieľom je mať čo najlepšiu zložitosť, však? Ideálne O(1), teda konštantnú, kde čas nezávisí od počtu prvkov.

Tereza: Presne tak. Ale to je skôr sen. Pri triedení je magickým číslom O(n log n). Čokoľvek lepšie je pre porovnávacie triediace algoritmy v podstate nemožné.

Filip: Dobre, poďme sa pozrieť na konkrétne dátové štruktúry. Čo taký spájaný zoznam? Vždy mi to prišlo trochu abstraktné.

Tereza: Vôbec nie je! Predstav si to ako hľadanie pokladu, kde každá indícia ti povie, kde je ukrytá tá ďalšia. Spájaný zoznam je reťaz prvkov, kde každý prvok, alebo vrchol, obsahuje dáta a odkaz na ďalší prvok.

Filip: Takže prvky nemusia byť uložené v pamäti vedľa seba ako v bežnom poli?

Tereza: Presne tak. To je ich najväčšia výhoda – dynamická veľkosť. Môžeš ľahko pridať alebo odstrániť prvok bez toho, aby si musel presúvať všetko ostatné. Nevýhodou je, že ak chceš nájsť desiaty prvok, musíš prejsť cez deväť predchádzajúcich. Nemôžeš tam len tak skočiť.

Filip: Existujú aj iné typy?

Tereza: Áno! Dvojito spájaný zoznam je ako obojsmerná ulica – každý prvok pozná svojho predchodcu aj nasledovníka. A cyklický spájaný zoznam je ako kolotoč – posledný prvok ukazuje späť na prvý. Nikdy sa nezastaví!

Filip: Dobre, poďme na triedenie. Spomínala si O(n log n) ako skvelý čas. Ktorý algoritmus ho dosahuje?

Tereza: Jeden z najznámejších je Merge Sort. Funguje na princípe „rozdeľuj a panuj“. Je to taký extrémne organizovaný pedant.

Filip: Ako to myslíš?

Tereza: Predstav si, že máš kopu kariet. Merge Sort ich rozdelí na dve polovičky. Potom každú polovičku znova na polovičky, a tak ďalej, až kým ti neostanú len jednotlivé karty. A potom ich začne spájať dokopy, ale už v správnom, utriedenom poradí.

Filip: To znie… metodicky. A zložitosť?

Tereza: Vždy, ale naozaj vždy, je to O(n log n). V najlepšom, priemernom aj najhoršom prípade. Je veľmi spoľahlivý a stabilný, čo znamená, že prvky s rovnakou hodnotou si zachovajú pôvodné poradie.

Filip: Aký je teda háčik? Znie to dokonale.

Tereza: Ten neporiadok, o ktorom sme hovorili. Pamäťová zložitosť. Merge Sort potrebuje dodatočné pole, ktoré je rovnako veľké ako to pôvodné. Takže jeho pamäťová zložitosť je O(n). Pri obrovských dátach to môže byť problém.

Filip: Takže ak je Merge Sort pedant, aký je jeho konkurent, Quick Sort?

Tereza: Quick Sort je taký inteligentný, ale trochu chaotický hazardér. Je tiež založený na princípe „rozdeľuj a panuj“, ale robí to inak.

Filip: Ako?

Tereza: Vyberie si jeden prvok, ktorému hovoríme pivot. Potom všetky ostatné prvky rozdelí na dve kôpky – menšie ako pivot a väčšie ako pivot. A tento proces opakuje rekurzívne na oboch kôpkach.

Filip: A prečo hazardér?

Tereza: Pretože jeho výkon extrémne závisí od výberu pivota. Ak ho vyberieš dobre, v priemere je ešte rýchlejší ako Merge Sort v praxi. Jeho zložitosť je tiež O(n log n). Ale ak máš smolu a vyberieš veľmi zlého pivota – napríklad najmenší alebo najväčší prvok v už utriedenom poli – jeho časová zložitosť padá na katastrofálnych O(n²).

Filip: A čo pamäť? Je lepší ako Merge Sort?

Tereza: Oveľa! Quick Sort je takzvaný in-place algoritmus. Nepotrebuje veľa extra pamäte, len O(log n) na rekurzívne volania. Preto sa v praxi používa veľmi často na interné triedenie, teda keď sa dáta zmestia do pamäte.

Filip: Dobre, poďme to zhrnúť. Keby som si mal vybrať, kedy je lepší Merge Sort a kedy Quick Sort?

Tereza: Je to jednoduché. Potrebuješ zaručený výkon a stabilitu, napríklad pri triedení obrovského súboru na disku, a nevadí ti použiť viac pamäte? Zvoľ Merge Sort.

Filip: A Quick Sort?

Tereza: Chceš najvyššiu možnú rýchlosť v priemernom prípade, triediš dáta v pamäti a si ochotný riskovať ten malinký, teoretický scenár najhoršieho prípadu? Quick Sort je tvoj šampión.

Filip: Takže neexistuje jeden „najlepší“ algoritmus. Závisí to od kontextu. To je tá pointa z úvodu!

Tereza: Presne tak! Výber správnej dátovej štruktúry a algoritmu je ako výber správneho nástroja. Kladivom tiež nezašraubuješ skrutku.

Filip: Aj keď som to už párkrát skúsil.

Filip: Existuje ešte nejaký spôsob, ako veci zrýchliť, hlavne pri vyhľadávaní?

Tereza: A ako! Volá sa to hašovanie. Je to úplne iný prístup. Namiesto porovnávania prvkov vezmeme kľúč – napríklad meno študenta – a pomocou špeciálnej hašovacej funkcie mu priamo vypočítame jeho „adresu“ v tabuľke.

Filip: Takže nemusím prechádzať celý zoznam, aby som niekoho našiel? Len vypočítam index a idem priamo tam?

Tereza: Presne! V ideálnom prípade je vyhľadávanie, vkladanie aj mazanie takmer okamžité. Je to O(1) – ten náš sen o konštantnom čase.

Filip: Znie to až príliš dobre na to, aby to bola pravda. Kde je problém?

Tereza: Kolízie. Niekedy sa stane, že hašovacia funkcia priradí dvom rôznym kľúčom rovnaký index. Predstav si, že dvaja ľudia dostanú rovnaké číslo skrinky.

Filip: A čo potom?

Tereza: Musíme to riešiť. Najčastejšie sa používa takzvané reťazenie. Na každej pozícii v tabuľke nie je len jeden prvok, ale spájaný zoznam. Ak nastane kolízia, nový prvok jednoducho pridáme do tohto zoznamu. Aj s kolíziami je hašovanie neuveriteľne efektívne.

Filip: Fascinujúce. Takže od lineárnych zoznamov, cez inteligentné triedenie, až po magické hašovanie. Svet dátových štruktúr je naozaj pestrý.

Filip: Takže po spojkových zoznamoch a poliach, ktoré boli dosť lineárne, sa dnes pozrieme na niečo, čo mi príde oveľa... chaotickejšie. Stromy a grafy. Tereza, kde začať?

Tereza: Chaotické sa to len zdá, Filip. V skutočnosti je v tom krásny poriadok. Začnime grafmi. Predstav si ich ako mapu vzťahov medzi objektmi.

Filip: Mapu vzťahov? Ako napríklad... mapa priateľov na sociálnej sieti?

Tereza: Presne tak! To je skvelý príklad. Matematicky je graf len súbor dvoch vecí. Máme množinu vrcholov, čo sú v tvojom príklade ľudia... a množinu hrán, čo sú tie priateľstvá medzi nimi.

Filip: Chápem. Takže vrcholy sú objekty a hrany sú spojenia.

Tereza: Áno. A tie hrany môžu byť dvojaké. V neorientovanom grafe je hrana medzi mnou a tebou obojsmerná – sme priatelia. Je to ako obojsmerná ulica.

Filip: Logické. A ten druhý typ?

Tereza: To je orientovaný graf. Tam má hrana smer. Predstav si Twitter alebo Instagram. Ja môžem sledovať teba, ale ty mňa nemusíš. Spojenie ide len jedným smerom, A → B. To sa hodí aj pri plánovaní úloh, kde jedna úloha musí skončiť, aby druhá mohla začať.

Filip: Aha, takže závislosti. To dáva zmysel. A ako si počítač pamätá, kto je s kým spojený?

Tereza: Najčastejšie pomocou zoznamu susedov. Každý vrchol má jednoducho zoznam vrcholov, s ktorými je priamo spojený. Je to pamäťovo úsporné, aj keď zistiť, či existuje konkrétna hrana, môže trvať o chvíľku dlhšie.

Filip: Dobre, grafom rozumiem. A čo sú potom stromy? Musím si doniesť pílku?

Tereza: Nie, tú nechaj doma. Strom je v informatike len špeciálny, veľmi usporiadaný typ grafu. Má dve kľúčové vlastnosti. Je súvislý, takže sa z každého vrcholu dostaneš do každého iného... a je acyklický.

Filip: Acyklický? To znamená...?

Tereza: Že v ňom nie sú žiadne cykly. Nemôžeš ísť z vrcholu A do B, potom do C a zrazu sa vrátiť späť do A. Vždy ideš len jedným smerom, ako po konároch stromu, nikdy sa nevrátiš v kruhu.

Filip: Ako v rodokmeni. Tam sa tiež nevraciaš v kruhoch. Dúfam.

Tereza: Presne! A rovnako ako rodokmeň, aj dátový strom má jeden špeciálny vrchol na samom vrchu – voláme ho koreň. Vrcholy pod ním sú jeho potomkovia a on je ich rodič.

Filip: Super analógia. A existujú aj rôzne druhy stromov?

Tereza: Množstvo, ale najznámejší a najpoužívanejší je binárny strom. Tam platí jednoduché pravidlo: každý rodič môže mať najviac dvoch potomkov. Jedného ľavého a jedného pravého.

Filip: Dobre, máme binárny strom. Ako v ňom ale niečo nájdem? Alebo ako ho celý vypíšem?

Tereza: Na to slúži takzvané prechádzanie stromu. Existujú tri základné spôsoby: preorder, inorder a postorder. Líšia sa len v poradí, v akom navštevuješ koreň, ľavý podstrom a pravý podstrom.

Filip: To znie dosť abstraktne. Načo je dobré mať tri rôzne spôsoby?

Tereza: Každý sa hodí na niečo iné. Napríklad inorder ti pri správne usporiadanom strome vráti všetky prvky pekne zoradené od najmenšieho po najväčší. Je to extrémne užitočné.

Filip: A čo znamená "správne usporiadaný" strom?

Tereza: To je dôležitá otázka! Ak chceme, aby bol strom efektívny, mal by byť vyvážený. To znamená, že jeho ľavá a pravá strana sú približne rovnako hlboké.

Filip: A čo sa stane, ak nie je?

Tereza: Predstav si, že do stromu vkladáš už zoradené čísla: 1, 2, 3, 4, 5. Skončíš so stromom, ktorý vyzerá ako dlhý zoznam – každý prvok má len jedného potomka. A v takom prípade strácaš všetky výhody. Vyhľadávanie je potom pomalé, skoro ako v obyčajnom poli.

Filip: Takže musíme dbať na to, aby strom nebol jednostranný. Znie to ako výchova detí.

Tereza: Niečo na tom bude. Našťastie existujú samovyvažovacie stromy, napríklad AVL stromy, ktoré si pri vkladaní a mazaní prvkov svoju štruktúru automaticky upravujú, aby zostali efektívne.

Filip: Kde všade sa s takýmito stromami a grafmi v praxi stretnem?

Tereza: Všade. Grafy modelujú dopravné a počítačové siete, sociálne siete. Stromy zase organizujú dáta v databázach alebo reprezentujú súborový systém v tvojom počítači – tie priečinky a súbory.

Filip: A spomínala si nejaké kódovanie...

Tereza: Áno, Huffmanovo kódovanie! To je geniálne využitie binárnych stromov na kompresiu dát. Myšlienka je jednoduchá: znakom, ktoré sa v texte vyskytujú často, priradíme krátky kód. A tým menej častým dlhší. Tým sa celková veľkosť súboru zmenší.

Filip: To je super! A čo to vyhľadávanie, ktoré si spomínala?

Tereza: Keď máš dáta pekne usporiadané, napríklad v poli alebo vyváženom strome, môžeš použiť binárne vyhľadávanie. Namiesto toho, aby si prechádzal všetko od začiatku do konca... to je sekvenčné vyhľadávanie...

Filip: ...čo je strašne pomalé pri veľkých dátach.

Tereza: Presne. Pri binárnom vyhľadávaní sa pozrieš do stredu. Ak je hľadaný prvok menší, zahodíš celú pravú polovicu a hľadáš len v ľavej. A takto to opakuješ. Je to neuveriteľne rýchle. Časová zložitosť je len O(log n).

Filip: Páni. Takže, ak to mám zhrnúť. Prešli sme si všetko od základných polí, cez flexibilné spojkové zoznamy, až po dnešné stromy a grafy, ktoré modelujú zložité vzťahy a hierarchie.

Tereza: Presne tak. Kľúčový poznatok je, že neexistuje jedna najlepšia dátová štruktúra. Vždy záleží na konkrétnom probléme, ktorý riešiš. Výber správnej štruktúry ti môže ušetriť obrovské množstvo času a výpočtového výkonu.

Filip: A to bol, zdá sa, posledný kúsok našej skladačky o dátových štruktúrach. Tereza, veľmi pekne ti ďakujem za všetky vysvetlenia. Myslím, že si nám to všetkým poriadne osvetlila.

Tereza: Ja ďakujem za pozvanie, Filip. Bola to radosť. A pamätajte, informatika nie je mágia, je to len veľmi šikovne poskladaná logika.

Filip: To je skvelé záverečné slovo. Týmto sa s vami, milí poslucháči, lúčime. Dúfame, že ste si z našej série odniesli veľa nových poznatkov. Toto bol váš Studyfi Podcast. Dopočutia nabudúce!