Dátové štruktúry a algoritmy v Jave, časť 1: Prehľad

Programátori Java používajú na ukladanie a organizáciu údajov dátové štruktúry a na manipuláciu s údajmi v týchto štruktúrach používame algoritmy. Čím viac budete rozumieť dátovým štruktúram a algoritmom a ich vzájomnej spolupráci, tým efektívnejšie budú vaše programy Java.

Tento tutoriál predstavuje krátku sériu predstavujúcu dátové štruktúry a algoritmy. V 1. časti sa dozviete, čo je dátová štruktúra a ako sú klasifikované. Dozviete sa tiež, čo je to algoritmus, ako sú algoritmy reprezentované a ako používať funkcie časovej a priestorovej zložitosti na porovnanie podobných algoritmov. Keď získate tieto základné informácie, budete pripravení sa v časti 2 dozvedieť o vyhľadávaní a triedení pomocou jednorozmerných polí.

Čo je to dátová štruktúra?

Dátové štruktúry sú založené na abstraktných dátových typoch (ADT), ktoré Wikipedia definuje takto:

[A] matematický model pre dátové typy, kde je dátový typ definovaný jeho správaním (sémantikou) z pohľadu používateľa údajov, najmä pokiaľ ide o možné hodnoty, možné operácie s údajmi tohto typu a správanie týchto operácií.

ADT sa nestará o pamäťové znázornenie svojich hodnôt alebo o to, ako sú implementované jeho operácie. Je to ako rozhranie Java, čo je dátový typ, ktorý je odpojený od akejkoľvek implementácie. Naproti tomu a dátová štruktúra je konkrétna implementácia jedného alebo viacerých ADT, podobných tomu, ako triedy Java implementujú rozhrania.

Príklady ADT zahŕňajú Zamestnanec, Vozidlo, Pole a Zoznam. Zvážte Zoznam ADT (tiež známy ako Sekvenčný ADT), ktorý popisuje usporiadanú kolekciu prvkov, ktoré zdieľajú spoločný typ. Každý prvok v tejto kolekcii má svoju vlastnú pozíciu a sú povolené duplicitné prvky. Medzi základné operácie podporované zoznamom ADT patria:

Vytvára sa nový a prázdny zoznam
Pridanie hodnoty na koniec zoznamu
Vkladanie hodnoty do zoznamu
Vymazanie hodnoty zo zoznamu
Iterácia zoznamu
Zničenie zoznamu

Dátové štruktúry, ktoré môžu implementovať zoznam ADT, zahŕňajú jednorozmerné polia s pevnou a dynamickou veľkosťou a jednotlivo prepojené zoznamy. (Budete oboznámení s poľami v časti 2 a prepojenými zoznamami v časti 3.)

Klasifikácia dátových štruktúr

Existuje mnoho druhov dátových štruktúr, od jednoduchých premenných po polia alebo prepojené zoznamy objektov, ktoré obsahujú viac polí. Všetky dátové štruktúry možno klasifikovať ako primitívne alebo agregované a niektoré sú klasifikované ako kontajnery.

Primitíva vs agregáty

Najjednoduchší druh dátovej štruktúry ukladá jednotlivé dátové položky; napríklad premenná, ktorá uchováva boolovskú hodnotu, alebo premenná, ktorá uchováva celé číslo. Takéto dátové štruktúry označujem ako primitívi.

Mnoho dátových štruktúr je schopných uložiť viac dátových položiek. Napríklad pole môže ukladať viac dátových položiek do svojich rôznych slotov a objekt môže ukladať viac dátových položiek prostredníctvom svojich polí. Tieto dátové štruktúry označujem ako agregáty.

Všetky dátové štruktúry, ktoré preskúmame v tejto sérii, sú agregované.

Kontajnery

Čokoľvek, z čoho sú uložené a načítané dátové položky, by sa mohlo považovať za dátovú štruktúru. Príklady zahŕňajú dátové štruktúry odvodené z vyššie spomenutých ADT zamestnancov, vozidiel, polí a zoznamov.

