Datastrukturer og algoritmer i Java, del 1: Oversigt

Java-programmører bruger datastrukturer til at gemme og organisere data, og vi bruger algoritmer til at manipulere dataene i disse strukturer. Jo mere du forstår om datastrukturer og algoritmer, og hvordan de arbejder sammen, jo mere effektive bliver dine Java-programmer.

Denne tutorial lancerer en kort serie, der introducerer datastrukturer og algoritmer. I del 1 lærer du, hvad en datastruktur er, og hvordan datastrukturer klassificeres. Du lærer også, hvad en algoritme er, hvordan algoritmer er repræsenteret, og hvordan man bruger tid og rums kompleksitetsfunktioner til at sammenligne lignende algoritmer. Når du har fået disse grundlæggende, vil du være klar til at lære om søgning og sortering med endimensionelle arrays, i del 2.

Hvad er en datastruktur?

Datastrukturer er baseret på abstrakte datatyper (ADT), som Wikipedia definerer som følger:

[A] matematisk model for datatyper, hvor en datatype defineres af dens adfærd (semantik) set fra en bruger af dataets synspunkt, specifikt med hensyn til mulige værdier, mulige operationer på data af denne type og adfærd af disse operationer.

En ADT er ligeglad med hukommelsesrepræsentationen af ​​dens værdier eller hvordan dens operationer implementeres. Det er som en Java-grænseflade, som er en datatype, der er afbrudt fra enhver implementering. I modsætning hertil a datastruktur er en konkret implementering af en eller flere ADT'er, svarende til hvordan Java-klasser implementerer grænseflader.

Eksempler på ADT'er inkluderer medarbejder, køretøj, matrix og liste. Overvej listen ADT (også kendt som Sequence ADT), som beskriver en ordnet samling af elementer, der deler en fælles type. Hvert element i denne samling har sin egen position, og duplikatelementer er tilladt. Grundlæggende operationer understøttet af List ADT inkluderer:

• Oprettelse af en ny og tom liste
• Tilføje en værdi til slutningen af ​​listen
• Indsættelse af en værdi på listen
• Sletning af en værdi fra listen
• Itererer over listen
• Ødelægger listen

Datastrukturer, der kan implementere List ADT, inkluderer endimensionelle arrays i fast størrelse og dynamisk størrelse og enkeltkoblede lister. (Du bliver introduceret til arrays i del 2 og sammenkædede lister i del 3.)

Klassificering af datastrukturer

Der er mange slags datastrukturer, der spænder fra enkelte variabler til arrays eller sammenkædede lister over objekter, der indeholder flere felter. Alle datastrukturer kan klassificeres som primitiver eller aggregater, og nogle klassificeres som containere.

Primitiver vs aggregater

Den enkleste form for datastruktur gemmer enkelt dataelementer; for eksempel en variabel, der gemmer en boolsk værdi, eller en variabel, der gemmer et heltal. Jeg henviser til sådanne datastrukturer som primitiver.

Mange datastrukturer er i stand til at lagre flere dataelementer. For eksempel kan en matrix gemme flere dataelementer i dens forskellige slots, og et objekt kan gemme flere dataelementer via dets felter. Jeg henviser til disse datastrukturer som aggregater.

Alle datastrukturer, vi vil se på i denne serie, er aggregater.

Beholdere

Alt, hvorfra dataelementer gemmes og hentes, kan betragtes som en datastruktur. Eksempler inkluderer datastrukturer afledt af de tidligere nævnte ADT'er for medarbejder, køretøj, matrix og liste.

Mange datastrukturer er designet til at beskrive forskellige enheder. Forekomster af en Medarbejder klasse er datastrukturer, der findes for f.eks. at beskrive forskellige medarbejdere. Derimod eksisterer nogle datastrukturer som generiske lagringsbeholdere til andre datastrukturer. For eksempel kan en matrix gemme primitive værdier eller objektreferencer. Jeg henviser til denne sidstnævnte kategori af datastrukturer som containere.

Ud over at være aggregater er alle datastrukturer, vi ser på i denne serie, containere.

Datastrukturer og algoritmer i Java Collections

Java Collections Framework understøtter mange slags containerorienterede datastrukturer og tilknyttede algoritmer. Denne serie hjælper dig med bedre at forstå denne ramme.

Design mønstre og datastrukturer

Det er blevet ret almindeligt at bruge designmønstre til at introducere universitetsstuderende til datastrukturer. Et papir fra Brown University undersøger flere designmønstre, der er nyttige til at designe datastrukturer af høj kvalitet. Blandt andet demonstrerer papiret, at adaptermønsteret er nyttigt til design af stakke og køer. Demonstrationskoden vises i liste 1.

Fortegnelse 1. Brug af adaptermønsteret til stakke og køer (DequeStack.java)

