Fjern alle forekomster af en bestemt værdi fra en liste

1. Introduktion

I Java er det ligetil at fjerne en bestemt værdi fra en Liste ved brug af List.remove (). Imidlertid, effektivt at fjerne alle forekomster af en værdi er meget sværere.

I denne vejledning ser vi flere løsninger på dette problem, der beskriver fordele og ulemper.

Af hensyn til læsbarheden bruger vi en brugerdefineret liste (int ...) metode i testene, som returnerer en ArrayList indeholdende de elementer, vi passerede.

2. Brug af en mens Sløjfe

Da vi ved, hvordan man gør det fjern et enkelt element, gør det gentagne gange i en løkke ser enkel nok ud:

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

Det fungerer dog ikke som forventet:

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

Problemet er i 3. linje: vi kalder List.remove (int), der behandler sit argument som indekset, ikke den værdi, vi vil fjerne.

I testen ovenfor kalder vi altid list.remove (1), men elementets indeks, vi vil fjerne, er 0. Ringer List.remove () skifter alle elementer efter den fjernede til mindre indekser.

I dette scenarie betyder det, at vi sletter alle elementer undtagen det første.

Når kun det første er tilbage, indekset 1 vil være ulovligt. Derfor får vi en Undtagelse.

Bemærk, at vi kun står over for dette problem, hvis vi ringer List.remove () med en primitiv byte, kort, char eller int argument, da det første, som kompilatoren gør, når det forsøger at finde den matchende overbelastede metode, udvides.

Vi kan rette det ved at overføre værdien som Heltal:

ugyldig removeAll (liste liste, heltal element) {while (list.contains (element)) {list.remove (element); }}

Nu fungerer koden som forventet:

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

Siden List.contains () og List.remove () begge skal finde den første forekomst af elementet, denne kode forårsager unødvendig gennemgang af elementet.

Vi kan gøre det bedre, hvis vi gemmer indekset for den første begivenhed:

ugyldig removeAll (liste liste, heltal element) {int index; mens ((index = list.indexOf (element))> = 0) {list.remove (index); }}

Vi kan kontrollere, at det fungerer:

// given liste liste = liste (1, 2, 3); int valueToRemove = 1; // når removeAll (liste, valueToRemove); // derefter assertThat (liste) .isEqualTo (liste (2, 3));

Mens disse løsninger producerer kort og ren kode, de har stadig dårlig præstation: fordi vi ikke holder styr på fremskridtene, List.remove () skal finde den første forekomst af den angivne værdi for at slette den.

Også når vi bruger en ArrayList, elementforskydning kan forårsage mange referencekopiering, endog omfordele backing-arrayet flere gange.

3. Fjernelse indtil Liste Ændringer

List.remove (E-element) har en funktion, som vi ikke nævnte endnu: den returnerer a boolsk værdi, hvilket er rigtigt hvis den Liste ændret på grund af operationen, derfor indeholdt den elementet.

Noter det List.remove (int-indeks) returnerer ugyldige, for hvis det angivne indeks er gyldigt, bliver Liste fjerner det altid. Ellers kaster det IndexOutOfBoundsException.

Med dette kan vi udføre fjernelser indtil Liste ændringer:

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

Det fungerer som forventet:

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

På trods af at den er kort, lider denne implementering af de samme problemer, som vi beskrev i det foregående afsnit.

3. Brug af en til Sløjfe

Vi kan holde styr på vores fremskridt ved at krydse elementerne med en til sløjfe og fjern den aktuelle, hvis den matcher:

ugyldig removeAll (Liste liste, int element) {for (int i = 0; i <liste.størrelse (); i ++) {hvis (Objects.equals (element, list.get (i))) {list.remove (i ); }}}

Det fungerer som forventet:

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

Men hvis vi prøver det med en anden input, giver det en forkert output:

// givet liste liste = liste (1, 1, 2, 3); int valueToRemove = 1; // når removeAll (liste, valueToRemove); // derefter assertThat (liste) .isEqualTo (liste (1, 2, 3));

Lad os analysere, hvordan koden fungerer trin for trin:

  • i = 0
    • element og list.get (i) begge er lig med 1 på linje 3, så Java kommer ind i kroppen af hvis udmelding,
    • vi fjerner elementet ved indeks 0,
    • liste indeholder nu 1, 2 og 3
  • i = 1
    • list.get (i) vender tilbage 2 fordi når vi fjerner et element fra en Liste, det skifter alle igangværende elementer til mindre indekser

Så vi står over for dette problem, når vi har to tilstødende værdier, som vi vil fjerne. For at løse dette skal vi opretholde loop-variablen.

Mindsker det, når vi fjerner elementet:

ugyldig removeAll (Liste liste, int element) {for (int i = 0; i <liste.størrelse (); i ++) {hvis (Objects.equals (element, list.get (i))) {list.remove (i ); jeg--; }}}

Forøgelse kun 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) ; } andet {i ++; }}}

Bemærk, at i sidstnævnte fjernede vi erklæringen i ++ ved linje 2.

Begge løsninger fungerer som forventet:

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

