streamalism.org

1. Introduksjon

I Java er det greit å fjerne en bestemt verdi fra en Liste ved hjelp av List.remove (). Derimot, effektivt fjerne alle forekomster av en verdi er mye vanskeligere.

I denne opplæringen ser vi flere løsninger på dette problemet, som beskriver fordeler og ulemper.

For lesbarhets skyld bruker vi en tilpasset liste (int ...) metode i testene, som returnerer en ArrayList inneholder elementene vi passerte.

2. Bruke en samtidig som Løkke

Siden vi vet hvordan fjern et enkelt element, gjør det gjentatte ganger i en løkke ser enkel nok ut:

ugyldig removeAll (Listeliste, int-element) {while (list.contains (element)) {list.remove (element); }}

Det fungerer imidlertid ikke som forventet:

// gitt Listeliste = liste (1, 2, 3); int valueToRemove = 1; // når assertThatThrownBy (() -> removeAll (liste, valueToRemove)) .isInstanceOf (IndexOutOfBoundsException.class);

Problemet er i 3. linje: vi ringer List.remove (int), som behandler argumentet som indeksen, ikke verdien vi vil fjerne.

I testen ovenfor ringer vi alltid list.remove (1), men elementets indeks vi vil fjerne er 0. Ringer List.remove () forskyver alle elementene etter den fjernede til mindre indekser.

I dette scenariet betyr det at vi sletter alle elementene, bortsett fra det første.

Når bare den første gjenstår, indeksen 1 vil være ulovlig. Derfor får vi en Unntak.

Merk at vi bare møter dette problemet hvis vi ringer List.remove () med en primitiv byte, kort, røye eller int argumentet, siden det første kompilatoren gjør når den prøver å finne den matchende overbelastede metoden, utvides.

Vi kan korrigere det ved å sende verdien som Heltall:

ugyldig removeAll (Listeliste, Heltallelement) {while (list.contains (element)) {list.remove (element); }}

Nå fungerer koden som forventet:

// gitt Listeliste = liste (1, 2, 3); int valueToRemove = 1; // når removeAll (liste, valueToRemove); // deretter hevder at (liste) .isEqualTo (liste (2, 3));

Siden List.contains () og List.remove () begge må finne den første forekomsten av elementet, denne koden forårsaker unødvendig elementgjennomgang.

Vi kan gjøre det bedre hvis vi lagrer indeksen for den første forekomsten:

ugyldig removeAll (Listeliste, Heltallelement) {int-indeks; mens ((index = list.indexOf (element))> = 0) {list.remove (index); }}

Vi kan bekrefte at det fungerer:

// gitt Listeliste = liste (1, 2, 3); int valueToRemove = 1; // når removeAll (liste, valueToRemove); // deretter hevder at (liste) .isEqualTo (liste (2, 3));

Mens disse løsningene gir kort og ren kode, de har fortsatt dårlig ytelse: fordi vi ikke holder oversikt over fremgangen, List.remove () må finne den første forekomsten av den oppgitte verdien for å slette den.

Også når vi bruker en ArrayList, elementforskyvning kan føre til mange referansekopieringer, til og med omfordele backing-arrayet flere ganger.

3. Fjerne inntil Liste Endringer

List.remove (E-element) har en funksjon vi ikke nevnte ennå: den returnerer a boolsk verdi, som er ekte hvis Liste endret på grunn av operasjonen, derfor inneholdt den elementet.

Noter det List.remove (int-indeks) returnerer ugyldige, fordi hvis den angitte indeksen er gyldig, vil Liste fjerner den alltid. Ellers kaster det IndexOutOfBoundsException.

Med dette kan vi utføre fjerninger til Liste Endringer:

ugyldig removeAll (Listeliste, int-element) {while (list.remove (element)); }

Det fungerer som forventet:

// gitt Listeliste = liste (1, 1, 2, 3); int valueToRemove = 1; // når removeAll (liste, valueToRemove); // deretter hevder at (liste) .isEqualTo (liste (2, 3));

Til tross for at den er kort, lider denne implementeringen av de samme problemene som vi beskrev i forrige avsnitt.

3. Bruke en til Løkke

