Tietorakenteet ja algoritmit Javassa, osa 1: Yleiskatsaus

Java-ohjelmoijat käyttävät tietorakenteita tietojen tallentamiseen ja järjestämiseen, ja algoritmeja käytämme näiden rakenteiden tietojen käsittelyyn. Mitä enemmän ymmärrät tietorakenteista ja algoritmeista sekä niiden yhteistyöstä, sitä tehokkaammat Java-ohjelmat ovat.

Tämä opetusohjelma käynnistää lyhyen sarjan, joka esittelee tietorakenteita ja algoritmeja. Osasta 1 opit, mikä on tietorakenne ja miten tietorakenteet luokitellaan. Opit myös, mikä algoritmi on, miten algoritmit on esitetty ja kuinka käyttää aika- ja avaruusfunktioita vastaavien algoritmien vertaamiseen. Kun olet saanut nämä perusasiat, olet valmis oppimaan osasta 2 etsimisen ja lajittelun yksiulotteisten taulukoiden avulla.

Mikä on tietorakenne?

Tietorakenteet perustuvat abstrakteihin tietotyyppeihin (ADT), jotka Wikipedia määrittelee seuraavasti:

[A] matemaattinen malli tietotyypeille, joissa tietotyyppi määritetään sen käyttäytymisen (semantiikan) perusteella käyttäjän näkökulmasta, erityisesti mahdollisten arvojen, tämän tyyppisten tietojen mahdollisten toimintojen ja käyttäytymisen suhteen näistä toiminnoista.

ADT ei välitä arvojensa edustuksesta muistissaan tai siitä, miten sen toiminnot toteutetaan. Se on kuin Java-käyttöliittymä, joka on tietotyyppi, joka on irrotettu mistä tahansa toteutuksesta. Sen sijaan a tietorakenne on yhden tai useamman ADT: n konkreettinen toteutus, samanlainen kuin Java-luokat toteuttavat rajapintoja.

Esimerkkejä ADT: stä ovat Employee, Vehicle, Array ja List. Harkitse List ADT (tunnetaan myös nimellä Sequence ADT), joka kuvaa järjestettyä kokoelmaa elementtejä, joilla on yhteinen tyyppi. Jokaisella tämän kokoelman elementillä on oma sijainti ja päällekkäiset elementit ovat sallittuja. List ADT: n tukemia perustoimintoja ovat:

Uuden ja tyhjän luettelon luominen
Arvon lisääminen luettelon loppuun
Lisätään arvo luetteloon
Arvon poistaminen luettelosta
Toistuu luettelon yli
Luettelon tuhoaminen

Tietorakenteet, jotka voivat toteuttaa List ADT: n, sisältävät kiinteäkokoisia ja dynaamisia kokoisia yksiulotteisia taulukoita ja yksitellen linkitettyjä luetteloita. (Esität taulukot osassa 2 ja linkitetyt luettelot osassa 3.)

Tietorakenteiden luokittelu

Tietorakenteita on monenlaisia, aina yksittäisistä muuttujista taulukoihin tai linkitettyihin luetteloihin objekteista, jotka sisältävät useita kenttiä. Kaikki tietorakenteet voidaan luokitella primitiiveiksi tai aggregaateiksi, ja jotkut luokitellaan kontteiksi.

Primitiivit vs. aggregaatit

Yksinkertaisin tietorakenne tallentaa yksittäiset tietoerät; esimerkiksi muuttuja, joka tallentaa Boolen-arvon, tai muuttuja, joka tallentaa kokonaisluvun. Viittaan sellaisiin tietorakenteisiin primitiivit.

Monet tietorakenteet pystyvät tallentamaan useita datakohteita. Esimerkiksi matriisi voi tallentaa useita dataelementtejä eri paikkoihinsa, ja objekti voi tallentaa useita tietoeriä kenttiensä kautta. Viittaan näihin tietorakenteisiin aggregaatit.

Kaikki tässä sarjassa tarkastelemamme tietorakenteet ovat aggregaatteja.

Kontit

Kaikki, mistä tietoerät tallennetaan ja haetaan, voidaan katsoa tietorakenteeksi. Esimerkkejä ovat tietorakenteet, jotka on johdettu aiemmin mainituista työntekijöistä, ajoneuvoista, ryhmistä ja luettelo-ADT: stä.

