streamalism.org

1. Inleiding

In Java is het eenvoudig om een ​​specifieke waarde te verwijderen uit een Lijst gebruik makend van List.remove (). Echter, het efficiënt verwijderen van alle exemplaren van een waarde is veel moeilijker.

In deze zelfstudie zien we meerdere oplossingen voor dit probleem, waarin de voor- en nadelen worden beschreven.

Omwille van de leesbaarheid gebruiken we een aangepaste lijst (int ...) methode in de tests, die een ArrayList met de elementen die we passeerden.

2. Met behulp van een terwijl Lus

Omdat we weten hoe verwijder een enkel element en doe het herhaaldelijk in een lus ziet er eenvoudig genoeg uit:

void removeAll (List list, int element) {while (list.contains (element)) {list.remove (element); }}

Het werkt echter niet zoals verwacht:

// gegeven lijst lijst = lijst (1, 2, 3); int valueToRemove = 1; // when assertThatThrownBy (() -> removeAll (lijst, waardeToRemove)) .isInstanceOf (IndexOutOfBoundsException.class);

Het probleem zit in de derde regel: we bellen List.remove (int), die zijn argument behandelt als de index, niet als de waarde die we willen verwijderen.

In bovenstaande test bellen we altijd lijst.remove (1), maar de index van het element dat we willen verwijderen is 0. Roeping List.remove () verschuift alle elementen na de verwijderde naar kleinere indices.

In dit scenario betekent dit dat we alle elementen verwijderen, behalve de eerste.

Als alleen de eerste overblijft, is de index 1 zal illegaal zijn. Daarom krijgen we een Uitzondering.

Merk op dat we dit probleem alleen onder ogen zien als we bellen List.remove () met een primitief byte, kort, char of int argument, aangezien het eerste dat de compiler doet wanneer hij de overeenkomende overbelaste methode probeert te vinden, verbreedt.

We kunnen het corrigeren door de waarde door te geven als Geheel getal:

void removeAll (lijst lijst, geheel getal element) {while (list.contains (element)) {list.remove (element); }}

Nu werkt de code zoals verwacht:

// gegeven lijst lijst = lijst (1, 2, 3); int valueToRemove = 1; // when removeAll (list, valueToRemove); // dan assertThat (lijst) .isEqualTo (lijst (2, 3));

Sinds Lijst. Bevat () en List.remove () beide moeten het eerste voorkomen van het element vinden, deze code veroorzaakt onnodige elementdoorgang.

We kunnen het beter doen als we de index van het eerste voorval opslaan:

void removeAll (lijstlijst, integer-element) {int index; while ((index = list.indexOf (element))> = 0) {list.remove (index); }}

We kunnen verifiëren dat het werkt:

// gegeven lijst lijst = lijst (1, 2, 3); int valueToRemove = 1; // when removeAll (list, valueToRemove); // dan assertThat (lijst) .isEqualTo (lijst (2, 3));

Hoewel deze oplossingen korte en duidelijke code produceren, ze presteren nog steeds slecht: omdat we de voortgang niet bijhouden, List.remove () moet de eerste instantie van de opgegeven waarde vinden om deze te verwijderen.

Ook als we een ArrayList, kan het verschuiven van elementen veel referentiekopieën veroorzaken, zelfs als de backing-array meerdere keren opnieuw wordt toegewezen.

3. Verwijderen tot het Lijst Veranderingen

List.remove (E-element) heeft een functie die we nog niet hebben genoemd: it geeft een terug boolean waarde, dat is waar als het Lijst gewijzigd vanwege de operatie, daarom bevatte het het element.

Let daar op List.remove (int index) geeft ongeldig terug, want als de opgegeven index geldig is, de Lijst verwijdert het altijd. Anders gooit het IndexOutOfBoundsException.

Hiermee kunnen we verhuizingen uitvoeren tot de Lijst veranderingen:

void removeAll (List list, int element) {while (list.remove (element)); }

Het werkt zoals verwacht:

// gegeven lijst lijst = lijst (1, 1, 2, 3); int valueToRemove = 1; // when removeAll (list, valueToRemove); // dan assertThat (lijst) .isEqualTo (lijst (2, 3));

Ondanks dat het kort is, lijdt deze implementatie aan dezelfde problemen die we in de vorige sectie hebben beschreven.

3. Met behulp van een voor Lus

We kunnen onze voortgang bijhouden door door de elementen te gaan met een voor loop en verwijder de huidige als deze overeenkomt met:

void removeAll (List list, int element) {for (int i = 0; i <list.size (); i ++) {if (Objects.equals (element, list.get (i))) {list.remove (i ); }}}

Het werkt zoals verwacht:

