Uklonite sve pojave određene vrijednosti s popisa

1. Uvod

U Javi je jednostavno ukloniti određenu vrijednost iz a Popis koristeći List.remove (). Međutim, učinkovito uklanjanje svih pojava vrijednosti je puno teže.

U ovom uputstvu vidjet ćemo više rješenja za ovaj problem, opisujući prednosti i nedostatke.

Radi čitljivosti koristimo običaj popis (int…) metoda u testovima, koja vraća ArrayList koji sadrže elemente koje smo prošli.

2. Korištenje a dok Petlja

Otkad znamo kako uklonite jedan element, ponavljajući to uzastopno izgleda dovoljno jednostavno:

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

Međutim, to ne radi kako se očekivalo:

// zadani popis list = list (1, 2, 3); int valueToRemove = 1; // kada assertThatThrownBy (() -> removeAll (list, valueToRemove)) .isInstanceOf (IndexOutOfBoundsException.class);

Problem je u 3. retku: zovemo List.remove (int), koja svoj argument tretira kao indeks, a ne vrijednost koju želimo ukloniti.

U gornjem testu uvijek zovemo list.remove (1), ali indeks elementa koji želimo ukloniti je 0. Pozivanje List.remove () pomiče sve elemente nakon uklonjenog na manje indekse.

U ovom scenariju to znači da brišemo sve elemente, osim prvog.

Kad ostane samo prvi, indeks 1 bit će ilegalno. Stoga dobivamo Iznimka.

Imajte na umu da se s tim problemom suočavamo samo ako nazovemo List.remove () s primitivnom bajt, kratko, char ili int argument, budući da se prvo što prevodilac pokušava učiniti kada pokuša pronaći odgovarajuću preopterećenu metodu, širi.

To možemo ispraviti dodavanjem vrijednosti kao Cijeli broj:

void removeAll (Lista popisa, Integer element) {while (list.contens (element)) {list.remove (element); }}

Sada kod radi kako se očekivalo:

// zadani popis list = list (1, 2, 3); int valueToRemove = 1; // kada removeAll (list, valueToRemove); // zatim assertThat (list) .isEqualTo (list (2, 3));

Od List.contens () i List.remove () obojica moraju pronaći prvu pojavu elementa, ovaj kod uzrokuje nepotrebno okretanje elementa.

Možemo bolje ako pohranimo indeks prve pojave:

void removeAll (Popis popisa, Integer element) {int indeks; while ((index = list.indexOf (element))> = 0) {list.remove (index); }}

Možemo provjeriti radi li:

// zadani popis list = list (1, 2, 3); int valueToRemove = 1; // kada removeAll (list, valueToRemove); // zatim assertThat (list) .isEqualTo (list (2, 3));

Iako ova rješenja proizvode kratki i čisti kod, još uvijek imaju loš učinak: jer ne pratimo napredak, List.remove () mora pronaći prvu pojavu navedene vrijednosti da bi je izbrisao.

Također, kada koristimo ArrayList, pomicanje elemenata može uzrokovati kopiranje mnogih referenci, čak i nekoliko puta preraspodjelu pozadinskog niza.

3. Uklanjanje do Popis Promjene

List.remove (E element) ima značajku koju još nismo spomenuli: to vraća a boolean vrijednost, koja je pravi ako je Popis promijenio zbog operacije, stoga je sadržavao element.

Imajte na umu, to List.remove (int indeks) vraća void, jer ako je navedeni indeks valjan, Popis uvijek ga uklanja. Inače, baca IndexOutOfBoundsException.

Pomoću toga možemo obavljati uklanjanja do Popis promjene:

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

Djeluje prema očekivanjima:

// zadani popis popis = popis (1, 1, 2, 3); int valueToRemove = 1; // kada removeAll (list, valueToRemove); // zatim assertThat (list) .isEqualTo (list (2, 3));

Iako je kratka, ova provedba pati od istih problema koje smo opisali u prethodnom odjeljku.

3. Korištenje a za Petlja

Svoj napredak možemo pratiti kretanjem kroz elemente pomoću a za petlju i uklonite trenutnu ako se podudara:

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