Monet tietorakenteet on suunniteltu kuvaamaan erilaisia kokonaisuuksia. Instansseja sellaisen Työntekijä luokka ovat tietorakenteita, joita on olemassa esimerkiksi erilaisten työntekijöiden kuvaamiseksi. Sitä vastoin jotkut tietorakenteet ovat yleisiä tallennusastioita muille tietorakenteille. Esimerkiksi taulukko voi tallentaa primitiivisiä arvoja tai objektiviittauksia. Viittaan tähän jälkimmäiseen tietorakenteiden luokkaan astiat.

Sen lisäksi että kaikki tässä sarjassa tarkastelemamme tietorakenteet ovat aggregaatteja, ovat kontteja.

Tietorakenteet ja algoritmit Java-kokoelmissa

Java Collections Framework tukee monenlaisia konttipohjaisia tietorakenteita ja niihin liittyviä algoritmeja. Tämä sarja auttaa sinua ymmärtämään paremmin tätä kehystä.

Suunnittelumallit ja tietorakenteet

On tullut melko yleiseksi käyttää suunnittelumalleja tutustuttamaan yliopiston opiskelijoita tietorakenteisiin. Brownin yliopiston paperi tarkastelee useita suunnittelumalleja, joista on hyötyä laadukkaiden tietorakenteiden suunnittelussa. Muun muassa paperi osoittaa, että sovittimen malli on hyödyllinen pinojen ja jonojen suunnittelussa. Esittelykoodi näkyy luettelossa 1.

Luettelo 1. Adapteri-mallin käyttäminen pinoissa ja jonoissa (DequeStack.java)