Mnoho dátových štruktúr je navrhnutých na opis rôznych entít. Prípady Zamestnanec triedy sú dátové štruktúry, ktoré existujú napríklad na opis rôznych zamestnancov. Naproti tomu niektoré dátové štruktúry existujú ako všeobecné úložné nádoby pre iné dátové štruktúry. Napríklad do poľa sa môžu ukladať primitívne hodnoty alebo odkazy na objekty. Túto poslednú kategóriu dátových štruktúr označujem ako nádob.

Rovnako ako agregáty, všetky dátové štruktúry, na ktoré sa pozrieme v tejto sérii, sú kontajnermi.

Dátové štruktúry a algoritmy v zbierkach Java

Rámec kolekcie Java podporuje mnoho druhov kontajnerových údajových štruktúr a súvisiacich algoritmov. Táto séria vám pomôže lepšie pochopiť tento rámec.

Dizajnové vzory a dátové štruktúry

Pomerne často sa stáva, že sa dizajnérske vzory používajú na zoznámenie študentov univerzity s dátovými štruktúrami. Dokument Brown University skúma niekoľko dizajnových vzorov, ktoré sú užitočné pri navrhovaní vysoko kvalitných dátových štruktúr. Príspevok okrem iného demonštruje, že vzor adaptéra je užitočný na navrhovanie stohov a front. Demonštračný kód je uvedený v zozname 1.

Zoznam 1. Použitie vzoru adaptéra pre stohy a fronty (DequeStack.java)

