Podcast na Datové struktury

Kapitoly

Úvod do datových struktur

Abstraktní typ vs. Struktura

Velké O: Měření rychlosti

Pole: Základní stavební kámen

Přepis

Lukáš: …počkat, takže celé datové struktury jsou vlastně jenom o tom, jak si efektivně uklidit v pokojíčku? To je neuvěřitelné.

Lucie: Přesně tak! Jen ten pokojíček je paměť počítače a místo hraček uklízíš data. Cílem je, abys všechno rychle našel a nemusel přehrabovat celý pokoj pokaždé, když něco hledáš.

Lukáš: Dobře, tohle jsem vůbec netušil – a myslím, že to musí slyšet všichni. Posloucháte Studyfi Podcast. Takže Lucie, proč je to tak klíčové?

Lucie: Protože bez správného systému, bez správné datové struktury, by i ten nejrychlejší počítač na světě byl zoufale pomalý. Představ si Google, který by na tvůj dotaz odpovídal hodinu. To by nikdo nepoužíval.

Lukáš: Dobře, chápu. Ale často slyším dva pojmy: abstraktní datový typ a datová struktura. Není to to samé?

Lucie: Skvělá otázka! Není, ale úzce to souvisí. Představ si to jako recept. Abstraktní datový typ, neboli ADT, je jenom nápad – „Chci upéct bábovku.“ Definuje, co bys měl umět udělat: přidat ingredience, zamíchat, upéct.

Lukáš: Rozumím, ADT je tedy cíl. Co je potom ta struktura?

Lucie: Datová struktura je ten konkrétní recept. Říká ti, jak to přesně udělat. Vezmeš pole na mouku a cukr, spojový seznam na rozinky… Je to konkrétní implementace toho nápadu. ADT je „co“, struktura je „jak“.

Lukáš: A jak poznáme, který „recept“ je nejlepší? Některé jsou přece rychlejší než jiné.

Lucie: Přesně! A k tomu používáme něco, čemu se říká asymptotická notace, nejčastěji Velké O. Zní to složitě, ale je to jen způsob, jak měřit, o kolik víc práce musí počítač udělat, když přidáš víc dat.

Lukáš: Takže je to taková známka za efektivitu?

Lucie: V podstatě ano. Třeba složitost O(1) je sen každého programátora. Znamená to, že operace trvá pořád stejně, ať máš v datech pět položek, nebo pět milionů. Je to konstantní čas.

Lukáš: A na druhé straně spektra?

Lucie: Tam jsou věci jako O(n), kde čas roste lineárně s počtem prvků, nebo ještě hůř, O(n²), kde se doba běhu s každým prvkem navíc dramaticky prodlužuje. Tomu se snažíme vyhýbat.

Lukáš: Pojďme se podívat na nějaký konkrétní příklad. Co je takový nejzákladnější stavební kámen?

Lucie: Určitě pole, anglicky array. Je to prostě souvislý blok paměti, rozdělený na stejně velké přihrádky. Každá má svůj index, tedy číslo, začínající od nuly.

Lukáš: To zní jako ta O(1) věc, o které jsi mluvila. Když znám číslo přihrádky, tak tam sáhnu rovnou, ne?

Lucie: Přesně tak! Přístup k prvku v poli má složitost O(1), což je jeho obrovská výhoda. Počítač si adresu jednoduše vypočítá. Ale má to i háček.

Lukáš: A to je?

Lucie: Zkus přidat prvek doprostřed. Musíš všechny prvky za ním posunout o jedno místo dál. A to už je operace se složitostí O(n). Stejné je to s mazáním. Takže pole je skvělé na čtení, ale ne tak moc na časté změny uprostřed.

Lukáš: Takže výběr struktury je vždycky nějaký kompromis. Díky moc, Lucie, to bylo super srozumitelné!

Lucie: Rádo se stalo! Hlavní je pamatovat si, že neexistuje jedna nejlepší struktura pro všechno. Vždy záleží na tom, co potřebujete dělat.