Denne implementering ser ud til at være rigtig ved første øjekast. Det har det dog stadig gjort alvorlige ydeevne problemer:

  • fjernelse af et element fra en ArrayList, skifter alle varer efter det
  • adgang til elementer efter indeks i en LinkedList betyder at krydse gennem elementerne en efter en, indtil vi finder indekset

4. Brug af en for hver Sløjfe

Siden Java 5 kan vi bruge for hver løkke for at gentage gennem en Liste. Lad os bruge det til at fjerne elementer:

ugyldig removeAll (Liste liste, int element) {for (Heltal nummer: liste) {hvis (Objects.equals (nummer, element)) {list.remove (nummer); }}}

Bemærk, at vi bruger Heltal som loop-variabelens type. Derfor får vi ikke en NullPointerException.

Også på denne måde påberåber vi os List.remove (E-element), som forventer den værdi, vi vil fjerne, ikke indekset.

Så rent som det ser ud, desværre fungerer det ikke:

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

Det for hver loop bruger Iterator at krydse gennem elementerne. Imidlertid, når vi ændrer Liste, det Iterator kommer i en inkonsekvent tilstand. Derfor kaster det ConcurrentModificationException.

Lektionen er: vi bør ikke ændre en Liste, mens vi får adgang til dets elementer i en for hver løkke.

5. Brug af en Iterator

Vi kan bruge Iterator direkte for at krydse og ændre Liste med det:

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

Denne måde, det Iterator kan spore tilstanden af Liste (fordi det foretager ændringen). Som et resultat fungerer ovenstående kode som forventet:

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

Siden hver Liste klasse kan give deres egne Iterator implementering, kan vi med sikkerhed antage, at det implementerer elementkørsel og fjernelse af den mest effektive måde.

Brug dog ArrayList betyder stadig masser af elementskift (og måske array-allokering). Koden ovenfor er også lidt sværere at læse, fordi den adskiller sig fra standarden til loop, som de fleste udviklere er fortrolige med.

6. Indsamling

Indtil dette ændrede vi originalen Liste objekt ved at fjerne de ting, vi ikke havde brug for. Det kan vi snarere oprette en ny Liste og saml de genstande, vi vil beholde:

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

Da vi leverer resultatet i et nyt Liste objekt, skal vi returnere det fra metoden. Derfor er vi nødt til at bruge metoden på en anden måde:

// givet Listeliste = liste (1, 1, 2, 3); int valueToRemove = 1; // når Listresultat = removeAll (liste, valueToRemove); // derefter assertThat (resultat) .isEqualTo (liste (2, 3));

Bemærk, at vi nu kan bruge for hver loop, da vi ikke ændrer Liste vi gentager i øjeblikket igennem.

Da der ikke er nogen fjernelser, er der ingen grund til at flytte elementerne. Derfor fungerer denne implementering godt, når vi bruger en ArrayList.

Denne implementering opfører sig anderledes på nogle måder end de tidligere:

  • det ændrer ikke originalen Liste men returnerer et nyt en
  • metoden bestemmer, hvad der returneres Liste'S implementering er, det kan være anderledes end originalen

Vi kan også ændre vores implementering til få den gamle adfærd; vi rydder originalen Liste og tilføj de indsamlede elementer til det:

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

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

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

Da vi ikke ændrer Liste kontinuerligt behøver vi ikke at få adgang til elementer efter position eller skifte dem. Der er også kun to mulige array-allokeringer: når vi ringer List.clear () og List.addAll ().

7. Brug af Stream API

Java 8 introducerede lambda-udtryk og stream-API. Med disse kraftfulde funktioner kan vi løse vores problem med en meget ren kode:

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

Denne løsning fungerer på samme måde, som når vi samlede de resterende elementer.

Som et resultat har den de samme egenskaber, og vi skal bruge det til at returnere resultatet:

// givet Listeliste = liste (1, 1, 2, 3); int valueToRemove = 1; // når Listresultat = removeAll (liste, valueToRemove); // derefter assertThat (resultat) .isEqualTo (liste (2, 3));

Bemærk, at vi kan konvertere det til at fungere som de andre løsninger med den samme tilgang, som vi gjorde med den oprindelige 'indsamling' implementering.

8. Brug fjerneHvis

Med lambdas og funktionelle grænseflader introducerede Java 8 også nogle API-udvidelser. F.eks List.removeIf () metode, som implementerer det, vi så i det sidste afsnit.

Det forventer en Prædikat, som skal vende tilbage rigtigt når vi vil fjerne elementet i modsætning til det foregående eksempel, hvor vi var nødt til at vende tilbage rigtigt da vi ønskede at beholde elementet:

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

Det fungerer som de andre løsninger ovenfor:

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

På grund af det faktum, at Liste selv implementerer denne metode, kan vi med sikkerhed antage, at den har den bedste ydeevne til rådighed. Oven i det giver denne løsning den reneste kode af alle.

9. Konklusion

I denne artikel så vi mange måder at løse et simpelt problem, herunder forkerte. Vi analyserede dem for at finde den bedste løsning til ethvert scenario.

Som sædvanligt er eksemplerne tilgængelige på GitHub.