Tips om brug af samlinger

1. Liste over samlinger

Som du måske husker, har Java samlinger - et praktisk værktøj til lagring af objekter af samme type.

Lad os prøve at huske de vigtigste samlingsrelaterede grænseflader:

Liste , sæt , kort og kø .

Som sædvanligt er værktøjer ikke nødvendigvis gode eller dårlige - det afgørende er, om du bruger dem til deres tilsigtede formål. Og for at gøre det skal vi grundigt forstå deres specifikke funktioner for at vide, hvilken samling vi skal bruge og hvornår.

1. Liste

Lad os starte med den mest brugte samling.

Liste så tæt som muligt på et almindeligt gammelt array.

Denne samling lader os bekvemt gemme en liste over objekter af samme type uden at bekymre os om størrelsen af ​​selve samlingen, som vi ville være nødt til, hvis vi brugte et array. Elementer i samlingen tilgås via indeks. Hvis vi ved præcis, hvor et objekt er og har brug for at få adgang til det ofte uden ofte at skulle tilføje eller fjerne elementer, er en liste ideel.

2. Indstil

Sættet har en helt anden struktur.

Sættet er bedst egnet, når vi skal opbevare unikke genstande. For eksempel et sæt forfattere i et bibliotek, hvor hver forfatter er unik. Men vi kan ikke bare gå hen og få fat i en bestemt forfatter fra den. Set lader os hurtigt tjekke, om en bestemt forfatter er til stede i vores bibliotek, dvs. vi kan kontrollere, om et unikt objekt er til stede i et sæt . Vi kan også iterere over hele samlingen og få adgang til hvert element, men at gøre det er ikke optimalt.

Med andre ord, for vores bibliotek kan et sæt repræsentere samlingen af ​​alle unikke forfattere for hurtigt at kontrollere, om en bestemt forfatter er til stede.

3. Kort

Kort er mere som et arkivskab, hvor hver fil er signeret og kan opbevare individuelle objekter eller hele strukturer. Kort bør bruges i tilfælde, hvor vi har brug for at vedligeholde en kortlægning fra en værdi til en anden.

For Map kaldes disse relationer nøgleværdi-par.

Vi kunne bruge denne struktur i vores bibliotek ved at bruge forfatterobjekter som nøgler og lister ( listeobjekter ) af bøger som værdier. Efter at have kontrolleret et sæt for at se, om der findes et forfatterobjekt i biblioteket, kan vi bruge det samme forfatterobjekt til at få en liste over hans eller hendes bøger fra et kort .

4. Kø

Kø er en samling, der - overrasker! — implementerer en køs adfærd. Og køen kan enten være LIFO (Last In, First Out) eller FIFO (First In, First Out). Hvad mere er, kan køen være tovejs eller "dobbeltende".

Denne struktur er nyttig, når de objekter, der tilføjes til klassen, skal bruges i den rækkefølge, de modtages. Tag for eksempel vores bibliotek.

Vi kan tilføje nyankomne besøgende til en kø og betjene dem på skift og udstede de bøger, de kommer efter.

Som vi kan se, er hver af disse strukturer god, hvis den bruges til det tilsigtede formål. Og vi fandt gode anvendelsesmuligheder for alle fire typer samlinger i et enkelt bibliotekseksempel.

2. Kompleksitet

Som allerede nævnt er de samlinger, vi overvejede ovenfor, grænseflader, hvilket betyder, at de skal have implementeringer for at vi kan bruge dem.

Ligesom at hamre søm med et mikroskop ikke er den bedste idé, er ikke enhver implementering af en kollektion egnet til enhver situation.

Når vi skal vælge det rigtige værktøj til et job, ser vi typisk på 2 egenskaber:

• Hvor godt passer værktøjet til jobbet?
• Hvor hurtigt vil det få arbejdet gjort?

Vi har brugt noget tid på at finde ud af, hvordan man vælger et passende værktøj til et job, men dets hastighed er noget nyt.

I databehandling udtrykkes et værktøjs hastighed ofte i form af tidskompleksitet og betegnes med et stort O.

Hvad i alverden er tidskompleksitet?

Enkelt sagt angiver tidskompleksitet den tid, det tager for en algoritme i samlingen at udføre en bestemt handling (tilføje/fjerne et element, søgning efter et element).

ArrayList vs LinkedList

Lad os se på dette ved hjælp af to implementeringer af List -grænsefladen - ArrayList og LinkedList .

