Lekce 1 - Úvod do datových struktur
Už umíte napsat "Hello world"? Je čas posunout se dále. V tomto článku se vám pokusím trochu přiblížit použití a možnosti různých datových struktur.
- Co to je vlastně datová struktura?
- Jak zvolit tu správnou?
- Jak moc jim musím rozumět "zevnitř"?
Všechny tyto otázky si dnes zodpovíme. Článek předpokládá znalosti alespoň úvodu do algoritmizace a časové složitosti, které naleznete v článcích Úvod do teorie algoritmů a Výpočet časové složitosti.
Proč se zabývat uložením dat
Nyní jsme v situaci, kdy umíme napsat běžné aplikace a alespoň jednou jsme použili pole. Pokud chceme však psát větší programy, nejspíš budou obsahovat i více dat. O hodně více, než jsme sami schopní si ohlídat. Pamatujte, počítač by si měl vše pamatovat, ne vy. Představme si, že si chceme uložit něco kolem milionu čísel. Některá tam mohou být vícekrát, některá tam nemusí být ani jednou. V čem je uložit? To záleží na tom, jaké operace nad těmito čísly chceme provádět.
Čísla můžeme jednoduše uložit do pole nesetříděná a máme po
problému s ukládáním. Co když ale budeme chtít v poli najít nějaké
číslo? Třeba maximum? Není problém, projdeme pole. Víme, že v poli o
velikosti n najdeme maximum v čase O(n). Ale co když
budeme postupně maxima odebírat, např. odbavovat nejdéle čekající
uživatele? Jednak nám v poli budou vznikat díry a jednak pro každé
vyhledání maxima budeme muset pole prohledat znovu. Možná by bylo lepší
použít jinou strukturu. Jiný způsob, jak ukládat data.
Kterou strukturu kdy použít
Strukturu vybereme tedy podle toho, jaké operace bychom chtěli nejčastěji provádět nad danými daty. Jaké operace chceme? Například najít prvek, najít maximum/minimum, najít předchůdce prvku, vložit prvek, odstranit, seřadit prvky atd...
Proč jsou datové struktury důležité? To je snadné, uveďme si příklad.
Farmář a programátor
O práci v jedné firmě se na pozici programátora ucházejí dva lidé.
Jeden farmář a druhý programátor. Farmář
celý život pracuje s polem, umí v něm vyhledávat a dokáže napsat velmi
sofistikovaný kód, který pracuje s poli. Druhý uchazeč je slabý student
programování, který předevčírem nevěděl, co je to String a
na pracovní pohovor se v záchvatu zoufalství naučil několik datových
struktur. Oba dostali za úkol naprogramovat aplikaci, které se předá hromada
čísel a bude vyhledávat, zda mezi nimi bylo "Šťastné číslo".
Farmář hrdě postaví objektový návrh a vše nasype do pole. Chudák student v záchvatu zoufalství vytvoří vyhledávací strom a jakž takž mu funguje. Ale ejhle, i přes veškeré optimalizace je farmářův kód mnohem pomalejší. Student je okamžitě přijat a farmář zas sedá za traktor ke svým oblíbeným polím.
Základní operace
Níže naleznete tabulku, která ukazuje několik málo datových struktur, které si postupně představíme. Dále uvádí časové složitosti základních operací, které bychom po strukturách mohli chtít:
| struktura | vložení prvku | odstranění | obsahuje prvek | nalezení minima |
|---|---|---|---|---|
| pole | O(1) | O(n) | O(n) | O(n) |
| uspořádané pole | O(n) | O(n) | O(log n) | O(1) |
| binární vyhledávací strom | Θ(log n) | Θ(log n) | Θ(log n) | Θ(log n) |
| zásobník | O(1) | O(n) | O(n) | O(n) |
Seznam struktur
Stručně si představíme nejdůležitější datové struktury a uvedeme si jejich výhody a nevýhody. Je to však pouze inspirace, více v samostatných článcích.
Pole (Array)
Pole používáme kvůli jeho rychlé práci přes indexy prvků.
Klady a zápory
| + | - |
|---|---|
| jednoduché na vytvoření | třídění v O(n*log n) |
| jednoduché na použití | vyhledávání v O(n), popř. O(log n), pokud je
setříděné |
přímé indexování v O(1) |
Fronta a zásobník (Queue and Stack)
Frontu nebo zásobník používáme, pokud potřebujeme s prvky pracovat v pořadí v jakém byly přidány nebo v opačném. Fronta podporuje přístup FIFO (First In First Out, tedy první přidaný prvek je první na řadě).
Zásobník podporuje přístup LIFO (Last in First Out), tedy poslední přidaný prvek je první na řadě.
Klady a zápory
| + | - |
|---|---|
push/vložit prvek v O(1) |
nelze vkládat doprostřed |
pop/odebrat prvek v O(1) |
|
zobrazit vršek struktury O(1) |
Množina (Set)
Množiny zajišťují, že se v nich každý prvek nachází jen jednou. Její prvky jsou tedy unikátní.
Klady a zápory
| + | - |
|---|---|
| rychlá kontrola, zda obsahuje hodnotu | velmi limitované použití |
| bez duplicitních hodnot |
Halda (Heap)
Halda nám umožňuje instantně odebrat největší nebo nejmenší prvek.
Klady a zápory
| + | - |
|---|---|
najdi min/max O(1) |
vyhledávání O(n) |
vlož O(log n) |
odstranění prvku O(n) |
odstraň min/max O(log n) |
Binární vyhledávací strom (BST)
Binární vyhledávací strom nám umožní prvky rychle vyhledávat a optimalizuje jejich vkládání a mazání.
Klady a zápory
| + | - |
|---|---|
| udržuje "setříděnost" | složitější manipulace s prvky |
vložení v O(log n) |
|
odstranění v O(log n) |
Pro zvídavé
Pokud jste článek dočetli až sem, nejspíše vás opravdu zajímá, co
skrývají taje datových struktur. Existuje nepřeberné množství možností,
jak využít jejich sílu. Z fronty můžeme udělat prioritní frontu, neboli
frontu s předbíháním. Z množiny můžeme udělat uspořádanou množinu či
ji zobecnit na slovník. Navíc, pokud řešíte nějaký problém, vhodně
zvolené datové struktury ho mohou vyřešit za vás. Jak například vypsat
unikátně všechna jména lidí v Jáchymově, tj. aby se žádná dvě jména
neopakovala? Samozřejmé hrdý traktorista bude bastlit kód přes pole a
porovnávání Stringů, ale použijete-li množinu, řešení je
krátké, stručné a elegantní. A přesně taková řešení máme rádi.
Protože po mistrovském zvládnutí algoritmů a datových struktur z vás bude
GURU!
V další lekci, Datové struktury pole a list, si dopodrobna vysvětlíme datové struktury jako je pole a list, ukážeme jejich výhody, nevýhody, a u metod se seznámíme s časovou složitostí.
