streamalism.org

1. Úvod

V Jave je jednoduché odstrániť konkrétnu hodnotu z a Zoznam použitím List.remove (). Avšak efektívne odstránenie všetkých výskytov hodnoty je oveľa ťažšie.

V tejto príručke uvidíme niekoľko riešení tohto problému s popisom výhod a nevýhod.

Kvôli čitateľnosti používame zvyk zoznam (int…) metóda v testoch, ktorá vráti an ArrayList obsahujúce prvky, ktoré sme prešli.

2. Pomocou a zatiaľ čo Slučka

Keďže vieme, ako na to odstrániť jeden prvok a robiť to opakovane v slučke vyzerá dosť jednoducho:

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

Nefunguje to však podľa očakávaní:

// daný Zoznam zoznam = zoznam (1, 2, 3); int hodnotaToRemove = 1; // keď assertThatThrownBy (() -> removeAll (list, valueToRemove)) .isInstanceOf (IndexOutOfBoundsException.class);

Problém je v 3. riadku: voláme List.remove (int), ktorý zaobchádza so svojím argumentom ako s indexom, nie s hodnotou, ktorú chceme odstrániť.

Vo vyššie uvedenom teste vždy voláme list.odstrániť (1), ale index prvku, ktorý chceme odstrániť, je 0. Telefonovanie List.remove () posunie všetky prvky po odstránenom na menšie indexy.

V tomto scenári to znamená, že odstránime všetky prvky okrem prvého.

Keď zostane iba prvý, index 1 bude nelegálne. Preto dostaneme Výnimka.

Upozorňujeme, že tomuto problému čelíme, iba ak zavoláme List.remove () s primitívom bajt, krátke, char alebo int Argument, pretože prvá vec, ktorú kompilátor urobí, keď sa pokúša nájsť zodpovedajúcu preťaženú metódu, sa rozširuje.

Môžeme to opraviť odovzdaním hodnoty ako Celé číslo:

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

Teraz kód funguje podľa očakávania:

// daný Zoznam zoznam = zoznam (1, 2, 3); int hodnotaToRemove = 1; // when removeAll (list, valueToRemove); // potom assertThat (list) .isEqualTo (list (2, 3));

Odkedy Zoznam.obsahuje () a List.remove () obaja musia nájsť prvý výskyt prvku, tento kód spôsobí zbytočný prechod prvku.

Môžeme urobiť lepšie, ak uložíme index prvého výskytu:

void removeAll (zoznam, celočíselný prvok) {int index; while ((index = list.indexOf (element))> = 0) {list.remove (index); }}

Môžeme overiť, že to funguje:

// daný Zoznam zoznam = zoznam (1, 2, 3); int hodnotaToRemove = 1; // when removeAll (list, valueToRemove); // potom assertThat (list) .isEqualTo (list (2, 3));

Aj keď tieto riešenia vytvárajú krátky a čistý kód, stále majú slabý výkon: pretože nesledujeme pokrok, List.remove () musí nájsť prvý výskyt poskytnutej hodnoty, aby ju odstránil.

Tiež, keď používame ArrayList, posun prvkov môže spôsobiť veľa kopírovaní odkazov, dokonca niekoľkokrát aj realokáciu podporného poľa.

3. Odstránenie, kým Zoznam Zmeny

List.remove (prvok E) má funkciu, ktorú sme ešte nespomenuli: ju vracia a boolovský hodnota, ktorá je pravda ak Zoznam sa zmenila z dôvodu operácie, preto obsahovala prvok.

Poznač si to List.remove (int index) vráti neplatnosť, pretože ak je poskytnutý index platný, znak Zoznam vždy to odstráni. Inak to hodí IndexOutOfBoundsException.

Vďaka tomu môžeme vykonávať sťahovanie až do Zoznam zmeny:

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

Funguje podľa očakávania:

// daný Zoznam zoznam = zoznam (1, 1, 2, 3); int hodnotaToRemove = 1; // when removeAll (list, valueToRemove); // potom assertThat (list) .isEqualTo (list (2, 3));

Napriek tomu, že je táto implementácia krátka, trpí rovnakými problémami, ktoré sme opísali v predchádzajúcej časti.

3. Pomocou a pre Slučka

Náš pokrok môžeme sledovať prechádzaním cez prvky s a pre slučku a odstráňte aktuálnu, ak sa zhoduje:

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

Funguje podľa očakávania:

