Programavimas

„Java“ duomenų struktūros ir algoritmai, 1 dalis. Apžvalga

„Java“ programuotojai naudoja duomenų struktūras duomenims saugoti ir tvarkyti, o mes naudojame algoritmus, kad manipuliuotume tų struktūrų duomenimis. Kuo daugiau suprasite duomenų struktūras ir algoritmus ir kaip jie veikia kartu, tuo efektyvesnės bus jūsų „Java“ programos.

Šioje pamokoje pateikiama trumpa serija, kurioje pristatomos duomenų struktūros ir algoritmai. 1 dalyje sužinosite, kas yra duomenų struktūra ir kaip duomenų struktūros klasifikuojamos. Taip pat sužinosite, kas yra algoritmas, kaip vaizduojami algoritmai ir kaip naudoti laiko ir erdvės sudėtingumo funkcijas norint palyginti panašius algoritmus. Įgiję šiuos pagrindus, 2 dalyje būsite pasirengę sužinoti apie paiešką ir rūšiavimą naudojant vienmates masyvus.

Kas yra duomenų struktūra?

Duomenų struktūros yra pagrįstos abstrakčiais duomenų tipais (ADT), kuriuos Vikipedija apibrėžia taip:

[A] matematinis duomenų tipų modelis, kai duomenų tipą apibrėžia jo elgesys (semantika) duomenų vartotojo požiūriu, ypač atsižvelgiant į galimas vertes, galimas operacijas su šio tipo duomenimis ir elgseną. šių operacijų.

ADT nesvarbu, ar atmintyje vaizduojamos jos vertės, ar kaip vykdomos jos operacijos. Tai tarsi „Java“ sąsaja, kuri yra duomenų tipas, atjungtas nuo bet kokio diegimo. Priešingai, a duomenų struktūra yra konkretus vienos ar kelių ADT įgyvendinimas, panašiai kaip „Java“ klasės įgyvendina sąsajas.

ADT pavyzdžiai yra „Darbuotojas“, „Transporto priemonė“, „Masyvas“ ir „Sąrašas“. Panagrinėkime sąrašą „ADT“ (taip pat žinomą kaip „Sequence ADT“), kuriame aprašoma užsakyta elementų, turinčių bendrą tipą, kolekcija. Kiekvienas šios kolekcijos elementas turi savo poziciją ir leidžiami elementų dublikatai. Pagrindinės operacijos, kurias palaiko „List ADT“, yra šios:

  • Naujo ir tuščio sąrašo kūrimas
  • Vertės pridėjimas sąrašo pabaigoje
  • Vertę įterpiate į sąrašą
  • Vertės ištrynimas iš sąrašo
  • Kartojasi per sąrašą
  • Sunaikinti sąrašą

Duomenų struktūros, galinčios įgyvendinti „ADT List“, apima fiksuoto dydžio ir dinamiško dydžio vieno matmens masyvus ir atskirai susietus sąrašus. (Jums bus pristatyti masyvai 2 dalyje ir susieti sąrašai 3 dalyje.)

Duomenų struktūrų klasifikavimas

Yra daugybė duomenų struktūrų rūšių, pradedant nuo atskirų kintamųjų iki masyvų ar susietų objektų, turinčių kelis laukus, sąrašų. Visos duomenų struktūros gali būti klasifikuojamos kaip primityvai ar suvestinės, o kai kurios - kaip konteineriai.

Pirmykščiai ir agregatai

Paprasčiausia duomenų struktūros rūšis saugo atskirus duomenų elementus; pavyzdžiui, kintamasis, kuriame saugoma Bulio reikšmė, arba kintamasis, kuriame saugomas sveikasis skaičius. Turiu omenyje tokias duomenų struktūras kaip pirmykščiai.

Daugelis duomenų struktūrų gali saugoti kelis duomenų elementus. Pavyzdžiui, masyvas gali saugoti kelis duomenų elementus įvairiuose laiko tarpsniuose, o objektas gali saugoti kelis duomenų elementus per savo laukus. Aš vadinu šias duomenų struktūras kaip agregatai.

Visos duomenų struktūros, kurias apžvelgsime šioje serijoje, yra suvestinės.

Konteineriai

Viskas, iš ko saugomi ir gaunami duomenų elementai, gali būti laikoma duomenų struktūra. Pavyzdžiai apima duomenų struktūras, gautas iš anksčiau paminėtų darbuotojų, transporto priemonių, masyvų ir sąrašų ADT.

