Datastrukturer og algoritmer i Java, del 1: oversikt

Java-programmerere bruker datastrukturer for å lagre og organisere data, og vi bruker algoritmer for å manipulere dataene i disse strukturene. Jo mer du forstår om datastrukturer og algoritmer, og hvordan de fungerer sammen, jo mer effektive blir Java-programmene dine.

Denne opplæringen lanserer en kort serie som introduserer datastrukturer og algoritmer. I del 1 lærer du hva en datastruktur er og hvordan datastrukturer er klassifisert. Du lærer også hva en algoritme er, hvordan algoritmer er representert, og hvordan du bruker tids- og romkompleksitetsfunksjoner for å sammenligne lignende algoritmer. Når du har disse grunnleggende, vil du være klar til å lære om søk og sortering med endimensjonale matriser, i del 2.

Hva er en datastruktur?

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

[A] matematisk modell for datatyper der en datatype defineres av dens oppførsel (semantikk) fra en bruker av dataene, spesielt når det gjelder mulige verdier, mulige operasjoner på data av denne typen og oppførsel av disse operasjonene.

En ADT bryr seg ikke om minnepresentasjonen av verdiene eller hvordan dens operasjoner implementeres. Det er som et Java-grensesnitt, som er en datatype som er koblet fra enhver implementering. I kontrast, a data struktur er en konkret implementering av en eller flere ADT-er, som ligner på hvordan Java-klasser implementerer grensesnitt.

Eksempler på ADT inkluderer medarbeider, kjøretøy, matrise og liste. Tenk på listen ADT (også kjent som Sequence ADT), som beskriver en ordnet samling av elementer som har en felles type. Hvert element i denne samlingen har sin egen posisjon, og dupliserte elementer er tillatt. Grunnleggende operasjoner som støttes av List ADT inkluderer:

• Opprette en ny og tom liste
• Legge til en verdi til slutten av listen
• Sette inn en verdi i listen
• Slette en verdi fra listen
• Itererer over listen
• Ødelegger listen

Datastrukturer som kan implementere List ADT inkluderer faste størrelser og dynamisk størrelse endimensjonale matriser og enkeltkoblede lister. (Du blir introdusert for matriser i del 2, og koblede lister i del 3.)

Klassifisering av datastrukturer

Det er mange typer datastrukturer, alt fra enkeltvariabler til matriser eller koblede lister over objekter som inneholder flere felt. Alle datastrukturer kan klassifiseres som primitiver eller aggregater, og noen er klassifisert som containere.

Primitiver vs aggregater

Den enkleste typen datastruktur lagrer enkelt dataelementer; for eksempel en variabel som lagrer en boolsk verdi eller en variabel som lagrer et heltall. Jeg refererer til slike datastrukturer som primitiver.

Mange datastrukturer er i stand til å lagre flere dataelementer. For eksempel kan en matrise lagre flere dataelementer i sine forskjellige spor, og et objekt kan lagre flere dataelementer via sine felt. Jeg refererer til disse datastrukturene som aggregater.

Alle datastrukturene vi ser på i denne serien er aggregater.

Beholdere

Alt som dataelementene lagres og hentes fra, kan betraktes som en datastruktur. Eksempler inkluderer datastrukturene avledet fra de tidligere nevnte ADT-ene for ansatt, kjøretøy, matrise og liste.

Mange datastrukturer er designet for å beskrive forskjellige enheter. Forekomster av en Ansatt klasse er datastrukturer som eksisterer for å beskrive forskjellige ansatte, for eksempel. I motsetning til det eksisterer noen datastrukturer som generiske lagringsskip for andre datastrukturer. For eksempel kan en matrise lagre primitive verdier eller objektreferanser. Jeg refererer til denne sistnevnte kategorien av datastrukturer som containere.

I tillegg til å være aggregater, er alle datastrukturene vi ser på i denne serien containere.

Datastrukturer og algoritmer i Java Collections

Java Collections Framework støtter mange typer containerorienterte datastrukturer og tilknyttede algoritmer. Denne serien vil hjelpe deg med å forstå dette rammeverket bedre.

Design mønstre og datastrukturer

Det har blitt ganske vanlig å bruke designmønstre for å introdusere universitetsstudenter til datastrukturer. Et papir fra Brown University undersøker flere designmønstre som er nyttige for å designe datastrukturer av høy kvalitet. Blant annet viser papiret at adaptermønsteret er nyttig for å designe stabler og køer. Demonstrasjonskoden vises i liste 1.

Oppføring 1. Bruke adaptermønsteret for stabler og køer (DequeStack.java)