// daný Zoznam zoznam = zoznam (1, 2, 3); int hodnotaToRemove = 1; // when removeAll (list, valueToRemove); // potom assertThat (list) .isEqualTo (list (2, 3));

Ak to však skúsime s iným vstupom, poskytne nesprávny výstup:

// daný Zoznam zoznam = zoznam (1, 1, 2, 3); int hodnotaToRemove = 1; // when removeAll (list, valueToRemove); // potom assertThat (list) .isEqualTo (list (1, 2, 3));

Poďme si podrobne zanalyzovať, ako kód funguje:

• i = 0
  • element a list.get (i) sú obaja rovní 1 na riadku 3, takže Java vstúpi do tela súboru ak vyhlásenie,
  • odstránime prvok na indexe 0,
  • tak zoznam teraz obsahuje 1, 2 a 3
• i = 1
  • list.get (i) vracia 2 pretože keď odstránime prvok z a Zoznam, posúva všetky postupujúce prvky na menšie indexy

Tomuto problému teda čelíme, keď máme dve susedné hodnoty, ktoré chceme odstrániť. Aby sme to vyriešili, mali by sme zachovať premennú cyklu.

Znižuje sa, keď odstránime prvok:

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

Zvyšuje sa iba vtedy, keď prvok neodstránime:

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

Upozorňujeme, že v druhom prípade sme vyhlásenie odstránili i ++ na riadku 2.

Obidve riešenia fungujú podľa očakávaní:

// daný Zoznam zoznam = zoznam (1, 1, 2, 3); int hodnotaToRemove = 1; // when removeAll (list, valueToRemove); // potom assertThat (list) .isEqualTo (list (2, 3));

Táto implementácia sa na prvý pohľad javí ako správna. Stále však má vážne problémy s výkonom:

• odstránenie prvku z ArrayList, posúva všetky položky po ňom
• prístup k prvkom indexom v a LinkedList znamená prechádzanie jednotlivými prvkami jednotlivými prvkami, kým nenájdeme index

4. Pomocou a pre každý Slučka

Od Java 5 môžeme používať pre každý slučka na iteráciu cez a Zoznam. Použijeme ho na odstránenie prvkov:

void removeAll (List list, int element) {for (Integer number: list) {if (Objects.equals (number, element)) {list.remove (number); }}}

Všimnite si, že to používame Celé číslo ako typ premennej slučky. Preto nedostaneme NullPointerException.

Aj týmto spôsobom sa dovolávame List.remove (prvok E), ktorý očakáva hodnotu, ktorú chceme odstrániť, nie index.

Rovnako čisté, ako to vyzerá, bohužiaľ nefunguje:

// daný Zoznam zoznam = zoznam (1, 1, 2, 3); int hodnotaToRemove = 1; // keď assertThatThrownBy (() -> removeWithForEachLoop (list, valueToRemove)) .isInstanceOf (ConcurrentModificationException.class);

The pre každý slučka používa Iterátor prechádzať živlami. Avšak keď upravujeme Zoznam, Iterátor sa dostane do nekonzistentného stavu. Preto to hodí ConcurrentModificationException.

Ponaučenie je: nemali by sme upravovať a Zoznam, zatiaľ čo k jeho prvkom pristupujeme v a pre každý slučka.

5. Pomocou an Iterátor

Môžeme použiť Iterátor priamo prechádzať a upravovať Zoznam s tým:

void removeAll (List list, int element) {for (Iterator i = list.iterator (); i.hasNext ();) {Integer number = i.next (); if (Objects.equals (number, element)) {i.remove (); }}}

Tadiaľto, the Iterátor môže sledovať stav súboru Zoznam (pretože sa v ňom vykonáva úprava). Výsledkom je, že vyššie uvedený kód funguje podľa očakávania:

// daný Zoznam zoznam = zoznam (1, 1, 2, 3); int hodnotaToRemove = 1; // when removeAll (list, valueToRemove); // potom assertThat (list) .isEqualTo (list (2, 3));

Keďže každý Zoznam triedy môžu poskytnúť svoje vlastné Iterátor môžeme s istotou predpokladať, že implementuje prechod a odstránenie prvku najefektívnejším možným spôsobom.

Avšak pomocou ArrayList stále znamená veľa radenia prvkov (a možno pole prerozdelené). Vyššie uvedený kód je tiež o niečo ťažšie čitateľný, pretože sa líši od štandardu pre slučka, ktorú väčšina vývojárov pozná.

