Tips om bruk av samlinger

1. Liste over samlinger

Som du kanskje husker, har Java samlinger - et hendig verktøy for å lagre objekter av samme type.

La oss prøve å huske de viktigste samlingsrelaterte grensesnittene:

Liste , Sett , Kart og Kø .

Som vanlig er verktøy ikke nødvendigvis gode eller dårlige - det som betyr noe er om du bruker dem til det tiltenkte formålet. Og for å gjøre det, må vi grundig forstå deres spesifikke funksjoner for å vite hvilken samling vi skal bruke og når.

1. Liste

La oss starte med den mest brukte samlingen.

List så nært som mulig til en vanlig gammel array.

Denne samlingen lar oss enkelt lagre en liste over objekter av samme type uten å bekymre oss for størrelsen på selve samlingen, slik vi ville ha gjort hvis vi brukte en matrise. Elementer i samlingen er tilgjengelig via indeks. Hvis vi vet nøyaktig hvor et objekt er og trenger å få tilgang til det ofte uten ofte å måtte legge til eller fjerne elementer, er en liste ideell.

2. Sett

Settet har en helt annen struktur.

Settet egner seg best når vi skal lagre unike gjenstander. For eksempel et sett med forfattere i et bibliotek der hver forfatter er unik. Men vi kan ikke bare gå og hente en spesifikk forfatter fra den. Sett lar oss raskt sjekke om en bestemt forfatter er til stede i biblioteket vårt, dvs. vi kan sjekke om et unikt objekt er tilstede i et sett . Vi kan også iterere over hele samlingen, få tilgang til hvert element, men å gjøre det er ikke optimalt.

Med andre ord, for biblioteket vårt kan et sett representere samlingen til alle unike forfattere for raskt å sjekke om en bestemt forfatter er til stede.

3. Kart

Kart er mer som et arkivskap, der hver fil er signert og kan lagre individuelle objekter eller hele strukturer. Kart bør brukes i tilfeller der vi trenger å opprettholde en kartlegging fra en verdi til en annen.

For Map kalles disse relasjonene nøkkelverdi-par.

Vi kan bruke denne strukturen i biblioteket vårt ved å bruke forfatterobjekter som nøkler og lister ( listeobjekter ) av bøker som verdier. Derfor, etter å ha sjekket et sett for å se om et forfatterobjekt finnes i biblioteket, kan vi bruke det samme forfatterobjektet for å få en liste over bøkene hans eller hennes fra et kart .

4. Kø

Queue er en samling som — overraskelse! — implementerer oppførselen til en kø. Og køen kan være enten LIFO (sist inn, først ut) eller FIFO (først inn, først ut). Dessuten kan køen være toveis, eller "dobbeltende".

Denne strukturen er nyttig når objektene som er lagt til klassen, må brukes i den rekkefølgen de mottas. Ta for eksempel biblioteket vårt.

Vi kan legge til nyankomne besøkende i en kø og betjene dem etter tur, og utstede bøkene de kommer for.

Som vi kan se, er hver av disse strukturene bra hvis de brukes til det tiltenkte formålet. Og vi fant gode bruksområder for alle fire typer samlinger i et enkelt bibliotekeksempel.

2. Kompleksitet

Som allerede nevnt, er samlingene vi vurderte ovenfor grensesnitt, noe som betyr at de må ha implementeringer for at vi skal kunne bruke dem.

Akkurat som å hamre spiker med et mikroskop ikke er den beste ideen, er ikke hver implementering av en samling egnet for enhver situasjon.

Når vi velger riktig verktøy for en jobb, ser vi vanligvis på 2 egenskaper:

• Hvor godt passer verktøyet til jobben?
• Hvor raskt vil det få jobben gjort?

Vi har brukt litt tid på å finne ut hvordan vi skal velge et passende verktøy for en jobb, men hastigheten er noe nytt.

I databehandling uttrykkes et verktøys hastighet ofte i form av tidskompleksitet og betegnes med stor bokstav O.

Hva i all verden er tidskompleksitet?

Enkelt sagt indikerer tidskompleksitet tiden det tar for en algoritme i samlingen å utføre en bestemt handling (legge til/fjerne et element, søke etter et element).

ArrayList vs LinkedList

La oss se på dette ved å bruke to implementeringer av List- grensesnittet - ArrayList og LinkedList .

For ytre utseende er det likt å jobbe med disse samlingene:

List<String> arrayList = new ArrayList<>();
arrayList.add(String);
arrayList.get(index);
arrayList.remove(index);
arrayList.remove(String);
 
List<String> linkedList = new LinkedList<>();
 
