Tips voor het gebruik van verzamelingen

1. Lijst met collecties

Zoals je je misschien herinnert, heeft Java verzamelingen - een handig hulpmiddel om objecten van hetzelfde type op te slaan.

Laten we proberen de belangrijkste collectiegerelateerde interfaces terug te halen:

Lijst , Stel in , Kaart en Wachtrij .

Zoals gewoonlijk zijn tools niet noodzakelijkerwijs goed of slecht - het gaat erom of u ze gebruikt voor het beoogde doel. En om dat te doen, moeten we hun specifieke kenmerken grondig begrijpen om te weten welke collectie we wanneer moeten gebruiken.

1. Lijst

Laten we beginnen met de meest gebruikte verzameling.

Lijst zo dicht mogelijk bij een gewone oude array.

Met deze verzameling kunnen we gemakkelijk een lijst met objecten van hetzelfde type opslaan zonder ons zorgen te hoeven maken over de grootte van de verzameling zelf, zoals we zouden moeten doen als we een array zouden gebruiken. Elementen van de collectie zijn toegankelijk via index. Als we precies weten waar een object zich bevindt en er regelmatig toegang toe moeten hebben zonder vaak elementen toe te voegen of te verwijderen, is een lijst ideaal.

2. Instellen

Set heeft een heel andere structuur.

Set is het meest geschikt wanneer we unieke objecten moeten opslaan. Bijvoorbeeld een set auteurs in een bibliotheek waar elke auteur uniek is. Maar we kunnen er niet zomaar een specifieke auteur uit halen. Met Set kunnen we snel controleren of een bepaalde auteur aanwezig is in onze bibliotheek, dwz we kunnen controleren of een uniek object aanwezig is in een Set . We kunnen ook de hele collectie herhalen, waarbij we toegang hebben tot elk element, maar dat is niet optimaal.

Met andere woorden, voor onze bibliotheek kan een set de verzameling van alle unieke auteurs vertegenwoordigen om snel te controleren of een bepaalde auteur aanwezig is.

3. Kaart

Kaart is meer een archiefkast, waar elk bestand is ondertekend en individuele objecten of hele structuren kan opslaan. Kaart moet worden gebruikt in gevallen waarin we een afbeelding van de ene waarde naar de andere moeten onderhouden.

Voor Map worden deze relaties sleutel-waardeparen genoemd.

We zouden deze structuur in onze bibliotheek kunnen gebruiken door auteursobjecten als sleutels en lijsten ( Lijstobjecten ) van boeken als waarden te gebruiken. Dus na het controleren van een set om te zien of er een auteurobject in de bibliotheek bestaat, kunnen we hetzelfde auteurobject gebruiken om een ​​lijst van zijn of haar boeken uit een kaart te halen .

4. Wachtrij

Queue is een verzameling die - verrassing! — implementeert het gedrag van een wachtrij. En de wachtrij kan LIFO (Last In, First Out) of FIFO (First In, First Out)zijnBovendien kan de wachtrij bidirectioneel zijn, of "double-ended".

Deze structuur is handig wanneer de objecten die aan de klasse zijn toegevoegd, moeten worden gebruikt in de volgorde waarin ze zijn ontvangen. Neem bijvoorbeeld onze bibliotheek.

We kunnen nieuw aangekomen bezoekers aan een wachtrij toevoegen en hen op hun beurt bedienen door de boeken uit te geven waarvoor ze komen.

Zoals we kunnen zien, is elk van deze structuren goed als ze worden gebruikt voor het beoogde doel. En we vonden goede toepassingen voor alle vier soorten collecties in één bibliotheekvoorbeeld.

2. Complexiteit

Zoals reeds opgemerkt, zijn de collecties die we hierboven hebben overwogen interfaces, wat betekent dat ze implementaties moeten hebben voordat we ze kunnen gebruiken.

Net zoals spijkers slaan met een microscoop niet het beste idee is, is niet elke uitvoering van een collectie geschikt voor elke situatie.

Bij het kiezen van het juiste gereedschap voor een klus kijken we doorgaans naar 2 kenmerken:

• Hoe goed past het gereedschap bij de klus?
• Hoe snel zal het de klus klaren?

We hebben enige tijd besteed aan het uitzoeken hoe we een geschikt gereedschap voor een klus kunnen kiezen, maar de snelheid ervan is iets nieuws.

Bij computers wordt de snelheid van een tool vaak uitgedrukt in termen van tijdcomplexiteit en aangeduid met een hoofdletter O.

Wat is in hemelsnaam tijdscomplexiteit?

Eenvoudig gezegd geeft tijdcomplexiteit de tijd aan die een algoritme in de verzameling nodig heeft om een ​​bepaalde actie uit te voeren (een element toevoegen/verwijderen, zoeken naar een element).

ArrayList versus LinkedList

Laten we dit eens bekijken aan de hand van twee implementaties van de List- interface: ArrayList en LinkedList .

