Úvod do dátových štruktúr
Už viete napísať "Hello world"? Je čas posunúť sa ďalej. V tomto článku sa vám pokúsim trochu priblížiť použitie a možnosti rôznych dátových štruktúr.
- Čo to je vlastne dátová štruktúra?
- Ako zvoliť tú správnu?
- Ako veľmi im musím rozumieť "zvnútra"?
Všetky tieto otázky si dnes zodpovieme. Článok predpokladá znalosti aspoň úvodu do algoritmizácie a časovej zložitosti, ktoré nájdete v článkoch Úvod do teórie algoritmov a Výpočet časovej zložitosti.
Prečo sa zaoberať uložením dát
Teraz sme v situácii, keď vieme napísať bežné aplikácie a aspoň raz sme použili poľa. Ak chceme však písať väčšie programy, najskôr budú obsahovať aj viac dát. O veľa viac, než sme sami schopní si ustrážiť. Pamätajte, počítač by si mal všetko pamätať, nie vy. Predstavme si, že si chceme uložiť niečo okolo milióna čísel. Niektoré tam môžu byť viackrát, niektoré tam nemusí byť ani raz. V čom je uložiť? To záleží na tom, aké operácie nad týmito číslami chceme vykonávať.
Čísla môžeme jednoducho uložiť do poľa Hlavička a máme po probléme
s ukladaním. Čo keď ale budeme chcieť v poli nájsť nejaké číslo?
Trebárs maximum? Nie je problém, prejdeme poľa. Vieme, že v poli o veľkosti
n nájdeme maximum v čase O(n). Ale čo keď budeme
postupne maxima odoberať, napr. Odbavovať najdlhšie čakajúci užívateľa?
Jednak nám v poli budú vznikať diery a jednak pre každé vyhľadanie maximá
budeme musieť poľa prehľadať znova. Možno by bolo lepšie použiť inú
štruktúru. Iný spôsob, ako ukladať dáta.
Ktorú štruktúru kedy použiť
Štruktúru vyberieme teda podľa toho, aké operácie by sme chceli najčastejšie vykonávať nad danými dátami. Aké operácie chceme? Napríklad nájsť prvok, nájsť maximum / minimum, nájsť predchodca prvku, vložiť prvok, odstrániť, zoradiť prvky atd ...
Prečo sú dátové štruktúry dôležité? To je jednoduché, uveďme si príklad.
Farmár a programátor
O prácu v jednej firme sa na pozíciu programátora uchádzajú dvaja
ľudia. Jeden farmár a druhý programátor.
Farmár celý život pracuje s poľom, vie v ňom vyhľadávať a dokáže
napísať veľmi sofistikovaný kód, ktorý pracuje s poľami. Druhý
uchádzač je slabý študent programovanie, ktorý predvčerom nevedel, čo je
to String a na pracovný pohovor sa v záchvate zúfalstva naučil
niekoľko dátových štruktúr. Obaja dostali za úlohu naprogramovať
aplikáciu, ktoré sa odovzdá hromada čísel a bude vyhľadávať, či medzi
nimi bolo "Šťastné číslo".
Farmár hrdo postaví objektový návrh a všetko nasype do poľa. Chudák študent v záchvate zúfalstva vytvorí vyhľadávací strom a ako-tak mu funguje. Ale ajhľa, aj napriek všetkým optimalizácia je farmárov kód oveľa pomalší. Študent je okamžite prijatý a farmár zas sadá za traktor k svojim obľúbeným poliam.
Základné operácie
Nižšie nájdete tabuľku, ktorá ukazuje niekoľko málo dátových štruktúr, ktoré si postupne predstavíme. Ďalej uvádza časovej zložitosti základných operácií, ktoré by sme po štruktúrach mohli chcieť:
| štruktúra | vloženie prvku | odstránenie | obsahuje prvok | nájdenie minima |
|---|---|---|---|---|
| poľa | O (1) | O (n) | O (n) | O (n) |
| usporiadané pole | O (n) | O (n) | O (log n) | O (1) |
| binárny vyhľadávací strom | Θ (log n) | Θ (log n) | Θ (log n) | Θ (log n) |
| zásobník | O (1) | O (n) | O (n) | O (n) |
Zoznam štruktúr
Stručne si predstavíme najdôležitejšie dátové štruktúry a uvedieme si ich výhody a nevýhody. Je to však len inšpirácia, viac v samostatných článkoch.
Pole (Array)
Pole používame kvôli jeho rýchle prácu cez indexy prvkov.
Klady a zápory
| + | - |
|---|---|
| jednoduché na vytvorenie | triedenie v O(n*log n) |
| jednoduché na použitie | vyhľadávanie v O(n), popr. O(log n), ak je
zotriedené |
priame indexovanie v O(1) |
Front alebo zásobník používame pokiaľ potrebujeme s prvkami pracovať v poradí v akom boli pridané alebo v opačnom. Fronta podporuje prístup FIFO (First In First Out, teda prvý pridaný prvok je prvá na rade).
Zásobník podporuje prístup LIFO (Last in First Out), teda posledný pridaný prvok je prvý na rade.
Klady a zápory
| + | - |
|---|---|
push / vložiť prvok v O(1) |
nemožno vkladať doprostred |
pop / odobrať prvok v O(1) |
|
zobraziť vršok štruktúry O(1) |
Množiny zaisťujú, že sa v nich každý prvok nachádza len raz. Jej prvky sú teda unikátne.
Klady a zápory
| + | - |
|---|---|
| rýchla kontrola, či obsahuje hodnotu | veľmi limitované použitie |
| bez duplicitných hodnôt |
Halda nám umožňuje instantne odobrať najväčší alebo najmenší prvok.
Klady a zápory
| + | - |
|---|---|
nájdi min / max O(1) |
vyhľadávania O(n) |
vlož O(log n) |
odstránenie prvku O(n) |
odstráň min / max O(log n) |
Binárny vyhľadávací strom nám umožní prvky rýchlo vyhľadávať a optimalizuje ich vkladanie a mazanie.
Klady a zápory
| + | - |
|---|---|
| udržuje "setříděnost" | zložitejšie manipulácie s prvkami |
vloženie v O(log n) |
|
odstránenie v O(log n) |
Ak ste článok dočítali až sem, pravdepodobne vás naozaj zaujíma, čo
skrývajú topí dátových štruktúr. Existuje nepreberné množstvo
možností, ako využiť ich silu. Z frontu môžeme urobiť prioritné front,
čiže front s předbíháním. Z množiny môžeme urobiť usporiadanú
množinu či ju zovšeobecniť na slovník. Navyše, ak riešite nejaký
problém, vhodne zvolené dátové štruktúry ho môžu vyriešiť za vás. Ako
napríklad vypísať unikátne všetky mená ľudí v Jáchymove, tj. Aby sa
žiadna dve mená neopakovala? Samozrejmé hrdý traktorista bude bastlit kód
cez pole a porovnávanie String ov, ale ak použijete množinu,
riešenie je krátke, stručné a elegantné. A presne také riešenia máme
radi. Pretože po majstrovskom zvládnutí algoritmov a dátových štruktúr z
vás bude GURU!