verejná trieda DequeStack implementuje Stack {Deque D; // obsahuje prvky zásobníka public DequeStack () {D = new MyDeque (); } @Override public int size () {return D.size (); } @Override public boolean isEmpty () {return D.isEmpty (); } @Override public void push (Object obj) {D.insertLast (obj); } @Override public Object top () hodí StackEmptyException {try {return D.lastElement (); } catch (DequeEmptyException err) {throw new StackEmptyException (); }} @Override public Object pop () vyvolá StackEmptyException {try {return D.removeLast (); } catch (DequeEmptyException err) {throw new StackEmptyException (); }}}

V zozname 1 sú výňatky z Brown University DequeStack triedy, ktorá demonštruje vzor adaptéra. Poznač si to Stoh a Deque sú rozhrania, ktoré popisujú Stack a Deque ADT. MyDeque je trieda, ktorá implementuje Deque.

Prepísanie metód rozhrania

Pôvodný kód, na ktorom je založený záznam 1, zdrojový kód nepredstavoval Stoh, Dequea MyDeque. Pre zrozumiteľnosť som uviedol @ Override anotácie, ktoré ukazujú, že všetky DequeStackprepíšu nekonštruktívne metódy Stoh metódy.

DequeStack prispôsobuje sa MyDeque aby mohla realizovať Stoh. Všetci z DequeStackMetódou sú jednorázové volania do Deque metódy rozhrania. Je tu však malá vráska Deque výnimky sa konvertujú na Stoh výnimky.

Čo je to algoritmus?

Algoritmy, ktoré sa historicky používajú ako nástroj na matematické výpočty, sú úzko spojené s počítačovou vedou a najmä s dátovými štruktúrami. An algoritmus je postupnosť pokynov, ktorá dokončí úlohu v konečnom časovom období. Vlastnosti algoritmu sú nasledujúce:

Prijíma nulu alebo viac vstupov
Produkuje najmenej jeden výstup
Skladá sa z jasných a jednoznačných pokynov
Končí po konečnom počte krokov
Je dosť základné, aby to človek mohol vykonávať pomocou ceruzky a papiera

Upozorňujeme, že hoci programy môžu mať algoritmický charakter, veľa programov sa neukončí bez externého zásahu.

Mnoho sekvencií kódu sa kvalifikuje ako algoritmus. Jedným príkladom je sekvencia kódu, ktorá vytlačí správu. Preslávenejšie je, že Euklidov algoritmus sa používa na výpočet najväčšieho spoločného matematického deliteľa. Môže sa dokonca stať, že základné operácie dátovej štruktúry (ako napr uložiť hodnotu do slotu poľa) sú algoritmy. V tejto sérii sa budem väčšinou zameriavať na algoritmy vyššej úrovne používané na spracovanie dátových štruktúr, ako sú napríklad algoritmy Binary Search a Matrix Multiplication.

Vývojové diagramy a pseudokód

Ako reprezentujete algoritmus? Písanie kódu pred úplným porozumením jeho základného algoritmu môže viesť k chybám, tak aká je lepšia alternatíva? Dve možnosti sú vývojové diagramy a pseudokód.

Použitie vývojových diagramov na predstavenie algoritmov

A vývojový diagram je vizuálna reprezentácia toku riadenia algoritmu. Toto znázornenie ilustruje príkazy, ktoré je potrebné vykonať, rozhodnutia, ktoré je potrebné vykonať, logický tok (pre iteráciu a iné účely) a terminály, ktoré označujú počiatočné a koncové body. Obrázok 1 odhaľuje rôzne symboly, ktoré vývojové diagramy používajú na vizualizáciu algoritmov.

Zvážte algoritmus, ktorý inicializuje počítadlo na 0, číta znaky až do nového riadku (\ n) znak je viditeľný, zvyšuje počítadlo pre každý prečítaný znak číslice a po prečítaní znaku nového riadku vytlačí hodnotu počítadla. Vývojový diagram na obrázku 2 ilustruje riadiaci tok tohto algoritmu.

Jednoduchosť vývojového diagramu a jeho schopnosť vizuálne predstaviť tok riadenia algoritmu (takže je ľahké ho sledovať) sú jeho hlavnými výhodami. Vývojové diagramy však majú aj niekoľko nevýhod:

Je ľahké zaviesť chyby alebo nepresnosti do veľmi podrobných vývojových diagramov kvôli nudnosti spojenej s ich vykreslením.
Umiestnenie, označenie a pripojenie symbolov vývojového diagramu vyžaduje určitý čas, dokonca aj s využitím nástrojov na urýchlenie tohto procesu. Toto oneskorenie môže spomaliť vaše pochopenie algoritmu.
Vývojové diagramy patria do éry štruktúrovaného programovania a nie sú také užitočné v objektovo orientovanom kontexte. Naproti tomu Unified Modeling Language (UML) je vhodnejší na vytváranie objektovo orientovaných vizuálnych reprezentácií.

Používanie pseudokódu na predstavenie algoritmov

Alternatívou k vývojovým diagramom je pseudokód, čo je textová reprezentácia algoritmu, ktorý sa približuje konečnému zdrojovému kódu. Pseudokód je užitočný na rýchle zapísanie reprezentácie algoritmu. Pretože sa syntax netýka, neexistujú žiadne prísne pravidlá pre písanie pseudokódu.

Pri písaní pseudokódu by ste sa mali usilovať o konzistenciu. Vďaka konzistentnosti bude oveľa jednoduchšie preložiť pseudokód do skutočného zdrojového kódu. Zvážte napríklad nasledujúcu pseudokódovú reprezentáciu predchádzajúceho protiorientovaného vývojového diagramu:

 VYHLASOVAŤ CHARAKTER ch = '' VYHLASOVAŤ počet INTEGEROV = 0 PREČÍTAJTE si ch AK CH GE '0' A ch LE '9' POTOM počet = počet + 1 UKONČIŤ AŽ DO CH EQ '\ n' POČET TLAČI KONIEC

Pseudokód najskôr predstavuje niekoľko VYHLASOVAŤ výroky, ktoré zavádzajú premenné ch a počítať, inicializované na predvolené hodnoty. Potom predstavuje a DO slučka, ktorá sa vykoná AŽch obsahuje \ n (znak nového riadku), kedy sa slučka končí a a TLAČ výstupy výpisu počítaťhodnota.

Pre každú iteráciu slučky ČÍTAŤ spôsobí, že sa znak načíta z klávesnice (alebo možno zo súboru - v tomto prípade nezáleží na tom, čo predstavuje podkladový vstupný zdroj) a priradí sa k ch. Ak je tento znak číslica (jedna z 0 cez 9), počítať sa zvyšuje o 1.

Výber správneho algoritmu

Dátové štruktúry a algoritmy, ktoré používate, kriticky ovplyvňujú dva faktory vo vašich aplikáciách:

Využitie pamäte (pre dátové štruktúry).
Čas CPU (pre algoritmy, ktoré interagujú s týmito dátovými štruktúrami).

Z toho vyplýva, že by ste si mali osobitne uvedomiť algoritmy a dátové štruktúry, ktoré používate pre aplikácie, ktoré spracúvajú veľké množstvo údajov. Patria sem aplikácie používané pre veľké dáta a internet vecí.

Vyvažovanie pamäte a procesora

Pri výbere dátovej štruktúry alebo algoritmu niekedy nájdete znak inverzný vzťah medzi využitím pamäte a časom CPU: čím menej pamäte dátová štruktúra využíva, tým viac algoritmov spojených s časom CPU potrebuje na spracovanie dátových položiek dátovej štruktúry. Čím viac pamäte použije dátová štruktúra, tým menej algoritmov spojených s časom procesora bude potrebných na spracovanie dátových položiek, čo povedie k rýchlejším výsledkom algoritmu.

Pokiaľ je to možné, mali by ste sa usilovať vyvážiť využitie pamäte a času CPU. Túto úlohu môžete zjednodušiť analýzou algoritmov na určenie ich efektívnosti. Ako dobre funguje jeden algoritmus proti druhému podobného charakteru? Odpoveď na túto otázku vám pomôže urobiť dobrý výber pri výbere medzi viacerými algoritmami.

Účinnosť meracieho algoritmu

Niektoré algoritmy fungujú lepšie ako iné. Napríklad algoritmus binárneho vyhľadávania je takmer vždy účinnejší ako algoritmus lineárneho vyhľadávania - niečo, čo uvidíte sami v časti 2. Chcete zvoliť najefektívnejší algoritmus pre potreby svojej aplikácie, ale táto voľba nemusí byť taká zrejmá. ako by ste si mysleli.

Čo napríklad znamená, ak algoritmu Selection Sort (uvedenému v časti 2) trvá 0,4 sekundy, kým sa na danom stroji zoradí 10 000 celých čísel? Táto referenčná hodnota je platná iba pre konkrétny stroj, konkrétnu implementáciu algoritmu a pre veľkosť vstupných údajov.

Ako počítačový vedec používame časovú a priestorovú zložitosť na meranie účinnosti algoritmu a ich destiláciu do funkcie zložitosti abstraktné podrobnosti implementácie a runtime prostredia. Funkcie zložitosti odhaľujú odchýlky v časových a priestorových požiadavkách algoritmu na základe množstva vstupných údajov:

A funkcia časovej zložitosti meria algoritmus časová zložitosť- znamená, ako dlho trvá dokončenie algoritmu.
A funkcia priestorovej zložitosti meria algoritmus zložitosť priestoru- znamenajúca veľkosť režijného množstva pamäte požadovanú algoritmom na vykonanie jeho úlohy.

Obe funkcie zložitosti sú založené na veľkosti vstupu (n), čo nejako odráža množstvo vstupných údajov. Zvážte nasledujúci pseudokód pre tlač poľa:

 VYHLASOVAŤ INTEGER i, x [] = [10, 15, -1, 32] PRE i = 0 DO DĹŽKY (x) - 1 TLAČ x [i] ĎALŠIE i KONIEC

Funkcie časovej zložitosti a časovej zložitosti

Časovú zložitosť tohto algoritmu môžete vyjadriť zadaním funkcie časovej zložitosti t (n) = an+ b, kde a (konštantný multiplikátor) predstavuje čas potrebný na dokončenie jednej iterácie slučky a b predstavuje čas nastavenia algoritmu. V tomto príklade je časová zložitosť lineárna.