julkisen luokan DequeStack toteuttaa Stackin {Deque D; // pitää pinon elementit julkisena 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 () heittää StackEmptyException {try {return D.lastElement (); } catch (DequeEmptyException err) {heitä uusi StackEmptyException (); }} @Override public Object pop () heittää StackEmptyException {yritä {return D.removeLast (); } catch (DequeEmptyException err) {heitä uusi StackEmptyException (); }}}

Listaus 1 otteita Brownin yliopiston paperista DequeStack luokka, joka osoittaa sovittimen mallin. Ota huomioon, että Pino ja Deque ovat rajapintoja, jotka kuvaavat Stack and Deque ADT: itä. MyDeque on luokka, joka toteuttaa Deque.

Ohittavat käyttöliittymämenetelmät

Alkuperäinen koodi, johon luettelo 1 perustuu, ei esittänyt lähdekoodia Pino, Dequeja MyDeque. Selvyyden vuoksi olen ottanut käyttöön @Ohittaa merkinnät osoittavat, että kaikki DequeStackei-rakentajan menetelmät ohittavat Pino menetelmiä.

DequeStack mukautuu MyDeque jotta se voi toteuttaa Pino. Kaikki DequeStack: n menetelmä on yhden linjan puhelu Deque käyttöliittymän menetelmät. On kuitenkin pieni ryppy, jossa Deque poikkeukset muunnetaan Pino poikkeuksia.

Mikä on algoritmi?

Historiallisesti matemaattisen laskennan työkaluna käytettyjä algoritmeja on läheisesti yhteydessä tietojenkäsittelytieteisiin ja erityisesti tietorakenteisiin. An algoritmi on käskyjen sarja, joka suorittaa tehtävän rajallisessa ajassa. Algoritmin ominaisuudet ovat seuraavat:

Vastaanottaa nollaa tai enemmän tuloja
Tuottaa ainakin yhden lähdön
Koostuu selkeistä ja yksiselitteisistä ohjeista
Päättyy lopullisen määrän vaiheiden jälkeen
Onko tarpeeksi yksinkertainen, jotta henkilö voi suorittaa sen kynällä ja paperilla

Huomaa, että vaikka ohjelmat voivat olla luonteeltaan algoritmeja, monet ohjelmat eivät lopu ilman ulkoista puuttumista.

Monet koodisekvenssit täyttävät algoritmit. Yksi esimerkki on koodisarja, joka tulostaa raportin. Vielä tunnetummin, Euclidin algoritmia käytetään laskemaan matemaattinen suurin yhteinen jakaja. Voidaan jopa tehdä tapa, että tietorakenteen perustoiminnot (kuten tallentaa arvon matriisipaikkaan) ovat algoritmeja. Tässä sarjassa keskityn suurimmaksi osaksi korkeamman tason algoritmeihin, joita käytetään tietorakenteiden käsittelemiseen, kuten Binaarihaku- ja Matriisikertaistamisalgoritmit.

Vuokaaviot ja pseudokoodi

Kuinka edustat algoritmia? Koodin kirjoittaminen ennen sen taustalla olevan algoritmin ymmärtämistä voi johtaa virheisiin, joten mikä on parempi vaihtoehto? Kaksi vaihtoehtoa ovat vuokaaviot ja pseudokoodi.

Vuokaavioiden käyttäminen algoritmien esittämiseen

A vuokaavio on visuaalinen esitys algoritmin ohjausvirrasta. Tämä esitys kuvaa suoritettavia lauseita, tehtäviä päätöksiä, logiikkavirtaa (iterointia ja muita tarkoituksia varten) ja päätelaitteita, jotka osoittavat aloitus- ja loppupisteet. Kuva 1 paljastaa eri symbolit, joita vuokaaviot käyttävät algoritmien visualisointiin.

Tarkastellaan algoritmia, joka alustaa laskurin nollaksi, lukee merkkejä uudelle riville (\ n) -merkki näkyy, se lisää laskurin jokaiselle luetulle merkille ja tulostaa laskurin arvon uuden rivin merkin lukemisen jälkeen. Kuvion 2 vuokaavio kuvaa tämän algoritmin ohjausvirtaa.

Vuokaavion yksinkertaisuus ja kyky esittää algoritmin ohjausvirta visuaalisesti (niin, että sitä on helppo seurata) ovat sen suuria etuja. Vuokaavioilla on kuitenkin myös useita haittoja:

Virheiden tai epätarkkuuksien lisääminen erittäin yksityiskohtaisiin vuokaavioihin on helppoa niiden piirtämiseen liittyvän ikävyyden vuoksi.
Vuokaavion symbolien sijoittaminen, merkitseminen ja yhdistäminen vie aikaa, jopa työkalujen avulla tämän prosessin nopeuttamiseksi. Tämä viive saattaa hidastaa algoritmin ymmärtämistä.
Vuokaaviot kuuluvat jäsenneltyyn ohjelmointiaikaan, eivätkä ne ole yhtä hyödyllisiä olio-kontekstissa. Sen sijaan Unified Modeling Language (UML) on sopivampi luomaan olio-orientoituja visuaalisia esityksiä.

Pseudokoodin käyttäminen algoritmien esittämiseen

Vaihtoehto vuokaavioille on pseudokoodi, joka on lopullista lähdekoodia lähentävän algoritmin teksti. Pseudokoodi on hyödyllinen algoritmin esityksen kirjoittamiseen nopeasti. Koska syntaksista ei ole huolta, pseudokoodin kirjoittamiselle ei ole kovia ja nopeita sääntöjä.

Pseudokoodia kirjoitettaessa on pyrittävä johdonmukaisuuteen. Johdonmukaisuuden ansiosta pseudokoodin kääntäminen todelliseksi lähdekoodiksi on paljon helpompaa. Harkitse esimerkiksi seuraavaa edellisen vastalähtöisen vuokaavion pseudokoodiesitystä:

 ILMOITA CHARACTER ch = '' ILMOITA INTEGER-luku = 0 LUE LUKU ch ch GE '0' JA ch LE '9' SENNEN määrä = count + 1 LOPPU JOS KETJUUN EQ '

Pseudokoodi esittää ensin pari JULISTAA lauseet, jotka esittävät muuttujia ch ja Kreivi, alustetaan oletusarvoihin. Sitten se esittää a TEHDÄ silmukka, joka suoritetaan SIIHEN ASTI KUNch sisältää \ n (uuden rivin merkki), jolloin silmukka päättyy ja a TULOSTA lausekkeen lähdöt Kreiviarvo.

Jokaiselle silmukan iteraatiolle LUKEA aiheuttaa merkin lukemisen näppäimistöltä (tai ehkä tiedostosta - tässä tapauksessa ei ole väliä mikä muodostaa taustalla olevan lähteen) ja osoitetaan ch. Jos tämä merkki on numero (yksi 0 kautta 9), Kreivi kasvaa 1.

Oikean algoritmin valinta

Käyttämäsi tietorakenteet ja algoritmit vaikuttavat kriittisesti kahteen tekijään sovelluksissasi:

Muistin käyttö (tietorakenteille).
Suorittimen aika (algoritmeille, jotka ovat vuorovaikutuksessa näiden tietorakenteiden kanssa).

Tästä seuraa, että sinun tulee olla erityisen tietoinen algoritmeista ja tietorakenteista, joita käytät sovelluksissa, jotka käsittelevät paljon tietoa. Näitä ovat sovellukset, joita käytetään suurten tietojen käyttöön ja esineiden internet.

Muistin ja suorittimen tasapainottaminen

Kun valitset tietorakenteen tai algoritmin, huomaat joskus käänteinen suhde muistin käytön ja suorittimen ajan välillä: mitä vähemmän muistia tietorakenne käyttää, sitä enemmän prosessorin aikaan liittyvien algoritmien on käsiteltävä tietorakenteen tiedot. Lisäksi, mitä enemmän muistia tietorakenne käyttää, sitä vähemmän prosessorin aikaan liittyviä algoritmeja on käsiteltävä data-kohteet - mikä johtaa nopeammiin algoritmituloksiin.

Sinun tulisi pyrkiä tasapainottamaan muistin käyttö ja suorittimen aika niin paljon kuin mahdollista. Voit yksinkertaistaa tätä tehtävää analysoimalla algoritmeja niiden tehokkuuden määrittämiseksi. Kuinka hyvin yksi algoritmi toimii toista vastaavaa luonnetta vastaan? Vastaaminen tähän kysymykseen auttaa sinua tekemään hyviä valintoja, kun haluat valita useiden algoritmien välillä.

Algoritmin tehokkuuden mittaus

Jotkut algoritmit toimivat paremmin kuin toiset. Esimerkiksi binäärihaun algoritmi on melkein aina tehokkaampi kuin lineaarisen haun algoritmi - jotain, mitä näet itse osassa 2. Haluat valita tehokkaimman algoritmin sovelluksesi tarpeisiin, mutta valinta ei välttämättä ole yhtä ilmeinen kuten luulisi.

Esimerkiksi, mitä se tarkoittaa, jos Selection Sort -algoritmi (esitelty osassa 2) vie 0,4 sekuntia 10000 kokonaisluvun lajittelemiseen tietyllä koneella? Tämä vertailuarvo pätee vain kyseiselle koneelle, algoritmin tietylle toteutukselle ja syötetietojen koolle.

Tietojenkäsittelytieteen tutkijana käytämme ajan monimutkaisuutta ja avaruuden monimutkaisuutta algoritmin tehokkuuden mittaamiseen tislaamalla ne osaksi monimutkaisuusfunktiot abstraktin toteutuksen ja ajonaikaisen ympäristön yksityiskohdat. Monimutkaisuusfunktiot paljastavat algoritmin aika- ja tilavaatimusten varianssin syötetietojen määrän perusteella:

A aika-monimutkaisuusfunktio mittaa algoritmin ajan monimutkaisuus- tarkoittaa kuinka kauan algoritmin suorittaminen kestää.
A avaruuden monimutkaisuusfunktio mittaa algoritmin avaruuden monimutkaisuus- tarkoittaa algoritmin tehtävän suorittamiseen tarvitseman muistin määrää.

Molemmat monimutkaisuusfunktiot perustuvat syötteen kokoon (n), joka heijastaa jotenkin syötetietojen määrää. Harkitse seuraavaa pseudokoodia taulukon tulostuksessa:

 ILMOITA INTEGER i, x [] = [10, 15, -1, 32] i = 0 - PITUUS (x) - 1 TULOSTE x [i] SEURAAVA i LOPPU

Ajan monimutkaisuus ja aikakompleksisuus

Voit ilmaista tämän algoritmin aikakompleksisuuden määrittämällä aikakompleksifunktion t (n) = an+ b, missä a (vakiokerroin) edustaa aikaa yhden silmukan iteroinnin suorittamiseen, ja b edustaa algoritmin asennusaikaa. Tässä esimerkissä ajan monimutkaisuus on lineaarinen.