Daugybė duomenų struktūrų yra skirtos apibūdinti įvairius objektus. Atvejai AN Darbuotojas klasė yra duomenų struktūros, kurios, pavyzdžiui, apibūdina įvairius darbuotojus. Priešingai, kai kurios duomenų struktūros egzistuoja kaip bendri kitų duomenų struktūrų saugojimo indai. Pavyzdžiui, masyvas gali išsaugoti primityvias reikšmes arba objektų nuorodas. Pastarąją duomenų struktūrų kategoriją vadinu konteineriai.

Visos duomenų struktūros, kurias apžvelgsime šioje serijoje, yra ne tik suvestinės, bet ir sudėtiniai rodiniai.

Duomenų struktūros ir algoritmai „Java“ kolekcijose

„Java Collections Framework“ palaiko daugybę į konteinerius orientuotų duomenų struktūrų ir susijusių algoritmų. Ši serija padės jums geriau suprasti šią sistemą.

Dizaino modeliai ir duomenų struktūros

Tapo gana įprasta naudoti dizaino modelius, kad universiteto studentai būtų supažindinti su duomenų struktūromis. Browno universiteto straipsnyje apžvelgiami keli dizaino modeliai, kurie yra naudingi kuriant aukštos kokybės duomenų struktūras. Be kita ko, dokumente parodyta, kad „Adapter“ modelis yra naudingas kuriant kaminus ir eiles. Parodymo kodas rodomas 1 sąraše.

Sąrašas 1. „Adapter“ modelio naudojimas kaminams ir eilėms (DequeStack.java)