Vi kan holde oversikt over fremgangen vår ved å krysse gjennom elementene med en til sløyfe og fjern den gjeldende hvis den samsvarer med:

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

Det fungerer som forventet:

// gitt Listeliste = liste (1, 2, 3); int valueToRemove = 1; // når removeAll (liste, valueToRemove); // deretter hevder at (liste) .isEqualTo (liste (2, 3));

Men hvis vi prøver det med en annen inngang, gir det en feil utgang:

// gitt Listeliste = liste (1, 1, 2, 3); int valueToRemove = 1; // når removeAll (liste, valueToRemove); // deretter hevder at (liste) .isEqualTo (liste (1, 2, 3));

La oss analysere hvordan koden fungerer trinnvis:

• jeg = 0
  • element og list.get (i) er begge like 1 på linje 3, så Java kommer inn i kroppen til hvis uttalelse,
  • vi fjerner elementet ved indeks 0,
  • så liste inneholder nå 1, 2 og 3
• jeg = 1
  • list.get (i) returnerer 2 fordi når vi fjerner et element fra en Liste, skifter det alle pågående elementer til mindre indekser

Så vi møter dette problemet når vi har to tilstøtende verdier, som vi vil fjerne. For å løse dette, bør vi opprettholde løkkevariabelen.

Å redusere det når vi fjerner elementet:

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

Å øke det bare når vi ikke fjerner elementet:

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

Merk at i sistnevnte fjernet vi uttalelsen i ++ på linje 2.

Begge løsningene fungerer som forventet:

// gitt Listeliste = liste (1, 1, 2, 3); int valueToRemove = 1; // når removeAll (liste, valueToRemove); // deretter hevder at (liste) .isEqualTo (liste (2, 3));

Denne implementeringen virker riktig for første øyekast. Imidlertid har det fortsatt alvorlige ytelsesproblemer:

• fjerne et element fra en ArrayList, skifter alle elementene etter den
• få tilgang til elementer etter indeks i en LinkedList betyr å krysse gjennom elementene en etter en til vi finner indeksen

4. Bruke en for hver Løkke

Siden Java 5 kan vi bruke for hver løkke for å gjenta gjennom en Liste. La oss bruke den til å fjerne elementer:

ugyldig removeAll (Listeliste, int-element) {for (Heltall: liste) {if (Objects.equals (number, element)) {list.remove (number); }}}

Merk at vi bruker Heltall som sløyfevariabelens type. Derfor får vi ikke en NullPointerException.

Også på denne måten påberoper vi oss List.remove (E-element), som forventer verdien vi vil fjerne, ikke indeksen.

Så rent som det ser ut, dessverre fungerer det ikke:

// gitt Listeliste = liste (1, 1, 2, 3); int valueToRemove = 1; // når assertThatThrownBy (() -> removeWithForEachLoop (liste, valueToRemove)) .isInstanceOf (ConcurrentModificationException.class);

De for hver loop bruker Iterator å krysse gjennom elementene. Derimot, når vi endrer Liste, den Iterator kommer i en inkonsekvent tilstand. Derfor kaster det ConcurrentModificationException.

Leksjonen er: vi bør ikke endre en Liste, mens vi får tilgang til elementene i en for hver Løkke.

5. Bruke en Iterator

Vi kan bruke Iterator direkte for å krysse og modifisere Liste med det:

ugyldig removeAll (Listeliste, int-element) {for (Iterator i = list.iterator (); i.hasNext ();) {Heltall = i.next (); hvis (Objects.equals (nummer, element)) {i.remove (); }}}

Denne måten, de Iterator kan spore tilstanden til Liste (fordi det gjør modifikasjonen). Som et resultat fungerer koden ovenfor som forventet:

// gitt Listeliste = liste (1, 1, 2, 3); int valueToRemove = 1; // når removeAll (liste, valueToRemove); // deretter assertThat (liste) .isEqualTo (liste (2, 3));

Siden hver Liste klasse kan gi sine egne Iterator implementering, kan vi trygt anta at den implementerer traversering og fjerning av elementer på en mest mulig effektiv måte.

Imidlertid bruker ArrayList betyr fortsatt mye elementskifting (og kanskje omplassering av array). Dessuten er koden ovenfor litt vanskeligere å lese, fordi den skiller seg fra standarden til loop, som de fleste utviklere er kjent med.