offentlig klasse DequeStack implementerer Stack {Deque D; // holder elementene i stakken offentlig DequeStack () {D = ny 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 toppen () kaster StackEmptyException {prøv {return D.lastElement (); } fange (DequeEmptyException err) {kast ny StackEmptyException (); }} @ Override public Object pop () kaster StackEmptyException {prøv {return D.removeLast (); } fange (DequeEmptyException err) {kast ny StackEmptyException (); }}}

Oppføring 1 utdrag av Brown University-papirene DequeStack klasse, som demonstrerer adaptermønsteret. Noter det Stable og Deque er grensesnitt som beskriver ADTer fra Stack og Deque. MyDeque er en klasse som implementerer Deque.

Overstyrende grensesnittmetoder

Den opprinnelige koden som Listing 1 er basert på, presenterte ikke kildekoden for Stable, Deque, og MyDeque. For klarhetens skyld har jeg introdusert @Overstyring kommentarer for å vise at alle DequeStacksine ikke-konstruktørmetoder overstyrer Stable metoder.

DequeStack tilpasser seg MyDeque slik at den kan implementeres Stable. Alt DequeStackmetoden er enlinjeanrop til Deque grensesnittets metoder. Imidlertid er det en liten rynke der Deque unntak blir omgjort til Stable unntak.

Hva er en algoritme?

Historisk brukt som et verktøy for matematisk beregning, er algoritmer dypt forbundet med datavitenskap, og spesielt med datastrukturer. An algoritme er en sekvens av instruksjoner som utfører en oppgave i en begrenset periode. Kvaliteten til en algoritme er som følger:

• Mottar null eller flere innganger
• Produserer minst en utgang
• Består av klare og entydige instruksjoner
• Avslutter etter et endelig antall trinn
• Er grunnleggende nok til at en person kan utføre det med blyant og papir

Vær oppmerksom på at selv om programmer kan være algoritmiske, avslutter ikke mange programmer uten ekstern intervensjon.

Mange kodesekvenser kvalifiserer som algoritmer. Et eksempel er en kodesekvens som skriver ut en rapport. Mer kjent er Euclids algoritme brukt til å beregne den matematiske største fellesdeleren. Det kan til og med gjøres en sak om at en datastrukturs grunnleggende operasjoner (som f.eks lagre verdi i array-spor) er algoritmer. I denne serien vil jeg for det meste fokusere på algoritmer på høyere nivå som brukes til å behandle datastrukturer, som Binary Search og Matrix Multiplication algoritmer.

Flytskjemaer og pseudokode

Hvordan representerer du en algoritme? Å skrive kode før du forstår den underliggende algoritmen, kan føre til feil, så hva er et bedre alternativ? To alternativer er flytskjemaer og pseudokode.

Bruke flytskjemaer for å representere algoritmer

EN flytskjema er en visuell fremstilling av en algoritmes kontrollflyt. Denne representasjonen illustrerer utsagn som må utføres, beslutninger som må tas, logikkflyt (for iterasjon og andre formål) og terminaler som indikerer start- og sluttpunkter. Figur 1 viser de forskjellige symbolene som flytskjemaer bruker for å visualisere algoritmer.

Vurder en algoritme som initialiserer en teller til 0, leser tegn til en ny linje (\ n) vises, øker telleren for hvert siffertegn som er lest, og skriver ut tellerens verdi etter at den nye linjetegnet er lest. Flytskjemaet i figur 2 illustrerer denne algoritmens kontrollflyt.

Et flytskjerms enkelhet og dets evne til å presentere en algoritmes kontrollflyt visuelt (slik at det er enkelt å følge) er de viktigste fordelene. Flytskjemaer har også flere ulemper, men:

• Det er enkelt å introdusere feil eller unøyaktigheter i svært detaljerte flytskjemaer på grunn av kjedsomheten knyttet til å tegne dem.
• Det tar tid å posisjonere, merke og koble til et flytskjerms symboler, til og med å bruke verktøy for å øke hastigheten på denne prosessen. Denne forsinkelsen kan redusere forståelsen av en algoritme.
• Flytskjemaer tilhører den strukturerte programmeringstiden og er ikke like nyttige i en objektorientert kontekst. I motsetning er Unified Modeling Language (UML) mer hensiktsmessig for å lage objektorienterte visuelle representasjoner.

Bruke pseudokode for å representere algoritmer

Et alternativ til flytskjemaer er pseudokode, som er en tekstlig fremstilling av en algoritme som tilnærmer seg den endelige kildekoden. Pseudokode er nyttig for raskt å skrive ned en algoritmes representasjon. Fordi syntaksen ikke er en bekymring, er det ingen harde og raske regler for å skrive pseudokode.

Du bør strebe etter konsistens når du skriver pseudokode. Å være konsistent vil gjøre det mye enklere å oversette pseudokoden til faktisk kildekode. Tenk for eksempel på følgende pseudokode-fremstilling av det forrige motorienterte flytskjemaet:

 ERKLAR TEGN ch = '' ERKLÆR INTEGER-teller = 0 LES LES HVIS ch GE '0' OG ch LE '9' DERetter teller = teller + 1 SLUT HVIS TIL ch EQ '\ n' PRINT count END

Pseudokoden presenterer først et par ERKLÆRE utsagn som introduserer variabler ch og telle, initialisert til standardverdier. Den presenterer deretter en GJØRE løkke som kjøres FØRch inneholder \ n (den nye linjekarakteren), hvor sløyfen slutter og a SKRIVE UT uttalelsesutganger telleverdi.

For hver loop iterasjon, LESE får et tegn til å bli lest fra tastaturet (eller kanskje en fil - i dette tilfellet spiller det ingen rolle hva som utgjør den underliggende inngangskilden) og tilordnes ch. Hvis dette tegnet er et siffer (ett av 0 gjennom 9), telle økes av 1.

Velge riktig algoritme

Datastrukturene og algoritmene du bruker, påvirker to faktorer i applikasjonene dine kritisk:

1. Minnebruk (for datastrukturer).
2. CPU-tid (for algoritmer som samhandler med disse datastrukturene).

Det følger av at du bør være spesielt oppmerksom på algoritmene og datastrukturene du bruker for applikasjoner som vil behandle mye data. Disse inkluderer applikasjoner som brukes til big data og Internet of Things.

Balanserer minne og CPU

Når du velger en datastruktur eller algoritme, vil du noen ganger oppdage en omvendt forhold mellom minnebruk og CPU-tid: jo mindre minne en datastruktur bruker, jo mer trenger CPU-tidstilknyttede algoritmer for å behandle datastrukturens dataelementer. Dessuten, jo mer minne en datastruktur bruker, jo mindre trenger CPU-tid tilknyttede algoritmer for å behandle dataelementene - noe som fører til raskere algoritmeresultater.

Så mye som mulig, bør du prøve å balansere minnebruk med CPU-tid. Du kan forenkle denne oppgaven ved å analysere algoritmer for å bestemme effektiviteten. Hvor bra fungerer en algoritme mot en annen av lignende karakter? Å svare på dette spørsmålet vil hjelpe deg med å ta gode valg gitt et valg mellom flere algoritmer.

Måling av algoritmeeffektivitet

Noen algoritmer fungerer bedre enn andre. For eksempel er Binary Search-algoritmen nesten alltid mer effektiv enn Linear Search-algoritmen - noe du vil se selv i del 2. Du vil velge den mest effektive algoritmen for applikasjonens behov, men det valget er kanskje ikke så opplagt som du skulle tro.

For eksempel, hva betyr det hvis valgsorteringsalgoritmen (introdusert i del 2) tar 0,4 sekunder å sortere 10.000 heltall på en gitt maskin? Denne referansen er bare gyldig for den aktuelle maskinen, den spesielle implementeringen av algoritmen og for størrelsen på inngangsdataene.

Som informatiker bruker vi tidskompleksitet og romkompleksitet for å måle en algoritmes effektivitet, og destillere disse til kompleksitetsfunksjoner å abstrakte implementering og kjøretidsmiljødetaljer. Kompleksitetsfunksjoner avslører avviket i en algoritmes tids- og romkrav basert på mengden inngangsdata:

• EN tidskompleksitetsfunksjon måler en algoritme tidskompleksitet- som betyr hvor lang tid en algoritme tar å fullføre.
• EN rom-kompleksitet funksjon måler en algoritme romkompleksitet- som betyr hvor mye minneoverhead som kreves av algoritmen for å utføre oppgaven.

Begge kompleksitetsfunksjonene er basert på størrelsen på inngangen (n), som på en eller annen måte gjenspeiler mengden inngangsdata. Vurder følgende pseudokode for matrixutskrift:

 ERKLÆR INTEGER i, x [] = [10, 15, -1, 32] FOR i = 0 TIL LENGDE (x) - 1 UTSKRIFT x [i] NESTE i SLUTT

Tidskompleksitet og tidskompleksitetsfunksjoner

Du kan uttrykke tidskompleksiteten til denne algoritmen ved å spesifisere funksjonen for tidskompleksitet t (n) = an+ b, hvor en (en konstant multiplikator) representerer hvor lang tid det er å fullføre en loop-iterasjon, og b representerer algoritmens oppsettstid. I dette eksemplet er tidskompleksiteten lineær.