Tips om hur du använder samlingar

1. Förteckning över samlingar

Som du kanske minns har Java samlingar - ett praktiskt verktyg för att lagra objekt av samma typ.

Låt oss försöka komma ihåg de viktigaste samlingsrelaterade gränssnitten:

Lista , Ställ in , Karta och Kö .

Som vanligt är verktyg inte nödvändigtvis bra eller dåliga - det som spelar roll är om du använder dem för det avsedda syftet. Och för att göra det måste vi noggrant förstå deras specifika egenskaper för att veta vilken samling vi ska använda och när.

1. Lista

Låt oss börja med den mest använda samlingen.

Lista så nära som möjligt en vanlig gammal array.

Den här samlingen låter oss enkelt lagra en lista med objekt av samma typ utan att behöva oroa oss för storleken på själva samlingen, vilket vi skulle behöva om vi använde en array. Delar av samlingen nås via index. Om vi ​​vet exakt var ett objekt är och behöver komma åt det ofta utan att ofta behöva lägga till eller ta bort element, är en List idealisk.

2. Ställ in

Setet har en helt annan struktur.

Set passar bäst när vi behöver förvara unika föremål. Till exempel en uppsättning författare i ett bibliotek där varje författare är unik. Men vi kan inte bara gå och ta någon specifik författare från den. Set låter oss snabbt kontrollera om en viss författare finns i vårt bibliotek, dvs vi kan kontrollera om ett unikt objekt finns i en Set . Vi kan också iterera över hela samlingen, komma åt varje element, men att göra det är inte optimalt.

Med andra ord, för vårt bibliotek kan en uppsättning representera samlingen av alla unika författare för att snabbt kontrollera om någon speciell författare är närvarande.

3. Karta

Karta är mer som ett arkivskåp, där varje fil är signerad och kan lagra enskilda objekt eller hela strukturer. Karta bör användas i de fall vi behöver underhålla en mappning från ett värde till ett annat.

För Map kallas dessa relationer nyckel-värdepar.

Vi skulle kunna använda den här strukturen i vårt bibliotek genom att använda författarobjekt som nycklar och listor ( Listobjekt ) över böcker som värden. Efter att ha kontrollerat en uppsättning för att se om ett författarobjekt finns i biblioteket, kan vi alltså använda samma författarobjekt för att hämta en lista över hans eller hennes böcker från en karta .

4. Kö

Queue är en samling som — överraskning! — implementerar beteendet hos en kö. Och kön kan vara antingen LIFO (Last In, First Out) eller FIFO (First In, First Out). Dessutom kan kön vara dubbelriktad eller "dubbeländad".

Denna struktur är användbar när objekten som läggs till i klassen måste användas i den ordning de tas emot. Ta till exempel vårt bibliotek.

Vi kan lägga till nyanlända besökare till en kö och betjäna dem i tur och ordning, utfärda böckerna de kommer för.

Som vi kan se är var och en av dessa strukturer bra om de används för sitt avsedda syfte. Och vi hittade bra användningsområden för alla fyra typer av samlingar i ett enda biblioteksexempel.

2. Komplexitet

Som redan nämnts är samlingarna som vi betraktade ovan gränssnitt, vilket innebär att de måste ha implementeringar för att vi ska kunna använda dem.

Precis som att slå spikar med ett mikroskop inte är den bästa idén, är inte varje implementering av en kollektion anpassad för varje situation.

När vi väljer rätt verktyg för ett jobb tittar vi vanligtvis på två egenskaper:

• Hur väl passar verktyget jobbet?
• Hur snabbt kommer det att få jobbet gjort?

Vi har ägnat lite tid åt att ta reda på hur man väljer ett lämpligt verktyg för ett jobb, men dess hastighet är något nytt.

Vid beräkning uttrycks ett verktygs hastighet ofta i termer av tidskomplexitet och betecknas med en stor bokstav O.

Vad i hela friden är tidskomplexitet?

Enkelt uttryckt indikerar tidskomplexitet den tid som krävs för en algoritm i samlingen att utföra en viss åtgärd (lägga till/ta bort ett element, söka efter ett element).

ArrayList vs LinkedList

Låt oss titta på detta med två implementeringar av List- gränssnittet - ArrayList och LinkedList .