linkedList.add(String);
 
linkedList.get(index);
linkedList.remove(index);
linkedList.remove(String);
    

Som du kan se, ser det likt ut for begge samlingstyper å legge til, hente og fjerne elementer. Dette er fordi dette er implementeringer på samme grensesnitt. Men det er der likhetene slutter.

På grunn av deres forskjellige implementeringer av List- grensesnittet, utfører disse to strukturene forskjellige handlinger mer effektivt enn andre.

Vurder å fjerne og legge til et element.

Hvis vi trenger å fjerne et element fra midten av en ArrayList , må vi overskrive den delen av listen som følger etter elementet vi fjerner.

Anta at vi har en liste med 5 elementer og vi ønsker å fjerne den tredje.

List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
list.remove(2);
    

I dette tilfellet frigjør fjerningen en celle, så vi må skrive det 4. elementet der det 3. var, og det 5. hvor det 4. var.

Dette er svært ineffektivt.

Det samme skjer når du legger til et element midt på listen.

LinkedList er strukturert annerledes. Det går raskt å legge til eller fjerne elementer, siden vi bare trenger å endre referansene i de forrige og neste elementene, og dermed ekskludere objektet vi fjerner fra kjeden av elementer.

For å gå tilbake til eksemplet med den samme listen med 5 elementer, etter å ha fjernet det tredje elementet, er alt vi trenger å gjøre ganske enkelt å endre det andre elementets referanse til det neste elementet og det fjerde elementets referanse til det forrige.

Når et element legges til i listen, skjer den samme prosessen, men omvendt.

Legg merke til hvor mye mindre arbeid vi trenger å gjøre i en LinkedList sammenlignet med en ArrayList . Og det er bare 5 elementer. Hvis listen vår hadde 100 eller flere elementer, ville overlegenheten til LinkedList blitt enda mer merkbar.

Men hvordan endres situasjonen hvis vi får tilgang til et element etter indeks?

Alt er det stikk motsatte her.

Siden ArrayList er strukturert som en vanlig matrise, vil det være veldig enkelt for oss å få ethvert element etter indeksen. Vi flytter ganske enkelt pekeren til et bestemt sted og henter elementet fra den tilsvarende cellen.

Men en LinkedList fungerer rett og slett ikke på den måten. Vi må gå gjennom alle elementene i listen for å finne elementet med en bestemt indeks.

Skal vi prøve å uttrykke alt dette i form av stor O?

La oss starte med å få tilgang til et element etter indeks.

I en ArrayList skjer dette i ett trinn, uavhengig av hvor elementet er plassert i listen. Enten på slutten eller begynnelsen.

I dette tilfellet vil tidskompleksiteten være O(1) .

I en LinkedList må vi iterere over et antall elementer som tilsvarer verdien av indeksen vi trenger.

Tidskompleksiteten for en slik handling er O(n) , der n er indeksen til elementet vi trenger.

Her ser du at tallet vi setter i big-O-parentesen tilsvarer antall utførte handlinger.

Skal vi gå tilbake til å fjerne og legge til?

La oss starte med LinkedList.

Fordi vi ikke trenger å gjøre et stort antall handlinger for å legge til eller fjerne et element, og hastigheten på denne operasjonen ikke på noen måte avhenger av hvor elementet befinner seg, uttrykkes dens kompleksitet som O(1) og sies å være konstant.

Tidskompleksiteten til denne operasjonen for ArrayList er også O(n) , som vi kaller lineær kompleksitet.

I algoritmer med lineær kompleksitet avhenger kjøretiden direkte av antall elementer som skal behandles. Det kan også avhenge av elementets plassering, om det er i begynnelsen av listen eller mot slutten.

Tidskompleksitet kan også være logaritmisk. Dette uttrykkes som O(log n) .

Som et eksempel kan du vurdere et sortert tresett bestående av 10 tall. Vi ønsker å finne tallet 2.

Siden listen er sortert og ikke inneholder noen duplikater, kan vi dele den i to og sjekke hvilken halvdel som vil inneholde ønsket nummer, forkaste den irrelevante delen og deretter gjenta denne prosessen til vi kommer til ønsket element. Til syvende og sist vil vi finne (eller ikke finne) nummeret etter å ha behandlet log(n) antall elementer.

Her er en tabell som oppsummerer tidskompleksiteten for resten av samlingene.

Nå som vi har en tabell som viser tidskompleksiteten til populære samlinger, kan vi svare på spørsmålet hvorfor vi, av så mange samlinger, oftest bruker ArrayList , HashSet og HashMap .

Det er rett og slett det at de er mest effektive til de fleste oppgaver :)