For ydre udseende er arbejdet med disse kollektioner ens:

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 tilføjelse, hentning og fjernelse af elementer ens ud for begge samlingstyper. Dette skyldes, at der er tale om implementeringer på den samme grænseflade. Men det er her lighederne slutter.

På grund af deres forskellige implementeringer af List- grænsefladen udfører disse to strukturer forskellige handlinger mere effektivt end andre.

Overvej at fjerne og tilføje et element.

Hvis vi skal fjerne et element fra midten af ​​en ArrayList , skal vi overskrive den del af listen, der følger efter det element, vi fjerner.

Antag, at vi har en liste med 5 elementer, og vi vil fjerne det tredje.

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

I dette tilfælde frigiver fjernelsen en celle, så vi skal skrive det 4. element, hvor det 3. var, og det 5., hvor det 4. var.

Dette er meget ineffektivt.

Det samme sker, når du tilføjer et element til midten af ​​listen.

LinkedList er struktureret anderledes. Tilføjelse eller fjernelse af elementer er hurtig, da vi kun behøver at ændre referencerne i de foregående og næste elementer, og derved udelukke det objekt, vi fjerner fra kæden af ​​elementer.

For at vende tilbage til eksemplet med den samme liste med 5 elementer, efter at have fjernet det 3. element, skal vi blot ændre 2. elements reference til det næste element og 4. elements reference til det forrige.

Når et element tilføjes til listen, sker den samme proces, men omvendt.

Læg mærke til, hvor meget mindre arbejde vi skal udføre i en LinkedList sammenlignet med en ArrayList . Og det er kun 5 elementer. Hvis vores liste havde 100 eller flere elementer, ville LinkedLists overlegenhed blive endnu mere mærkbar.

Men hvordan ændrer situationen sig, hvis vi får adgang til et element efter indeks?

Alt er det stik modsatte her.

Da ArrayList er struktureret som et almindeligt array, vil det være meget nemt for os at få ethvert element efter dets indeks. Vi flytter blot markøren til et bestemt sted og henter elementet fra den tilsvarende celle.

Men en LinkedList fungerer simpelthen ikke sådan. Vi skal gennemgå alle elementerne på listen for at finde elementet med et bestemt indeks.

Skal vi prøve at udtrykke alt dette i form af stort O?

Lad os starte med at få adgang til et element efter indeks.

I en ArrayList sker dette i ét trin, uanset hvor elementet er placeret på listen. Om det er i slutningen eller begyndelsen.

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

I en LinkedList skal vi iterere over et antal elementer svarende til værdien af ​​det indeks, vi har brug for.

Tidskompleksiteten for en sådan handling er O(n) , hvor n er indekset for det element, vi har brug for.

Her ser du, at det tal vi sætter i big-O parentesen svarer til antallet af udførte handlinger.

Skal vi vender tilbage til at fjerne og tilføje?

Lad os starte med LinkedList.

Fordi vi ikke behøver at udføre et stort antal handlinger for at tilføje eller fjerne et element, og hastigheden af ​​denne operation ikke på nogen måde afhænger af, hvor elementet er placeret, udtrykkes dets kompleksitet som O(1) og siges . at være konstant.

Tidskompleksiteten af ​​denne operation for ArrayList er også O(n) , som vi kalder lineær kompleksitet.

I algoritmer med lineær kompleksitet afhænger køretiden direkte af antallet af elementer, der skal behandles. Det kan også afhænge af elementets placering, om det er i begyndelsen af ​​listen eller mod slutningen.

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

Som et eksempel kan du overveje et sorteret træsæt bestående af 10 numre. Vi ønsker at finde tallet 2.

Da listen er sorteret og ikke indeholder dubletter, kan vi dele den i to og kontrollere, hvilken halvdel der ville indeholde det ønskede nummer, kassere den irrelevante del og derefter gentage denne proces, indtil vi når det ønskede element. I sidste ende vil vi finde (eller ikke finde) antallet efter behandling af log(n) antal elementer.

Her er en tabel, der opsummerer tidskompleksiteten i resten af ​​samlingerne.

Nu hvor vi har en tabel, der viser tidskompleksiteten af ​​populære samlinger, kan vi besvare spørgsmålet, hvorfor vi ud af så mange samlinger oftest bruger ArrayList , HashSet og HashMap .

Det er simpelthen, at de er de mest effektive til de fleste opgaver :)