Podatkovne strukture in algoritmi v Javi, 1. del: Pregled

Programerji Java uporabljajo podatkovne strukture za shranjevanje in organiziranje podatkov, mi pa algoritme za obdelavo podatkov v teh strukturah. Bolj ko boste razumeli podatkovne strukture in algoritme ter kako delujejo skupaj, učinkovitejši bodo vaši programi Java.

Ta vadnica predstavlja kratko serijo s predstavitvijo podatkovnih struktur in algoritmov. V prvem delu boste izvedeli, kaj je podatkovna struktura in kako so razvrščene. Izvedeli boste tudi, kaj je algoritem, kako so algoritmi predstavljeni in kako uporabiti funkcije zapletenosti časa in prostora za primerjavo podobnih algoritmov. Ko boste dobili te osnove, se boste v 2. delu lahko naučili o iskanju in razvrščanju z enodimenzionalnimi nizi.

Kaj je podatkovna struktura?

Podatkovne strukture temeljijo na abstraktnih vrstah podatkov (ADT), ki jih Wikipedia opredeljuje na naslednji način:

[A] matematični model za podatkovne tipe, kjer je podatkovni tip definiran s svojim vedenjem (semantiko) z vidika uporabnika podatkov, zlasti glede možnih vrednosti, možnih operacij s podatki te vrste in vedenja teh operacij.

ADT ne skrbi za predstavitev svojih vrednosti v pomnilniku ali kako se izvajajo njegove operacije. To je kot vmesnik Java, ki je podatkovni tip, ki ni povezan z nobeno izvedbo. Nasprotno pa a podatkovna struktura je konkretna izvedba enega ali več ADT-jev, podobno kot razredi Java izvajajo vmesnike.

Primeri ADT vključujejo zaposlenega, vozilo, matriko in seznam. Razmislite o seznamu ADT (znan tudi kot zaporedje ADT), ki opisuje urejeno zbirko elementov, ki imajo skupen tip. Vsak element v tej zbirki ima svoj položaj in podvojeni elementi so dovoljeni. Osnovne operacije, ki jih podpira seznam ADT, vključujejo:

• Ustvarjanje novega in praznega seznama
• Dodajanje vrednosti na konec seznama
• Vstavljanje vrednosti na seznam
• Brisanje vrednosti s seznama
• Ponavljanje po seznamu
• Uničevanje seznama

Podatkovne strukture, ki lahko izvajajo ADT seznama, vključujejo enodimenzionalna polja s fiksno in dinamično velikostjo ter posamezno povezane sezname. (Predlogi se bodo predstavili v 2. delu in povezani seznami v 3. delu.)

Razvrščanje podatkovnih struktur

Obstaja veliko vrst podatkovnih struktur, od posameznih spremenljivk do nizov ali povezanih seznamov predmetov, ki vsebujejo več polj. Vse podatkovne strukture lahko razvrstimo kot primitivne ali sestavljene, nekatere pa kot vsebnike.

Primitivi vs agregati

Najenostavnejša vrsta podatkovne strukture hrani posamezne podatke; na primer spremenljivka, ki shranjuje logično vrednost, ali spremenljivka, ki hrani celo število. Na takšne strukture podatkov se sklicujem kot primitivci.

Številne podatkovne strukture lahko shranijo več podatkovnih postavk. Polje lahko na primer shrani več podatkovnih elementov v različnih režah, objekt pa lahko prek svojih polj shrani več podatkovnih elementov. Na te podatkovne strukture se sklicujem kot agregati.

Vse podatkovne strukture, ki si jih bomo ogledali v tej seriji, so agregati.

Zabojniki

Karkoli, iz katerega se shranjujejo in pridobivajo podatkovni elementi, bi se lahko štelo za podatkovno strukturo. Primeri vključujejo podatkovne strukture, ki izhajajo iz prej omenjenih ADT-jev za zaposlene, vozila, matrike in sezname.

Številne podatkovne strukture so zasnovane za opis različnih entitet. Primeri Zaposleni class so podatkovne strukture, ki na primer obstajajo za opis različnih zaposlenih. Nasprotno pa nekatere podatkovne strukture obstajajo kot generične shrambe za druge podatkovne strukture. Polje lahko na primer shrani primitivne vrednosti ali reference na objekt. Na to zadnjo kategorijo podatkovnih struktur se sklicujem kot posode.

Poleg tega, da so agregati, so vse podatkovne strukture, ki si jih bomo ogledali v tej seriji, tudi vsebniki.

Podatkovne strukture in algoritmi v zbirkah Java

Okvir Java Collections Framework podpira številne vrste vsebinsko usmerjenih podatkovnih struktur in pripadajočih algoritmov. Ta serija vam bo pomagala bolje razumeti ta okvir.

Oblikovanje vzorcev in podatkovnih struktur

Dokaj pogosta je uporaba vzorcev oblikovanja za uvajanje študentov v podatkovne strukture. Prispevek univerze Brown preučuje več vzorcev oblikovanja, ki so koristni za oblikovanje visokokakovostnih podatkovnih struktur. Članek med drugim dokazuje, da je vzorec adapterja koristen za oblikovanje skladov in čakalnih vrst. Demonstracijska koda je prikazana v seznamu 1.