viešosios klasės „DequeStack“ įgyvendina „Stack“ {Deque D; // laiko kamino elementus public DequeStack () {D = new MyDeque (); } @ Nepaisyti viešojo int dydžio () {grąžinti D. dydį (); } @Paisyti viešąją loginę reikšmę isEmpty () {return D.isEmpty (); } @Paisyti viešą tuštumą (Object obj) {D.insertLast (obj); } @Override public Object top () meta „StackEmptyException“ {try {return D.lastElement (); } pagauti (DequeEmptyException klaida) {mesti naują StackEmptyException (); }} @Override public Object pop () meta „StackEmptyException“ {try {return D.removeLast (); } pagauti (DequeEmptyException klaida) {mesti naują StackEmptyException (); }}}

1 sąraše pateikiamos Browno universiteto knygos ištraukos „DequeStack“ klasė, kuri demonstruoja „Adapter“ modelį. Prisimink tai Sukrauti ir Deque yra sąsajos, apibūdinančios „Stack“ ir „Deque ADT“. „MyDeque“ yra klasė, kuri įgyvendina Deque.

Pagrindiniai sąsajos metodai

Originalus kodas, kuriuo grindžiamas 1 sąrašas, nepateikė šaltinio kodo Sukrauti, Dequeir „MyDeque“. Aiškumo dėlei aš įvedžiau @ Nepaisyti anotacijos parodyti, kad visi „DequeStack“nekonstruktoriaus metodai yra svarbesni Sukrauti metodai.

„DequeStack“ prisitaiko „MyDeque“ kad jis galėtų įgyvendinti Sukrauti. Visi „DequeStack“metodas yra vienos linijos skambučiai į Deque sąsajos metodai. Tačiau yra maža raukšlė, kurioje Deque išimtys konvertuojamos į Sukrauti išimtys.

Kas yra algoritmas?

Istoriškai naudojami kaip matematinio skaičiavimo įrankis, algoritmai yra glaudžiai susiję su kompiuterių mokslu ir ypač su duomenų struktūromis. An algoritmas yra nurodymų seka, kuria užduotis įvykdoma per ribotą laiką. Algoritmo savybės yra šios:

  • Gauna nulį ar daugiau įėjimų
  • Sukuria bent vieną išvestį
  • Susideda iš aiškių ir nedviprasmiškų nurodymų
  • Baigiasi atlikus ribotą žingsnių skaičių
  • Yra pakankamai elementarus, kad žmogus galėtų tai atlikti naudodamas pieštuką ir popierių

Atkreipkite dėmesį, kad nors programos gali būti algoritminio pobūdžio, daugelis programų neužbaigia be išorinio įsikišimo.

Daugelis kodų sekų kvalifikuojamos kaip algoritmai. Vienas iš pavyzdžių yra kodų seka, kuria atspausdinama ataskaita. Garsiau tai, kad apskaičiuojant matematinį didžiausią bendrą daliklį naudojamas Euklido algoritmas. Netgi būtų galima teigti, kad pagrindinės duomenų struktūros operacijos (pvz., saugoti vertę masyvo lizde) yra algoritmai. Šioje serijoje daugiausia dėmesio skirsiu aukštesnio lygio algoritmams, naudojamiems duomenų struktūroms apdoroti, tokiems kaip „Dvejetainės paieškos“ ir „Matricos daugybos“ algoritmai.

Blokinės schemos ir pseudokodas

Kaip jūs vaizduojate algoritmą? Parašius kodą prieš visiškai suprantant jo pagrindinį algoritmą, gali atsirasti klaidų, tad kokia geresnė alternatyva? Du variantai yra schemos ir pseudokodas.

Blokinių schemų naudojimas algoritmams pateikti

A schema yra vizualus algoritmo valdymo srauto vaizdas. Šis atvaizdavimas iliustruoja teiginius, kuriuos reikia vykdyti, sprendimus, kuriuos reikia priimti, logikos srautą (iteracijai ir kitiems tikslams) ir terminalus, kurie nurodo pradžios ir pabaigos taškus. 1 paveiksle atskleidžiami įvairūs simboliai, kuriuos schemos naudoja algoritmams vizualizuoti.

Apsvarstykite algoritmą, kuris inicijuoja skaitiklį iki 0, skaito simbolius iki naujos eilutės (\ n) simbolis yra matomas, jis padidina skaitiklį kiekvienam skaitomam simboliui, kuris buvo perskaitytas, ir išspausdina skaitiklio vertę perskaičius naujos eilutės simbolį. 2 schemos schema iliustruoja šio algoritmo valdymo srautą.

Pagrindiniai srauto diagramos paprastumas ir galimybė vizualiai pateikti algoritmo valdymo srautą (kad būtų lengva sekti) yra pagrindiniai jo privalumai. Blokinės schemos taip pat turi keletą trūkumų:

  • Dėl labai nuobodžios, susijusios su jų piešimu, į labai išsamią schemą lengva įvesti klaidų ar netikslumų.
  • Sistemos simbolių išdėstymas, žymėjimas etiketėmis ir sujungimas užtrunka, net naudojant įrankius šiam procesui pagreitinti. Šis uždelsimas gali sulėtinti jūsų supratimą apie algoritmą.
  • Blokinės schemos priklauso struktūrizuoto programavimo erai ir nėra tokios naudingos objektui pritaikytame kontekste. Priešingai, „Unified Modeling Language“ (UML) yra tinkamesnė kuriant objektyvius vaizdinius vaizdus.

Pseudokodo naudojimas algoritmams pateikti

Alternatyva schemoms yra pseudokodas, kuris yra tekstinis algoritmo pateikimas, priartinantis galutinį šaltinio kodą. Pseudokodas yra naudingas greitai užrašant algoritmo vaizdą. Kadangi sintaksė nerūpi, nėra griežtų pseudokodo rašymo taisyklių.

Rašydami pseudokodą turėtumėte siekti nuoseklumo. Jei bus nuoseklus, pseudokodą paversti faktiniu šaltinio kodu bus daug lengviau. Pvz., Apsvarstykite šį pseudokodo atvaizdavimą ankstesnėje priešingos krypties schemoje:

 PASKELBK CHARAKTERĮ ch = '' DEKLARUOKITE INTEGER skaičių = 0 PERSKAITYKITE ch, jei ch GE '0' IR ch LE '9' TADAI skaičius = skaičius + 1 PABAIGA, JEI LIK KAD ch chromas EQ '

Pseudokodas pirmiausia pateikia porą PAREIŠKKITE teiginiai, įvedantys kintamuosius ch ir suskaičiuoti, inicijuojamos pagal numatytąsias vertes. Tada pateikiama a Daryk kilpa, kuri vykdoma IKIch yra \ n (naujos eilutės simbolis), tuo metu kilpa baigiasi ir a SPAUSDINTI pareiškimo išvestys suskaičiuotivertė.

Kiekvienai kilpos iteracijai SKAITYKITE simbolis perskaitomas iš klaviatūros (o gal failo - šiuo atveju nesvarbu, kas yra pagrindinis įvesties šaltinis) ir priskiriamas ch. Jei šis simbolis yra skaitmuo (vienas iš 0 per 9), suskaičiuoti yra padidinamas 1.

Tinkamo algoritmo pasirinkimas

Jūsų naudojamos duomenų struktūros ir algoritmai kritiškai veikia du jūsų programų veiksnius:

  1. Atminties naudojimas (duomenų struktūroms).
  2. Procesoriaus laikas (algoritmams, kurie sąveikauja su tomis duomenų struktūromis).

Iš to išplaukia, kad turėtumėte ypač atsižvelgti į algoritmus ir duomenų struktūras, kuriuos naudojate programoms, kurios apdoros daug duomenų. Tai apima programas, naudojamas didiesiems duomenims ir daiktų internetui.

Atminties ir procesoriaus subalansavimas

Pasirinkdami duomenų struktūrą ar algoritmą, kartais atrasite atvirkštinis santykis tarp atminties naudojimo ir procesoriaus laiko: kuo mažiau atminties naudoja duomenų struktūra, tuo daugiau su procesoriumi susijusių laiko algoritmų reikia apdoroti duomenų struktūros duomenų elementus. Be to, kuo daugiau atminties naudoja duomenų struktūra, tuo mažiau algoritmams, susijusiems su procesoriaus laiku, reikės apdoroti duomenų elementus, kad būtų gauti greitesni algoritmo rezultatai.

Kiek įmanoma, turėtumėte stengtis subalansuoti atminties naudojimą ir procesoriaus laiką. Šią užduotį galite supaprastinti analizuodami algoritmus, kad nustatytumėte jų efektyvumą. Ar gerai vienas algoritmas veikia prieš kitą panašaus pobūdžio algoritmą? Atsakymas į šį klausimą padės jums tinkamai pasirinkti, pasirinkus kelis algoritmus.

Algoritmo efektyvumo matavimas

Kai kurie algoritmai veikia geriau nei kiti. Pvz., Dvejetainės paieškos algoritmas beveik visada yra efektyvesnis nei tiesinės paieškos algoritmas - tai pamatysite patys 2 dalyje. Norite pasirinkti efektyviausią algoritmą savo programos poreikiams, tačiau šis pasirinkimas gali būti ne toks akivaizdus kaip pagalvotum.

Pavyzdžiui, ką tai reiškia, jei „Selection Sort“ algoritmas (pristatytas 2 dalyje) užtrunka 0,4 sekundės, norint surūšiuoti 10 000 sveikųjų skaičių tam tikroje mašinoje? Tas etalonas galioja tik konkrečiai mašinai, tam tikram algoritmo įgyvendinimui ir įvesties duomenų dydžiui.

Būdami kompiuterių mokslininkai, mes naudojame laiko ir erdvės sudėtingumą matuodami algoritmo efektyvumą, išskirstydami juos į sudėtingumo funkcijos abstrakti įgyvendinimo ir vykdymo laiko aplinkos detalės. Sudėtingumo funkcijos atskleidžia algoritmo laiko ir vietos poreikių dispersiją, atsižvelgiant į įvesties duomenų kiekį:

  • A laiko sudėtingumo funkcija matuoja algoritmą laiko sudėtingumas- reiškia, kiek užtrunka algoritmo užbaigimas.
  • A erdvės sudėtingumo funkcija matuoja algoritmą kosmoso sudėtingumas- reiškia algoritmo užduočiai atlikti reikalingą atminties kiekį.

Abi sudėtingumo funkcijos pagrįstos įvesties dydžiu (n), kuris kažkaip atspindi įvesties duomenų kiekį. Apsvarstykite šį pseudokodą spausdindami masyvą:

 PAREIŠKKITE „INTEGER“ i, x [] = [10, 15, -1, 32], jei i = 0 - ILGUMAS (x) - 1 SPAUSDINIMAS x [i] KITAS i PABAIGA

Laiko sudėtingumo ir laiko sudėtingumo funkcijos

Galite išreikšti šio algoritmo laiko sudėtingumą nurodydami laiko sudėtingumo funkciją t (n) = an+ b, kur a (pastovus daugiklis) nurodo laiko trukmę vienos ciklo iteracijos užbaigimui ir b nurodo algoritmo nustatymo laiką. Šiame pavyzdyje laiko sudėtingumas yra tiesinis.

$config[zx-auto] not found$config[zx-overlay] not found