// gegeven lijst lijst = lijst (1, 2, 3); int valueToRemove = 1; // when removeAll (list, valueToRemove); // dan assertThat (lijst) .isEqualTo (lijst (2, 3));

Als we het echter proberen met een andere invoer, levert het een onjuiste uitvoer op:

// gegeven lijst lijst = lijst (1, 1, 2, 3); int valueToRemove = 1; // when removeAll (list, valueToRemove); // dan assertThat (lijst) .isEqualTo (lijst (1, 2, 3));

Laten we stap voor stap analyseren hoe de code werkt:

• ik = 0
  • element en list.get (i) zijn beide gelijk aan 1 op regel 3, dus Java komt in de body van het als uitspraak,
  • we verwijderen het element bij index 0,
  • zo lijst bevat nu 1, 2 en 3
• ik = 1
  • list.get (i) geeft terug 2 omdat wanneer we een element verwijderen uit een Lijstverschuift het alle voortgaande elementen naar kleinere indices

Dus we worden geconfronteerd met dit probleem wanneer we hebben twee aangrenzende waarden, die we willen verwijderen. Om dit op te lossen, moeten we de lusvariabele behouden.

Verlagen wanneer we het element verwijderen:

void removeAll (List list, int element) {for (int i = 0; i <list.size (); i ++) {if (Objects.equals (element, list.get (i))) {list.remove (i ); ik--; }}}

Alleen verhogen als we het element niet verwijderen:

void removeAll (Lijstlijst, int element) {for (int i = 0; i <list.size ();) {if (Objects.equals (element, list.get (i))) {list.remove (i) ; } anders {i ++; }}}

Merk op dat we in het laatste de verklaring hebben verwijderd i ++ op regel 2.

Beide oplossingen werken zoals verwacht:

// gegeven lijst lijst = lijst (1, 1, 2, 3); int valueToRemove = 1; // when removeAll (list, valueToRemove); // dan assertThat (lijst) .isEqualTo (lijst (2, 3));

Deze implementatie lijkt op het eerste gezicht goed. Het heeft echter nog steeds ernstige prestatieproblemen:

• een element verwijderen uit een ArrayList, verschuift alle items erna
• toegang tot elementen via index in een LinkedList betekent dat we de elementen één voor één doorlopen totdat we de index vinden

4. Met behulp van een voor elk Lus

Sinds Java 5 kunnen we de voor elk lus om door een Lijst. Laten we het gebruiken om elementen te verwijderen:

void removeAll (Lijst lijst, int element) {for (Integer nummer: lijst) {if (Objects.equals (nummer, element)) {list.remove (nummer); }}}

Merk op dat we Geheel getal als het type van de lusvariabele. Daarom krijgen we geen NullPointerException.

Ook op deze manier doen we een beroep op List.remove (E-element), die de waarde verwacht die we willen verwijderen, niet de index.

Hoe schoon het er ook uitziet, het werkt helaas niet:

// gegeven lijst lijst = lijst (1, 1, 2, 3); int valueToRemove = 1; // when assertThatThrownBy (() -> removeWithForEachLoop (lijst, valueToRemove)) .isInstanceOf (ConcurrentModificationException.class);

De voor elk loop gebruikt Iterator om door de elementen te reizen. Echter, wanneer we de Lijst, de Iterator komt in een inconsistente staat. Daarom gooit het ConcurrentModificationException.

De les is: we moeten een Lijst, terwijl we toegang hebben tot de elementen ervan in een voor elk lus.

5. Met behulp van een Iterator

We kunnen de Iterator rechtstreeks om door het Lijst ermee:

void removeAll (Lijstlijst, int element) {for (Iterator i = list.iterator (); i.hasNext ();) {Geheel getal = i.next (); if (Objects.equals (nummer, element)) {i.remove (); }}}

Op deze manier de Iterator kan de staat van de Lijst (omdat het de wijziging aanbrengt). Als gevolg hiervan werkt de bovenstaande code zoals verwacht:

// gegeven lijst lijst = lijst (1, 1, 2, 3); int valueToRemove = 1; // when removeAll (list, valueToRemove); // dan assertThat (lijst) .isEqualTo (lijst (2, 3));

Sinds elke Lijst klasse kan hun eigen geven Iterator implementatie, kunnen we gerust aannemen, dat het implementeert het verplaatsen en verwijderen van elementen op de meest efficiënte manier.

Gebruik echter ArrayList betekent nog steeds veel verschuiven van elementen (en misschien opnieuw toewijzen van array). Bovendien is de bovenstaande code iets moeilijker te lezen, omdat deze afwijkt van de standaard voor loop, die de meeste ontwikkelaars kennen.

