Python týden Letní akce
Pouze tento týden sleva až 80 % na kurzy Python. Lze kombinovat s akcí Letní slevy na prémiový obsah!
Brno? Vypsali jsme pro vás nové termíny školení Základů programování a OOP v Brně!

Úvod do datových struktur

Unicorn College Tento obsah je dostupný zdarma v rámci projektu IT lidem.
Vydávání, hosting a aktualizace umožňují jeho sponzoři.

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

Farmář 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)

Datová struktura pole

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)

Datová struktura fronta

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ě).

Datová struktura zásobník

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)

Datová struktura halda

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

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!

Guru

 

 

Článek pro vás napsal Tricerator
Avatar
Jak se ti líbí článek?
2 hlasů
Autor se věnuje teoretické informatice. Ve svých volných chvílích nepohrdne šálkem dobrého čaje, kaligrafickým brkem a foukací harmonice.
Všechny články v sekci
Datové struktury
Miniatura
Následující článek
Datové struktury pole a list
Aktivity (4)

 

 

Komentáře

Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zatím nikdo nevložil komentář - buď první!