6. Zbieranie

Do tejto doby sme pôvodné upravovali Zoznam objekt odstránením položiek, ktoré sme nepotrebovali. Skôr môžeme vytvoriť nový Zoznam a zbierať predmety, ktoré si chceme nechať:

List removeAll (List list, int element) {List remainingElements = new ArrayList (); pre (Celé číslo: zoznam) {if (! Objects.equals (číslo, prvok)) {zostávajúceElements.add (číslo); }} vrátiť zostávajúce prvky; }

Pretože poskytujeme výsledok v novom Zoznam objekt, musíme ho vrátiť z metódy. Preto musíme metódu použiť iným spôsobom:

// daný Zoznam zoznam = zoznam (1, 1, 2, 3); int hodnotaToRemove = 1; // when List result = removeAll (list, valueToRemove); // potom assertThat (result) .isEqualTo (list (2, 3));

Upozorňujeme, že teraz môžeme použiť pre každý slučka, pretože nemeníme Zoznam momentálne prechádzame.

Pretože nie sú odstránené, nie je potrebné posúvať prvky. Preto táto implementácia funguje dobre, keď používame ArrayList.

Táto implementácia sa v niektorých ohľadoch správa inak ako predchádzajúce:

• nemení pôvodný text Zoznam ale vracia nový jeden
• o tom, čo sa vrátilo, rozhodne metóda ZoznamImplementácia je, môže sa líšiť od originálu

Tiež môžeme upraviť našu implementáciu na získať staré správanie; vyčistíme originál Zoznam a pridajte do nej zhromaždené prvky:

void removeAll (List list, int element) {List remainingElements = new ArrayList (); pre (Celé číslo: zoznam) {if (! Objects.equals (číslo, prvok)) {zostávajúce prvky.add (číslo); }} list.clear (); list.addAll (zostávajúce prvky); }

Funguje to rovnako ako predtým:

// daný Zoznam zoznam = zoznam (1, 1, 2, 3); int hodnotaToRemove = 1; // when removeAll (list, valueToRemove); // potom assertThat (list) .isEqualTo (list (2, 3));

Pretože nemeníme Zoznam neustále nemusíme pristupovať k prvkom podľa polohy alebo ich posúvať. Existujú iba dve možné realokácie polí: keď voláme List.clear () a List.addAll ().

7. Používanie Stream API

Java 8 predstavila výrazy lambda a stream API. Vďaka týmto výkonným funkciám môžeme vyriešiť náš problém pomocou veľmi čistého kódu:

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

Toto riešenie funguje rovnako, ako keď sme zbierali zvyšné prvky.

Vďaka tomu má rovnaké vlastnostia mali by sme ho použiť na vrátenie výsledku:

// daný Zoznam zoznam = zoznam (1, 1, 2, 3); int hodnotaToRemove = 1; // kedy Výsledok zoznamu = removeAll (list, valueToRemove); // potom assertThat (result) .isEqualTo (list (2, 3));

Upozorňujeme, že ho môžeme previesť tak, aby fungoval ako ostatné riešenia, a to rovnakým spôsobom, aký sme urobili pri pôvodnej implementácii „zhromažďovania“.

8. Používanie removeIf

S lambdami a funkčnými rozhraniami predstavila Java 8 aj niektoré rozšírenia API. Napríklad List.removeIf () metóda, ktorá implementuje to, čo sme videli v poslednej časti.

Očakáva a Predikát, ktorá by sa mala vrátiť pravda keď chceme odstrániť prvok, na rozdiel od predchádzajúceho príkladu, kam sme sa museli vrátiť pravda keď sme si chceli prvok ponechať:

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

Funguje to ako ostatné riešenia vyššie:

// daný Zoznam zoznam = zoznam (1, 1, 2, 3); int hodnotaToRemove = 1; // when removeAll (list, valueToRemove); // potom assertThat (list) .isEqualTo (list (2, 3));

Vzhľadom na to, že Zoznam sama implementuje túto metódu, môžeme s istotou predpokladať, že má najlepší dostupný výkon. Toto riešenie navyše poskytuje najčistejší kód zo všetkých.

9. Záver

V tomto článku sme videli veľa spôsobov, ako vyriešiť jednoduchý problém, vrátane nesprávnych. Analyzovali sme ich, aby sme našli najlepšie riešenie pre každý scenár.

Ako obvykle sú príklady k dispozícii na GitHub.