6. Verzamelen

Tot dit moment hebben we het origineel aangepast Lijst bezwaar maken door de items te verwijderen die we niet nodig hadden. We kunnen het eerder maak een nieuw Lijst en verzamel de items die we willen behouden:

Lijst removeAll (Lijst lijst, int element) {Lijst resterendeElements = nieuwe ArrayList (); for (Geheel getal: lijst) {if (! Objects.equals (getal, element)) {resterendeElements.add (getal); }} retourneer resterendeElements; }

Omdat we het resultaat in een nieuw Lijst object, we moeten het teruggeven vanuit de methode. Daarom moeten we de methode op een andere manier gebruiken:

// gegeven lijst lijst = lijst (1, 1, 2, 3); int valueToRemove = 1; // when List result = removeAll (list, valueToRemove); // dan assertThat (resultaat) .isEqualTo (lijst (2, 3));

Merk op dat we nu de voor elk lus omdat we de Lijst we zijn momenteel aan het doorlopen.

Omdat er geen verwijderingen zijn, is het niet nodig om de elementen te verplaatsen. Daarom presteert deze implementatie goed wanneer we een ArrayList.

Deze implementatie gedraagt ​​zich in sommige opzichten anders dan de eerdere:

• het wijzigt het origineel niet Lijst maar geeft een nieuw een
• de methode bepaalt wat er wordt geretourneerd LijstDe implementatie is, het kan afwijken van het origineel

Ook kunnen we onze implementatie aanpassen aan krijg het oude gedrag; we wissen het origineel Lijst en voeg de verzamelde elementen eraan toe:

void removeAll (Lijstlijst, int element) {Lijst resterendeElements = nieuwe ArrayList (); for (Geheel getal: lijst) {if (! Objects.equals (getal, element)) {resterendeElements.add (getal); }} list.clear (); list.addAll (resterende elementen); }

Het werkt op dezelfde manier als de vorige:

// gegeven lijst lijst = lijst (1, 1, 2, 3); int valueToRemove = 1; // when removeAll (list, valueToRemove); // dan assertThat (lijst) .isEqualTo (lijst (2, 3));

Omdat we het Lijst continu hoeven we elementen niet per positie te benaderen of ze te verschuiven. Er zijn ook slechts twee mogelijke hertoewijzingen van array: wanneer we aanroepen List.clear () en Lijst.addAll ().

7. Met behulp van de Stream API

Java 8 introduceerde lambda-expressies en stream-API. Met deze krachtige functies kunnen we ons probleem oplossen met een zeer schone code:

List removeAll (List list, int element) {return list.stream () .filter (e ->! Objects.equals (e, element)) .collect (Collectors.toList ()); }

Deze oplossing werkt op dezelfde manier, zoals toen we de resterende elementen verzamelden.

Daardoor heeft het dezelfde kenmerken, en we zouden het moeten gebruiken om het resultaat te retourneren:

// gegeven lijst lijst = lijst (1, 1, 2, 3); int valueToRemove = 1; // when List result = removeAll (list, valueToRemove); // dan assertThat (resultaat) .isEqualTo (lijst (2, 3));

Merk op dat we het kunnen converteren om te werken zoals de andere oplossingen met dezelfde aanpak die we deden met de oorspronkelijke ‘verzamelen’ -implementatie.

8. Met behulp van removeIf

Met lambda's en functionele interfaces introduceerde Java 8 ook enkele API-extensies. Bijvoorbeeld de Lijst.removeIf () methode, die implementeert wat we in de laatste sectie hebben gezien.

Het verwacht een Predikaat, die zou moeten terugkeren waar wanneer we willen verwijderen het element, in tegenstelling tot het vorige voorbeeld, waar we naar terug moesten waar toen we het element wilden behouden:

void removeAll (Lijstlijst, int element) {list.removeIf (n -> Objects.equals (n, element)); }

Het werkt net als de andere bovenstaande oplossingen:

// gegeven lijst lijst = lijst (1, 1, 2, 3); int valueToRemove = 1; // when removeAll (list, valueToRemove); // dan assertThat (lijst) .isEqualTo (lijst (2, 3));

Vanwege het feit dat de Lijst zelf implementeert deze methode, we kunnen er gerust van uitgaan, dat deze de beste beschikbare prestaties heeft. Bovendien biedt deze oplossing de schoonste code van allemaal.

9. Conclusie

In dit artikel hebben we veel manieren gezien om een ​​eenvoudig probleem op te lossen, inclusief onjuiste. We hebben ze geanalyseerd om voor elk scenario de beste oplossing te vinden.

Zoals gewoonlijk zijn de voorbeelden beschikbaar op GitHub.