När det gäller utseendet är det liknande att arbeta med dessa samlingar:

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 likadant ut för båda samlingstyperna att lägga till, hämta och ta bort element. Detta beror på att dessa är implementeringar på samma gränssnitt. Men det är där likheterna slutar.

På grund av deras olika implementeringar av List- gränssnittet, utför dessa två strukturer olika åtgärder mer effektivt än andra.

Överväg att ta bort och lägga till ett element.

Om vi ​​behöver ta bort ett element från mitten av en ArrayList måste vi skriva över den del av listan som följer efter elementet vi tar bort.

Anta att vi har en lista med 5 element och vi vill ta bort det tredje.

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

I det här fallet frigör borttagningen en cell, så vi måste skriva det 4:e elementet där det 3:e var och det 5:e där det 4:e var.

Detta är mycket ineffektivt.

Detsamma händer när man lägger till ett element i mitten av listan.

LinkedList är strukturerad annorlunda. Att lägga till eller ta bort element går snabbt, eftersom vi bara behöver ändra referenserna i föregående och nästa element, och därigenom utesluta objektet vi tar bort från elementkedjan.

För att återgå till exemplet med samma lista med 5 element, efter att ha tagit bort det 3:e elementet, behöver vi bara ändra det 2:a elementets referens till nästa element och det 4:e elementets referens till det föregående.

När ett element läggs till i listan sker samma process, men omvänt.

Lägg märke till hur mycket mindre arbete vi behöver göra i en LinkedList jämfört med en ArrayList . Och det är bara 5 element. Om vår lista hade 100 eller fler element skulle överlägsenheten hos LinkedList bli ännu mer märkbar.

Men hur förändras situationen om vi kommer åt ett element per index?

Allt är raka motsatsen här.

Eftersom ArrayList är strukturerad som en vanlig array, kommer det att vara väldigt enkelt för oss att hämta vilket element som helst efter dess index. Vi flyttar helt enkelt pekaren till en viss plats och hämtar elementet från motsvarande cell.

Men en LinkedList fungerar helt enkelt inte så. Vi måste gå igenom alla element i listan för att hitta elementet med ett visst index.

Ska vi försöka uttrycka allt detta i termer av stort O?

Låt oss börja med att komma åt ett element efter index.

I en ArrayList sker detta i ett steg, oavsett var elementet finns i listan. Oavsett om det är i slutet eller början.

I detta fall kommer tidskomplexiteten att vara O(1) .

I en LinkedList måste vi iterera över ett antal element lika med värdet på indexet vi behöver.

Tidskomplexiteten för en sådan åtgärd är O(n) , där n är indexet för det element vi behöver.

Här ser du att siffran vi sätter inom big-O parentesen motsvarar antalet utförda åtgärder.

Skal vi återgå till att ta bort och lägga till?

Låt oss börja med LinkedList.

Eftersom vi inte behöver göra ett stort antal åtgärder för att lägga till eller ta bort ett element, och hastigheten på denna operation inte på något sätt beror på var elementet är beläget, uttrycks dess komplexitet som O(1) och sägs att vara konstant.

Tidskomplexiteten för denna operation för ArrayList är också O(n) , som vi kallar linjär komplexitet.

I algoritmer med linjär komplexitet beror körtiden direkt på antalet element som ska bearbetas. Det kan också bero på elementets position, om det är i början av listan eller mot slutet.

Tidskomplexitet kan också vara logaritmisk. Detta uttrycks som O(log n) .

Som ett exempel, betrakta en sorterad TreeSet som består av 10 nummer. Vi vill hitta siffran 2.

Eftersom listan är sorterad och inte innehåller några dubbletter kan vi dela den på mitten och kontrollera vilken halva som skulle innehålla det önskade numret, kassera den irrelevanta delen och sedan upprepa denna process tills vi når önskat element. I slutändan kommer vi att hitta (eller inte hitta) numret efter bearbetning av log(n) antal element.

Här är en tabell som sammanfattar tidskomplexiteten för resten av samlingarna.

Nu när vi har en tabell som visar tidskomplexiteten för populära samlingar kan vi svara på frågan varför vi, av så många samlingar, oftast använder ArrayList , HashSet och HashMap .

Det är helt enkelt så att de är mest effektiva för de flesta uppgifter :)