Voor uiterlijke schijn is het werken met deze collecties vergelijkbaar:

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);
    

Zoals u kunt zien, ziet het toevoegen, ophalen en verwijderen van elementen er voor beide soorten verzamelingen hetzelfde uit. Dit komt omdat dit implementaties zijn op dezelfde interface. Maar daar eindigen de overeenkomsten.

Vanwege hun verschillende implementaties van de lijstinterface , voeren deze twee structuren verschillende acties efficiënter uit dan andere.

Overweeg een element te verwijderen en toe te voegen.

Als we een element uit het midden van een ArrayList moeten verwijderen , moeten we het deel van de lijst overschrijven dat volgt op het element dat we verwijderen.

Stel dat we een lijst van 5 elementen hebben en we willen de 3e verwijderen.

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

In dit geval maakt het verwijderen één cel vrij, dus we moeten het 4e element schrijven waar het 3e was, en het 5e waar het 4e was.

Dit is zeer inefficiënt.

Hetzelfde gebeurt bij het toevoegen van een element aan het midden van de lijst.

LinkedList is anders gestructureerd. Het toevoegen of verwijderen van elementen gaat snel, omdat we alleen de verwijzingen in de vorige en volgende elementen hoeven te wijzigen, waardoor het object dat we verwijderen uit de keten van elementen wordt uitgesloten.

Terugkerend naar het voorbeeld van dezelfde lijst van 5 elementen, na het verwijderen van het 3e element, hoeven we alleen maar de verwijzing van het 2e element naar het volgende element en de verwijzing van het 4e element naar het vorige te wijzigen.

Wanneer een element aan de lijst wordt toegevoegd, gebeurt hetzelfde proces, maar dan omgekeerd.

Merk op hoeveel minder werk we moeten doen in een LinkedList in vergelijking met een ArrayList . En dat zijn nog maar 5 elementen. Als onze lijst 100 of meer elementen had, zou de superioriteit van LinkedList nog meer opvallen.

Maar hoe verandert de situatie als we een element per index benaderen?

Alles is hier precies het tegenovergestelde.

Aangezien ArrayList is gestructureerd als een gewone array, zal het heel gemakkelijk voor ons zijn om elk element via de index te krijgen. We verplaatsen de aanwijzer eenvoudig naar een bepaalde plaats en halen het element uit de overeenkomstige cel.

Maar zo werkt een LinkedList nu eenmaal niet. We moeten alle elementen van de lijst doorlopen om het element met een bepaalde index te vinden.

Zullen we proberen dit allemaal uit te drukken in termen van grote O?

Laten we beginnen met toegang tot een element per index.

In een ArrayList gebeurt dit in één stap, ongeacht waar het element zich in de lijst bevindt. Of het nu aan het einde of aan het begin is.

In dit geval is de tijdscomplexiteit O(1) .

In een LinkedList moeten we een aantal elementen herhalen dat gelijk is aan de waarde van de index die we nodig hebben.

De tijdscomplexiteit voor zo'n actie is O(n) , waarbij n de index is van het element dat we nodig hebben.

Hier zie je dat het getal dat we tussen de grote O-haakjes plaatsen, overeenkomt met het aantal uitgevoerde acties.

Shell we keren terug naar verwijderen en toevoegen?

Laten we beginnen met LinkedList.

Omdat we niet een groot aantal acties hoeven uit te voeren om een ​​element toe te voegen of te verwijderen, en de snelheid van deze bewerking op geen enkele manier afhangt van waar het element zich bevindt, wordt de complexiteit uitgedrukt als O(1) en wordt gezegd constant zijn.

De tijdscomplexiteit van deze bewerking voor ArrayList is ook O(n) , wat we lineaire complexiteit noemen.

Bij algoritmen met lineaire complexiteit is de looptijd direct afhankelijk van het aantal te verwerken elementen. Het kan ook afhangen van de positie van het element, of het nu aan het begin van de lijst staat of aan het einde.

Tijdcomplexiteit kan ook logaritmisch zijn. Dit wordt uitgedrukt als O(log n) .

Beschouw als voorbeeld een gesorteerde TreeSet bestaande uit 10 getallen. We willen het getal 2 vinden.

Aangezien de lijst gesorteerd is en geen duplicaten bevat, kunnen we deze in tweeën splitsen en controleren welke helft het gewenste nummer zou bevatten, het irrelevante deel weggooien en dit proces herhalen totdat we het gewenste element bereiken. Uiteindelijk zullen we het aantal vinden (of niet vinden) na het verwerken van log(n) aantal elementen.

Hier is een tabel die de tijdscomplexiteit van de rest van de collecties samenvat.

Nu we een tabel hebben die de tijdcomplexiteit van populaire collecties laat zien, kunnen we de vraag beantwoorden waarom we van zoveel collecties het vaakst ArrayList , HashSet en HashMap gebruiken .

Het is gewoon dat ze het meest efficiënt zijn voor de meeste taken :)