Seznam 1. Uporaba vzorca adapterja za sklade in čakalne vrste (DequeStack.java)

javni razred DequeStack izvaja Stack {Deque D; // vsebuje elemente sklada public DequeStack () {D = new MyDeque (); } @Override public int size () {return D.size (); } @Override public boolean isEmpty () {return D.isEmpty (); } @Override public void push (Objekt obj) {D.insertLast (obj); } @Override public Object top () vrže StackEmptyException {try {return D.lastElement (); } catch (DequeEmptyException err) {throw new StackEmptyException (); }} @Override public Object pop () vrže StackEmptyException {try {return D.removeLast (); } catch (DequeEmptyException err) {throw new StackEmptyException (); }}}

Seznam 1 vsebuje odlomke iz univerze Brown DequeStack razred, ki prikazuje vzorec adapterja. Upoštevajte to Stack in Deque so vmesniki, ki opisujejo ADD-je Stack in Deque. MyDeque je razred, ki izvaja Deque.

Preglasitev vmesniških metod

Prvotna koda, na kateri temelji seznam 1, izvorne kode ni predstavila Stack, Deque, in MyDeque. Zaradi jasnosti sem predstavil @Override pripombe, ki dokazujejo, da so vsi DequeStackne-konstruktorske metode preglasijo Stack metode.

DequeStack prilagaja MyDeque tako da lahko izvaja Stack. Vse od DequeStack's metoda so enovrstni klici na Deque metode vmesnika. Vendar pa obstaja majhna guba, v kateri Deque izjeme se pretvorijo v Stack izjeme.

Kaj je algoritem?

Algoritmi so se v zgodovini uporabljali kot orodje za matematično računanje in so globoko povezani z računalništvom in zlasti s podatkovnimi strukturami. An algoritem je zaporedje navodil, ki opravijo nalogo v končnem časovnem obdobju. Lastnosti algoritma so naslednje:

• Prejema nič ali več vhodov
• Ustvari vsaj en izhod
• Sestavljena je iz jasnih in nedvoumnih navodil
• Konča se po končnem številu korakov
• Je dovolj osnovna, da jo lahko človek izvede s svinčnikom in papirjem

Upoštevajte, da čeprav so programi lahko algoritemske narave, se številni programi ne končajo brez zunanjega posredovanja.

Številna zaporedja kod se štejejo za algoritme. En primer je zaporedje kod, ki natisne poročilo. Še bolj znano je, da se Euclidov algoritem uporablja za izračun največjega matematičnega skupnega delitelja. Lahko bi celo navedli, da so osnovne operacije podatkovne strukture (na primer shrani vrednost v reži polja) so algoritmi. V tej seriji se bom večinoma osredotočil na algoritme na višji ravni, ki se uporabljajo za obdelavo podatkovnih struktur, kot sta algoritma binarnega iskanja in množenja matric.

Diagrami poteka in psevdokoda

Kako predstavljate algoritem? Pisanje kode pred popolnim razumevanjem njenega osnovnega algoritma lahko povzroči napake, kaj je torej boljša alternativa? Dve možnosti sta diagrami poteka in psevdokoda.

Uporaba diagramov poteka za predstavitev algoritmov

A diagram poteka je vizualna predstavitev krmilnega toka algoritma. Ta predstavitev ponazarja izjave, ki jih je treba izvesti, odločitve, ki jih je treba sprejeti, logični tok (za ponovitev in druge namene) ter terminale, ki označujejo začetne in končne točke. Slika 1 razkriva različne simbole, ki jih diagrami poteka uporabljajo za vizualizacijo algoritmov.

Razmislite o algoritmu, ki inicializira števec na 0, bere znake do nove vrstice (\ n), se prikaže števec za vsak prebrani števčni znak in po prebranem znaku nove vrstice natisne vrednost števca. Diagram poteka na sliki 2 prikazuje krmilni tok tega algoritma.

Preprostost diagrama poteka in njegova zmožnost vizualnega prikaza krmilnega toka algoritma (tako da je enostavno slediti) sta njegovi glavni prednosti. Diagrami poteka imajo tudi več pomanjkljivosti:

• Zaradi dolgočasja, povezanega z njihovim risanjem, je v zelo podrobne diagrame poteka enostavno vnesti napake ali netočnosti.
• Potreben je čas za določanje, označevanje in povezovanje simbolov diagrama poteka, tudi z uporabo orodij za pospešitev tega postopka. Ta zamuda lahko upočasni vaše razumevanje algoritma.
• Diagrami poteka spadajo v obdobje strukturiranega programiranja in v objektno usmerjenem kontekstu niso tako uporabni. Nasprotno pa je Unified Modeling Language (UML) bolj primeren za ustvarjanje objektno usmerjenih vizualnih predstavitev.

Uporaba psevdokode za predstavitev algoritmov

Alternativa diagramom poteka je psevdokod, ki je besedilna predstavitev algoritma, ki približuje končno izvorno kodo. Pseudocode je uporaben za hitro zapisovanje predstavitve algoritma. Ker sintaksa ni zaskrbljujoča, ni hitrih pravil za pisanje psevdokode.

Pri pisanju psevdokode si morate prizadevati za doslednost. Če boste dosledni, bo psevdokod veliko lažje prevesti v dejansko izvorno kodo. Upoštevajte na primer naslednjo predstavitev psevdokode prejšnjega protiusmerjenega diagrama poteka:

 IZJAVI ZNAK ch = '' IZJAVI INTEGER count = 0 PREBERI ch, ČE ch GE '0' IN ch LE '9' THEN count = count + 1 END IF UNTIL ch EQ '\ n' PRINT count END

Psevkodo najprej predstavi nekaj IZJAVITE izjave, ki uvajajo spremenljivke pogl in štetje, inicializirano na privzete vrednosti. Nato predstavlja a DO zanka, ki se izvaja DOpogl vsebuje \ n (znak nove vrstice), na kateri se zanka konča in a TISK izhodi stavka štetjevrednost.

Za vsako ponovitev zanke, PREBERITE povzroči, da se znak prebere s tipkovnice (ali morda datoteke - v tem primeru ni pomembno, kaj predstavlja osnovni vhodni vir) in dodeli pogl. Če je ta znak številka (ena od 0 skozi 9), štetje se poveča za 1.

Izbira pravega algoritma

Podatkovne strukture in algoritmi, ki jih uporabljate, kritično vplivajo na dva dejavnika v vaših aplikacijah:

1. Uporaba pomnilnika (za podatkovne strukture).
2. CPU čas (za algoritme, ki sodelujejo s temi podatkovnimi strukturami).

Iz tega sledi, da bi morali biti še posebej pozorni na algoritme in podatkovne strukture, ki jih uporabljate za aplikacije, ki obdelujejo veliko podatkov. Sem spadajo aplikacije, ki se uporabljajo za velike podatke in internet stvari.

Uravnavanje pomnilnika in CPU

Pri izbiri podatkovne strukture ali algoritma boste včasih odkrili inverzni odnos med porabo pomnilnika in časom procesorja: manj pomnilnika, kot ga uporablja podatkovna struktura, več algoritmov, povezanih s procesorjem, potrebuje za obdelavo podatkovnih elementov podatkovne strukture. Poleg tega, več kot pomnilnik uporablja podatkovna struktura, manj algoritmov, povezanih s procesorjem, bo potrebno za obdelavo podatkovnih elementov - kar bo privedlo do hitrejših rezultatov algoritmov.

Kolikor je le mogoče, si morate prizadevati za uravnoteženje porabe pomnilnika s časom procesorja. To nalogo lahko poenostavite z analizo algoritmov, da ugotovite njihovo učinkovitost. Kako dobro deluje en algoritem proti drugemu podobne narave? Odgovor na to vprašanje vam bo pomagal pri dobri izbiri med izbiro med več algoritmi.

Merjenje učinkovitosti algoritma

Nekateri algoritmi delujejo bolje kot drugi. Na primer, algoritem binarnega iskanja je skoraj vedno učinkovitejši od algoritma linearnega iskanja - nekaj, kar boste sami videli v 2. delu. Izbrati želite najučinkovitejši algoritem za potrebe vaše aplikacije, vendar ta izbira morda ni tako očitna kot bi si mislili.

Na primer, kaj pomeni, da algoritem za razvrščanje po izboru (uveden v 2. delu) traja 0,4 sekunde za razvrščanje 10.000 celih števil na določeni napravi? Ta primerjalna vrednost velja samo za določeno napravo, za določeno izvedbo algoritma in za velikost vhodnih podatkov.

Kot računalničar uporabljamo časovno zapletenost in zapletenost prostora za merjenje učinkovitosti algoritma, ki jih destilira v funkcije zapletenosti povzeti podrobnosti izvedbe in okolja med izvajanjem. Funkcije zapletenosti razkrivajo razlike v časovnih in prostorskih zahtevah algoritma glede na količino vhodnih podatkov:

• A funkcija časovne kompleksnosti meri algoritem časovna zapletenost- pomeni, kako dolgo traja algoritem za dokončanje.
• A funkcija zapletenosti prostora meri algoritem zapletenost prostora- pomeni količino režijskih stroškov pomnilnika, ki jih algoritem potrebuje za izvajanje svoje naloge.

Obe funkciji zapletenosti temeljita na velikosti vnosa (n), ki nekako odraža količino vhodnih podatkov. Za tiskanje matrike upoštevajte naslednjo psevdokodo:

 RAZGLASITE INTEGER i, x [] = [10, 15, -1, 32] FOR i = 0 DO DOLŽINE (x) - 1 PRINT x [i] NEXT i END

Funkcije časovne kompleksnosti in časovne kompleksnosti

Časovno zapletenost tega algoritma lahko izrazite z določitvijo funkcije časovne zapletenosti t (n) = an+ b, kje a (konstantni multiplikator) predstavlja čas, potreben za dokončanje ene ponovitve zanke, in b predstavlja čas nastavitve algoritma. V tem primeru je časovna zapletenost linearna.