6. Samling

Inntil dette modifiserte vi originalen Liste objektet ved å fjerne elementene vi ikke trengte. Vi kan heller lage en ny Liste og samle varene vi vil beholde:

Liste removeAll (Liste liste, int element) {Liste gjenværendeElements = ny ArrayList (); for (Heltall: liste) {if (! Objects.equals (nummer, element)) {gjenværendeElements.add (nummer); }} returner gjenværende Elementer; }

Siden vi gir resultatet i en ny Liste objekt, må vi returnere det fra metoden. Derfor må vi bruke metoden på en annen måte:

// gitt Listeliste = liste (1, 1, 2, 3); int valueToRemove = 1; // når listeresultat = removeAll (liste, valueToRemove); // deretter assertThat (resultat) .isEqualTo (liste (2, 3));

Merk at nå kan vi bruke for hver loop siden vi ikke endrer Liste vi gjentar for øyeblikket.

Fordi det ikke er noen fjerninger, er det ikke nødvendig å flytte elementene. Derfor fungerer denne implementeringen bra når vi bruker en ArrayList.

Denne implementeringen oppfører seg annerledes på noen måter enn de tidligere:

• den endrer ikke originalen Liste men returnerer en ny en
• metoden bestemmer hva som returneres Liste’Implementering er, kan det være annerledes enn originalen

Vi kan også endre implementeringen til få den gamle oppførselen; vi tømmer originalen Liste og legg til de innsamlede elementene i den:

ugyldig removeAll (Liste liste, int element) {Liste gjenværendeElements = ny ArrayList (); for (Integer number: list) {if (! Objects.equals (number, element)) {gjenværendeElements.add (nummer); }} list.clear (); list.addAll (gjenværendeElements); }

Det fungerer på samme måte som de før:

// gitt Listeliste = liste (1, 1, 2, 3); int valueToRemove = 1; // når removeAll (liste, valueToRemove); // deretter hevder at (liste) .isEqualTo (liste (2, 3));

Siden vi ikke endrer Liste kontinuerlig trenger vi ikke å få tilgang til elementer etter posisjon eller skifte dem. Dessuten er det bare to mulige omfordelinger: når vi ringer List.clear () og List.addAll ().

7. Bruke Stream API

Java 8 introduserte lambda-uttrykk og stream-API. Med disse kraftige funksjonene kan vi løse problemet vårt med en veldig ren kode:

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

Denne løsningen fungerer på samme måte, som når vi samlet inn de gjenværende elementene.

Som et resultat har den samme egenskaper, og vi bør bruke den til å returnere resultatet:

// gitt Listeliste = liste (1, 1, 2, 3); int valueToRemove = 1; // når listeresultat = removeAll (liste, valueToRemove); // deretter assertThat (resultat) .isEqualTo (liste (2, 3));

Merk at vi kan konvertere den til å fungere som de andre løsningene med samme tilnærming som vi gjorde med den opprinnelige 'samle' implementeringen.

8. Bruke fjerneHvis

Med lambdas og funksjonelle grensesnitt introduserte Java 8 også noen API-utvidelser. For eksempel List.removeIf () metode, som implementerer det vi så i forrige avsnitt.

Det forventer en Predikere, som skal komme tilbake ekte når vi vil fjerne elementet, i motsetning til forrige eksempel, der vi måtte tilbake ekte da vi ønsket å beholde elementet:

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

Det fungerer som de andre løsningene ovenfor:

// gitt Listeliste = liste (1, 1, 2, 3); int valueToRemove = 1; // når removeAll (liste, valueToRemove); // deretter hevderThat (liste) .isEqualTo (liste (2, 3));

På grunn av det faktum at Liste selv implementerer denne metoden, kan vi trygt anta at den har den beste ytelsen tilgjengelig. I tillegg gir denne løsningen den reneste koden av alle.

9. Konklusjon

I denne artikkelen så vi mange måter å løse et enkelt problem, inkludert feil. Vi analyserte dem for å finne den beste løsningen for hvert scenario.

Som vanlig er eksemplene tilgjengelige på GitHub.