Djeluje prema očekivanjima:

// zadani popis list = list (1, 2, 3); int valueToRemove = 1; // kada removeAll (list, valueToRemove); // zatim assertThat (list) .isEqualTo (list (2, 3));

Međutim, ako ga pokušamo s drugim ulazom, on daje netočan izlaz:

// zadani popis popis = popis (1, 1, 2, 3); int valueToRemove = 1; // kada removeAll (list, valueToRemove); // zatim assertThat (list) .isEqualTo (list (1, 2, 3));

Analizirajmo kako kôd radi, korak po korak:

  • i = 0
    • element i list.get (i) su oba jednaka 1 u retku 3, tako da Java ulazi u tijelo ako izjava,
    • uklanjamo element u indeksu 0,
    • tako popis sada sadrži 1, 2 i 3
  • i = 1
    • list.get (i) vraća se 2 jer kada uklonimo element iz a Popis, prebacuje sve postupne elemente na manje indekse

Pa se s tim problemom suočavamo kada imamo dvije susjedne vrijednosti, koje želimo ukloniti. Da bismo to riješili, trebali bismo održavati varijablu petlje.

Smanjivanje kada uklonimo element:

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

Povećavanje samo kada ne uklonimo element:

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

Imajte na umu da smo u potonjem uklonili izjavu i ++ u retku 2.

Oba rješenja rade prema očekivanjima:

// zadani popis popis = popis (1, 1, 2, 3); int valueToRemove = 1; // kada removeAll (list, valueToRemove); // zatim assertThat (list) .isEqualTo (list (2, 3));

Ova se primjena čini prikladnom na prvi pogled. Međutim, još uvijek ima ozbiljni problemi s performansama:

  • uklanjanje elementa iz ArrayList, prebacuje sve stavke nakon njega
  • pristup elementima indeksom u a LinkedList znači kretanje kroz elemente jedan po jedan dok ne pronađemo indeks

4. Korištenje a za svakoga Petlja

Od Jave 5 možemo koristiti za svakoga petlja za itiranje kroz a Popis. Upotrijebimo ga za uklanjanje elemenata:

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

Imajte na umu da koristimo Cijeli broj kao tip varijable petlje. Stoga nećemo dobiti a NullPointerException.

Također, na ovaj se način pozivamo List.remove (E element), koja očekuje vrijednost koju želimo ukloniti, a ne indeks.

Koliko god izgledao čisto, nažalost, ne ide:

// zadani popis popis = popis (1, 1, 2, 3); int valueToRemove = 1; // kada assertThatThrownBy (() -> removeWithForEachLoop (list, valueToRemove)) .isInstanceOf (ConcurrentModificationException.class);

The za svakoga petlja koristi Iterator za prelazak kroz elemente. Međutim, kada modificiramo Popis, Iterator dospije u nedosljedno stanje. Stoga baca ConcurrentModificationException.

Pouka je: ne bismo trebali mijenjati a Popis, dok pristupamo njegovim elementima u a za svakoga petlja.

5. Korištenjem Iterator

Možemo koristiti Iterator izravno za prelazak i izmjenu datoteke Popis s tim:

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

Ovuda, the Iterator može pratiti stanje u Popis (jer vrši izmjenu). Kao rezultat, gornji kod radi kako se očekivalo:

// zadani popis popis = popis (1, 1, 2, 3); int valueToRemove = 1; // kada removeAll (list, valueToRemove); // zatim assertThat (list) .isEqualTo (list (2, 3));

Budući da je svaki Popis razreda mogu pružiti svoje Iterator provedba, možemo sigurno pretpostaviti da implementira prelazak i uklanjanje elemenata na najučinkovitiji mogući način.

Međutim, koristeći ArrayList još uvijek znači puno promjena elemenata (a možda i preraspodjela niza). Također, gornji je kod malo teži za čitanje, jer se razlikuje od standardnog za petlja, s kojom je upoznat većina programera.

6. Sakupljanje