offentlig klasse DequeStack implementerer Stack {Deque D; // holder elementerne i stakken offentlige DequeStack () {D = nye MyDeque (); } @ Override public int-størrelse () {returner D. størrelse (); } @ Override public boolean isEmpty () {return D.isEmpty (); } @ Overstyr offentlig ugyldigt skub (Objekt obj) {D.insertLast (obj); } @ Override public Object top () kaster StackEmptyException {prøv {return D.lastElement (); } fange (DequeEmptyException err) {kast ny StackEmptyException (); }} @ Override public Object pop () kaster StackEmptyException {prøv {returner D.removeLast (); } fange (DequeEmptyException err) {kast ny StackEmptyException (); }}}

Notering 1 uddrag af Brown University-papirerne DequeStack klasse, som demonstrerer adaptermønsteret. Noter det Stak og Deque er grænseflader, der beskriver Stack og Deque ADT'er. MyDeque er en klasse, der implementerer Deque.

Overstyrende grænseflademetoder

Den originale kode, som Listing 1 er baseret på, præsenterede ikke kildekoden for Stak, Dequeog MyDeque. For klarhedens skyld har jeg introduceret det @Override bemærkninger for at vise, at alle DequeStack's ikke-konstruktørmetoder tilsidesætter Stak metoder.

DequeStack tilpasser sig MyDeque så det kan implementeres Stak. Alt af DequeStack's metode er enlinjekald til Deque grænseflades metoder. Der er dog en lille rynke, hvori Deque undtagelser konverteres til Stak undtagelser.

Hvad er en algoritme?

Historisk anvendt som et værktøj til matematisk beregning, er algoritmer dybt forbundet med datalogi og især datastrukturer. En algoritme er en sekvens af instruktioner, der udfører en opgave i et begrænset tidsrum. En algoritmes kvaliteter er som følger:

• Modtager nul eller flere input
• Producerer mindst en output
• Består af klare og utvetydige instruktioner
• Afslutter efter et endeligt antal trin
• Er grundlæggende nok til, at en person kan udføre det ved hjælp af blyant og papir

Bemærk, at mens programmer kan være algoritmiske, ophører mange programmer ikke uden ekstern indblanding.

Mange kodesekvenser betegnes som algoritmer. Et eksempel er en kodesekvens, der udskriver en rapport. Mere berømt bruges Euclids algoritme til at beregne den matematiske største fælles skiller. Der kan endda gøres en sag om, at en datastrukturs grundlæggende operationer (f.eks gem værdi i array slot) er algoritmer. I denne serie vil jeg for det meste fokusere på algoritmer på højere niveau, der bruges til at behandle datastrukturer, såsom Binary Search og Matrix Multiplication algoritmer.

Flowcharts og pseudokode

Hvordan repræsenterer du en algoritme? Skrivning af kode før fuld forståelse af den underliggende algoritme kan føre til fejl, så hvad er et bedre alternativ? To muligheder er flowcharts og pseudocode.

Brug af flowcharts til at repræsentere algoritmer

EN flowchart er en visuel repræsentation af en algoritmes kontrolflow. Denne repræsentation illustrerer udsagn, der skal udføres, beslutninger, der skal træffes, logisk flow (til iteration og andre formål) og terminaler, der indikerer start- og slutpunkter. Figur 1 afslører de forskellige symboler, som rutediagrammer bruger til at visualisere algoritmer.

Overvej en algoritme, der initialiserer en tæller til 0, læser tegn indtil en ny linje (\ n) tegn ses, forøger tælleren for hvert cifret tegn, der er blevet læst, og udskriver tællerens værdi, efter at den nye linjetegn er blevet læst. Flowdiagrammet i figur 2 illustrerer denne algoritmes kontrolflow.

Et flowcharts enkelhed og dets evne til at præsentere en algoritmes kontrolflow visuelt (så det er let at følge) er dets største fordele. Flowcharts har også flere ulemper, dog:

• Det er let at indføre fejl eller unøjagtigheder i meget detaljerede rutediagrammer på grund af det kedsomhed, der er forbundet med at tegne dem.
• Det tager tid at placere, mærke og forbinde et flowcharts symboler, selv ved hjælp af værktøjer til at fremskynde denne proces. Denne forsinkelse kan nedsætte din forståelse af en algoritme.
• Flowcharts tilhører den strukturerede programmerings æra og er ikke så nyttige i en objektorienteret sammenhæng. I modsætning hertil er Unified Modeling Language (UML) mere passende til at skabe objektorienterede visuelle repræsentationer.

Brug af pseudokode til at repræsentere algoritmer

Et alternativ til flowcharts er pseudokode, som er en tekstlig repræsentation af en algoritme, der tilnærmer sig den endelige kildekode. Pseudokode er nyttig til hurtig nedskrivning af en algoritmes repræsentation. Fordi syntaksen ikke er et problem, er der ingen hurtige regler for skrivning af pseudokode.

Du skal stræbe efter konsistens, når du skriver pseudokode. At være konsekvent gør det meget lettere at oversætte pseudokoden til den faktiske kildekode. Overvej f.eks. Følgende pseudokode-gengivelse af det tidligere modorienterede rutediagram:

 ERKLÆR TEGN ch = '' ERKLÆR INTEGER-tælling = 0 LÆS LÆS HVIS ch GE '0' OG ch LE '9' DAN tæller = tæller + 1 SLUT HVIS TIL ch EQ '\ n' PRINT tæller SLUT

Pseudokoden præsenterer først et par ERKLÆRE udsagn, der introducerer variabler ch og tælle, initialiseret til standardværdier. Derefter præsenterer det en Gør loop, der udføres SÅ LÆNGEch indeholder \ n (den nye linjetegn), på hvilket tidspunkt sløjfen slutter og a PRINT udsagn output tælleværdi.

For hver loop-iteration, LÆS får et tegn til at læses fra tastaturet (eller måske en fil - i dette tilfælde betyder det ikke noget, hvad der udgør den underliggende inputkilde) og tildeles ch. Hvis dette tegn er et ciffer (et af 0 igennem 9), tælle øges af 1.

Valg af den rigtige algoritme

Datastrukturer og algoritmer, du bruger, påvirker to faktorer i dine applikationer kritisk:

1. Hukommelsesforbrug (til datastrukturer).
2. CPU-tid (for algoritmer, der interagerer med disse datastrukturer).

Det følger heraf, at du skal være særlig opmærksom på de algoritmer og datastrukturer, du bruger til applikationer, der behandler masser af data. Disse inkluderer applikationer, der bruges til big data og Internet of Things.

Balancering af hukommelse og CPU

Når du vælger en datastruktur eller algoritme, vil du nogle gange opdage en omvendt forhold mellem hukommelsesforbrug og CPU-tid: jo mindre hukommelse en datastruktur bruger, jo mere CPU-tidstilknyttede algoritmer har brug for at behandle datastrukturens dataelementer. Jo mere hukommelse en datastruktur bruger, desto mindre CPU-tidstilknyttede algoritmer har brug for at behandle dataelementerne - hvilket fører til hurtigere algoritmeresultater.

Så meget som muligt skal du stræbe efter at afbalancere hukommelsesforbrug med CPU-tid. Du kan forenkle denne opgave ved at analysere algoritmer for at bestemme deres effektivitet. Hvor godt fungerer en algoritme mod en anden af ​​lignende art? Besvarelse af dette spørgsmål hjælper dig med at træffe gode valg, hvis du vælger mellem flere algoritmer.

Måling af algoritmeeffektivitet

Nogle algoritmer fungerer bedre end andre. For eksempel er binær søgealgoritmen næsten altid mere effektiv end den lineære søgealgoritme - noget du vil se selv i del 2. Du vil vælge den mest effektive algoritme til din applikations behov, men dette valg er muligvis ikke så indlysende som du ville tro.

Hvad betyder det f.eks., Hvis Selection Sort-algoritmen (introduceret i del 2) tager 0,4 sekunder at sortere 10.000 heltal på en given maskine? Dette benchmark er kun gyldigt for den pågældende maskine, den specifikke implementering af algoritmen og for størrelsen af ​​inputdataene.

Som computerforsker bruger vi tidskompleksitet og rumkompleksitet til at måle en algoritmes effektivitet og destillere disse i kompleksitetsfunktioner til abstrakt implementering og runtime miljøoplysninger. Kompleksitetsfunktioner afslører variansen i en algoritmes tids- og rumkrav baseret på mængden af ​​inputdata:

• EN tidskompleksitetsfunktion måler en algoritme tidskompleksitet- hvilket betyder, hvor lang tid en algoritme tager at fuldføre.
• EN rum-kompleksitet funktion måler en algoritme plads kompleksitet- hvilket betyder den mængde hukommelsesomkostninger, der kræves af algoritmen for at udføre sin opgave.

Begge kompleksitetsfunktioner er baseret på størrelsen på input (n), som på en eller anden måde afspejler mængden af ​​inputdata. Overvej følgende pseudokode til array-udskrivning:

 ERKLÆR INTEGER i, x [] = [10, 15, -1, 32] FOR i = 0 TIL LÆNGDE (x) - 1 UDSKRIV x [i] NÆSTE I SLUT

Tidskompleksitet og tidskompleksitetsfunktioner

Du kan udtrykke tidskompleksiteten af ​​denne algoritme ved at specificere tidskompleksitetsfunktionen t (n) = an+ b, hvor -en (en konstant multiplikator) repræsenterer den tid, det tager at gennemføre en loop-iteration, og b repræsenterer algoritmens opsætningstid. I dette eksempel er tidskompleksiteten lineær.