Do toga smo modificirali izvornik Popis objekt uklanjanjem predmeta koji nam nisu trebali. Dapače, možemo stvoriti novi Popis i prikupiti predmete koje želimo zadržati:

Popis removeAll (Popis popisa, element int) {Popis preostalihElemenata = novi ArrayList (); for (Integer number: list) {if (! Objects.equals (number, element)) {preostaliElements.add (broj); }} vrati preostale elemente; }

Budući da rezultat pružamo u novom Popis objekt, moramo ga vratiti iz metode. Stoga metodu moramo koristiti na drugi način:

// zadani popis popis = popis (1, 1, 2, 3); int valueToRemove = 1; // kada je Popis rezultat = removeAll (list, valueToRemove); // zatim assertThat (rezultat) .isEqualTo (list (2, 3));

Imajte na umu da sada možemo koristiti za svakoga petlja jer ne mijenjamo Popis trenutno prolazimo kroz.

Budući da nema uklanjanja, nema potrebe za pomicanjem elemenata. Stoga se ova implementacija dobro izvodi kada koristimo ArrayList.

Ova se implementacija na neki način ponaša drugačije od prethodnih:

  • ne mijenja original Popis ali vraća novi jedan
  • metoda odlučuje što se vraća Popis'S provedba je, može se razlikovati od originala

Također, možemo izmijeniti našu implementaciju u dobiti staro ponašanje; očistimo original Popis i dodajte mu prikupljene elemente:

void removeAll (Popis popisa, element int) {Popis preostalihElemenata = novi ArrayList (); for (Integer number: list) {if (! Objects.equals (number, element)) {preostaliElements.add (broj); }} list.clear (); list.addAll (preostaliElementi); }

Djeluje na isti način kao i prije:

// zadani popis popis = popis (1, 1, 2, 3); int valueToRemove = 1; // kada removeAll (list, valueToRemove); // zatim assertThat (list) .isEqualTo (list (2, 3));

Budući da ne mijenjamo Popis kontinuirano, ne moramo pristupiti elementima po položaju ili ih pomicati. Također, postoje samo dvije moguće preraspodjele niza: kada zovemo List.clear () i List.addAll ().

7. Korištenje Stream API-ja

Java 8 predstavila je lambda izraze i API za stream. Pomoću ovih moćnih značajki svoj problem možemo riješiti vrlo čistim kodom:

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

Ovo rješenje radi na isti način, kao kad smo prikupljali preostale elemente.

Kao rezultat, ima iste karakteristike, i trebali bismo ga koristiti za vraćanje rezultata:

// zadani popis popis = popis (1, 1, 2, 3); int valueToRemove = 1; // kada je Popis rezultat = removeAll (list, valueToRemove); // zatim assertThat (rezultat) .isEqualTo (list (2, 3));

Imajte na umu da ga možemo pretvoriti u rad kao i ostala rješenja s istim pristupom kao i s izvornom implementacijom "prikupljanja".

8. Korištenje ukloniAko

Uz lambde i funkcionalna sučelja, Java 8 je uvela i neka API proširenja. Na primjer, List.removeIf () metoda, koja provodi ono što smo vidjeli u prošlom odjeljku.

Očekuje a Predikat, koji bi se trebao vratiti pravi kad želimo ukloniti element, za razliku od prethodnog primjera, gdje smo se morali vratiti pravi kada smo željeli zadržati element:

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

Djeluje poput ostalih gornjih rješenja:

// zadani popis popis = popis (1, 1, 2, 3); int valueToRemove = 1; // kada removeAll (list, valueToRemove); // zatim assertThat (list) .isEqualTo (list (2, 3));

Zbog činjenice da je Popis sam primjenjuje ovu metodu, možemo sigurno pretpostaviti da ona ima najbolje dostupne performanse. Povrh svega, ovo rješenje pruža najčišći kôd od svih.

9. Zaključak

U ovom smo članku vidjeli mnogo načina za rješavanje jednostavnog problema, uključujući i netočne. Analizirali smo ih kako bismo pronašli najbolje rješenje za svaki scenarij.

Kao i obično, primjeri su dostupni na GitHubu.