Távolítsa el egy adott érték minden előfordulását a listáról
1. Bemutatkozás
A Java-ban egyszerű egy adott érték eltávolítása az a-ból Lista felhasználásával List.remove (). Azonban, hatékonyan eltávolítja az érték minden előfordulását sokkal nehezebb.
Ebben az oktatóanyagban több megoldást fogunk látni erre a problémára, ismertetve az előnyöket és hátrányokat.
Az olvashatóság érdekében szokást használunk lista (int…) módszer a tesztekben, amely egy Tömb lista mely elemeket elhaladtuk.
2. Használja a míg Hurok
Mivel tudjuk, hogyan kell távolítson el egyetlen elemet, ciklusban ismételten elvégezve elég egyszerűnek tűnik:
void removeAll (List list, int element) {while (list.contains (element)) {list.remove (element); }}
Ez azonban nem a várt módon működik:
// megadott Lista lista = lista (1, 2, 3); int értékToRemove = 1; // when assertThatThrownBy (() -> removeAll (list, valueToRemove)) .isInstanceOf (IndexOutOfBoundsException.class);
A probléma a 3. sorban van: hívunk List.remove (int), amely az argumentumát indexként kezeli, nem pedig az eltávolítani kívánt értéket.
A fenti tesztben mindig hívunk list.remove (1), de az elem indexe, amelyet el akarunk távolítani, az 0. Hívás List.remove () az eltávolított elem után az összes elemet kisebb indexekre tolja.
Ebben a forgatókönyvben azt jelenti, hogy az első kivételével minden elemet törölünk.
Ha csak az első marad, az index 1 törvényellenes lesz. Ezért kapunk egy Kivétel.
Ne feledje, hogy csak akkor nézünk szembe ezzel a problémával, ha hívunk List.remove () egy primitívvel byte, rövid, char vagy int argumentum, mivel az első dolog, amit a fordító tesz, amikor megpróbálja megtalálni a megfelelő túlterhelt metódust, szélesedik.
Korrigálhatjuk, ha az értéket átadjuk Egész szám:
void removeAll (Lista lista, Egész elem) {while (list.contains (element)) {list.remove (element); }}
Most a kód a várt módon működik:
// megadott Lista lista = lista (1, 2, 3); int értékToRemove = 1; // when removeAll (list, valueToRemove); // majd assertThat (lista) .isEqualTo (lista (2, 3));
Mivel List.contains () és List.remove () mindkettőnek meg kell találnia az elem első előfordulását, ez a kód felesleges elemjárást okoz.
Jobban tehetünk, ha tároljuk az első előfordulás indexét:
void removeAll (Lista lista, Egész elem) {int index; while ((index = list.indexOf (elem))> = 0) {list.remove (index); }}
Ellenőrizhetjük, hogy működik-e:
// megadott Lista lista = lista (1, 2, 3); int értékToRemove = 1; // when removeAll (list, valueToRemove); // majd assertThat (lista) .isEqualTo (lista (2, 3));
Míg ezek a megoldások rövid és tiszta kódot hoznak létre, még mindig gyenge a teljesítményük: mert nem követjük nyomon a haladást, List.remove () meg kell találnia a megadott érték első előfordulását annak törléséhez.
Továbbá, amikor egy Tömb lista, az elemeltolás sok referencia másolást okozhat, akár többször is átcsoportosíthatja a háttér tömböt.
3. Eltávolítás, amíg a Lista Változtatások
List.remove (E elem) van egy olyan jellemzője, amelyet még nem említettünk: ez visszatér a logikai érték, ami igaz ha a Lista a művelet miatt megváltozott, ezért tartalmazta az elemet.
Vegye figyelembe, hogy List.remove (int index) érvénytelen, mert ha a megadott index érvényes, akkor a Lista mindig eltávolítja. Ellenkező esetben dob IndexOutOfBoundsException.
Ezzel eltávolításokat hajthatunk végre a Lista változtatások:
void removeAll (List list, int elem) {while (list.remove (element)); }
A várakozásoknak megfelelően működik:
// adott Lista lista = lista (1, 1, 2, 3); int értékToRemove = 1; // when removeAll (list, valueToRemove); // majd assertThat (lista) .isEqualTo (lista (2, 3));
Annak ellenére, hogy rövid, ennek a megvalósításnak ugyanazok a problémái vannak, mint az előző szakaszban.
3. Használja a mert Hurok
Nyomon követhetjük fejlődésünket, ha végigjárjuk az elemeket a-val mert hurok, és távolítsa el az aktuálisat, ha megfelel:
void removeAll (List list, int element) {for (int i = 0; i <list.size (); i ++) {if (Objects.equals (element, list.get (i))) {list.remove (i ); }}}
A várakozásoknak megfelelően működik:
// megadott Lista lista = lista (1, 2, 3); int értékToRemove = 1; // when removeAll (list, valueToRemove); // majd assertThat (lista) .isEqualTo (lista (2, 3));
Ha azonban más bemenettel próbáljuk ki, akkor helytelen kimenetet ad:
// adott Lista lista = lista (1, 1, 2, 3); int értékToRemove = 1; // when removeAll (list, valueToRemove); // majd assertThat (lista) .isEqualTo (lista (1, 2, 3));
Vizsgáljuk meg lépésről lépésre a kód működését:
- i = 0
- elem és list.get (i) mindkettő egyenlő 1 a 3. sorban, így a Java belép a ha nyilatkozat,
- eltávolítjuk az elemet az indexnél 0,
- így lista most tartalmazza 1, 2 és 3
- i = 1
- list.get (i) visszatér 2 mivel amikor eltávolítunk egy elemet a Lista, az összes folyamatot kisebb indexekre tereli
Tehát akkor szembesülünk ezzel a problémával két szomszédos értékünk van, amelyeket el akarunk távolítani. Ennek megoldásához fenn kell tartanunk a ciklusváltozót.
Csökkentése az elem eltávolításakor:
void removeAll (List list, int element) {for (int i = 0; i <list.size (); i ++) {if (Objects.equals (element, list.get (i))) {list.remove (i ); én--; }}}
Csak akkor növeli, ha nem távolítjuk el az elemet:
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 ++; }}}
Ne feledje, hogy az utóbbiban eltávolítottuk az állítást i ++ a 2. vonalon.
Mindkét megoldás a várakozásoknak megfelelően működik:
// megadott Lista lista = lista (1, 1, 2, 3); int értékToRemove = 1; // when removeAll (list, valueToRemove); // majd assertThat (lista) .isEqualTo (lista (2, 3));
Ez a megvalósítás első látásra helyesnek tűnik. Mégis van komoly teljesítményproblémák:
- elem eltávolítása az Tömb lista, az összes elemet eltolja utána
- elemekhez való hozzáférés index alapján a LinkedList azt jelenti, hogy egyenként haladunk az elemeken, amíg meg nem találjuk az indexet
4. A az egyes Hurok
A Java 5 óta használhatjuk a az egyes hurok iterálni a Lista. Használjuk az elemek eltávolításához:
void removeAll (Lista lista, int elem) {for (Egész szám: lista) {if (Objektumok.egyenlő (szám, elem)) {list.remove (szám); }}}
Ne feledje, hogy használjuk Egész szám mint a ciklusváltozó típusa. Ezért nem kapunk egy NullPointerException.
Továbbá, így hivatkozunk List.remove (E elem), amely az eltávolítani kívánt értéket várja, nem pedig az indexet.
Bármennyire is tiszta, sajnos nem működik:
// adott Lista lista = lista (1, 1, 2, 3); int értékToRemove = 1; // when assertThatThrownBy (() -> removeWithForEachLoop (list, valueToRemove)) .isInstanceOf (ConcurrentModificationException.class);
A az egyes hurok használ Iterátor hogy áthaladjon az elemeken. Azonban, amikor módosítjuk a Lista, a Iterátor következetlen állapotba kerül. Ezért dob ConcurrentModificationException.
A tanulság: nem szabad módosítanunk a Lista, miközben elemeihez hozzáférünk a az egyes hurok.
5. A Iterátor
Használhatjuk a Iterátor közvetlenül átmenni és módosítani a Lista ezzel:
void removeAll (Lista lista, int elem) {for (Iterator i = list.iterator (); i.hasNext ();) {Egész szám = i.next (); if (Objektumok.egyenlő (szám, elem)) {i.remove (); }}}
Ily módon, a Iterátor nyomon tudja követni a Lista (mert elvégzi a módosítást). Ennek eredményeként a fenti kód a várt módon működik:
// adott Lista lista = lista (1, 1, 2, 3); int értékToRemove = 1; // when removeAll (list, valueToRemove); // majd assertThat (lista) .isEqualTo (lista (2, 3));
Mivel minden Lista osztály biztosíthatja a sajátját Iterátor megvalósítását nyugodtan feltételezhetjük a lehető leghatékonyabban valósítja meg az elemek bejárását és eltávolítását.
Azonban felhasználva Tömb lista még mindig sok elemváltást jelent (és talán tömbök átcsoportosítása). Ezenkívül a fenti kód kissé nehezebben olvasható, mert eltér a szabványtól mert loop, amelyet a legtöbb fejlesztő ismer.
6. Gyűjtés
Addig módosítottuk az eredetit Lista objektum eltávolításával a nem szükséges elemeket. Inkább tehetjük újat csinálni Lista és gyűjtsük össze a megtartani kívánt tárgyakat:
Lista removeAll (Lista lista, int elem) {Lista megmaradt Elemek = új ArrayList (); mert (Egész szám: lista) {if (! Objects.equals (szám, elem)) {fennmaradóElementek.add (szám); }} return leftElements; }
Mivel egy új eredményt adunk Lista objektum, vissza kell adnunk a metódusból. Ezért a módszert más módon kell használnunk:
// megadott Lista lista = lista (1, 1, 2, 3); int értékToRemove = 1; // amikor a List eredmény = removeAll (list, valueToRemove); // majd assertThat (eredmény) .isEqualTo (lista (2, 3));
Ne feledje, hogy most már használhatjuk a az egyes ciklus, mivel nem módosítjuk a Lista jelenleg iterálunk.
Mivel nincs eltávolítás, nincs szükség az elemek áthelyezésére. Ezért ez a megvalósítás jól teljesít, ha egy Tömb lista.
Ez a megvalósítás bizonyos szempontból eltérően viselkedik, mint a korábbiak:
- nem módosítja az eredetit Lista de egy újat ad vissza egy
- a módszer eldönti, hogy mit adott vissza Lista’Végrehajtása az, eltérhet az eredetitől
Emellett módosíthatjuk megvalósításunkat a kapja meg a régi viselkedést; kitisztítjuk az eredetit Lista és adja hozzá az összegyűjtött elemeket:
void removeAll (Lista lista, int elem) {Lista megmaradt Elemek = új ArrayList (); mert (Egész szám: lista) {if (! Objects.equals (szám, elem)) {fennmaradóElementek.add (szám); }} list.clear (); list.addAll (többiElement); }
Ugyanúgy működik, mint korábban:
// adott Lista lista = lista (1, 1, 2, 3); int értékToRemove = 1; // when removeAll (list, valueToRemove); // majd assertThat (lista) .isEqualTo (lista (2, 3));
Mivel nem módosítjuk a Lista folytonosan nem kell helyenként hozzáférnünk az elemekhez, és nem kell elmozdítanunk őket. Ezenkívül csak két lehetséges tömb átcsoportosítás lehetséges: amikor hívunk List.clear () és List.addAll ().
7. A Stream API használata
A Java 8 bevezette a lambda kifejezéseket és a stream API-t. Ezekkel az erőteljes funkciókkal nagyon tiszta kóddal tudjuk megoldani a problémánkat:
Lista removeAll (Lista lista, int elem) {return list.stream () .filter (e ->! Objects.equals (e, element)) .collect (Collectors.toList ()); }
Ez a megoldás ugyanúgy működik, mint amikor a maradék elemeket gyűjtöttük.
Ennek eredményeként ugyanazokkal a tulajdonságokkal rendelkezik, és az eredmény visszaadásához használnunk kell:
// adott Lista lista = lista (1, 1, 2, 3); int értékToRemove = 1; // amikor a List eredmény = removeAll (list, valueToRemove); // majd assertThat (eredmény) .isEqualTo (lista (2, 3));
Ne feledje, hogy átalakíthatjuk úgy, hogy a többi megoldáshoz hasonlóan működjön, az eredeti „gyűjtő” megvalósítással megegyező megközelítéssel.
8. Használata removeIf
A lambdas és a funkcionális interfészek segítségével a Java 8 néhány API kiterjesztést is bevezetett. Például a List.removeIf () módszer, amely megvalósítja az utolsó szakaszban látottakat.
Arra számít, hogy a Állítmány, amelynek vissza kellene térnie igaz amikor el akarjuk távolítani az elem, szemben az előző példával, ahová vissza kellett térnünk igaz amikor meg akartuk tartani az elemet:
void removeAll (Lista lista, int elem) {list.removeIf (n -> Objects.equals (n, element)); }
Úgy működik, mint a fenti megoldások:
// adott Lista lista = lista (1, 1, 2, 3); int értékToRemove = 1; // when removeAll (list, valueToRemove); // majd assertThat (lista) .isEqualTo (lista (2, 3));
Annak a ténynek köszönhetően, hogy a Lista maga alkalmazza ezt a módszert, nyugodtan feltételezhetjük, hogy az elérhető legjobb teljesítményt nyújtja. Ráadásul ez a megoldás biztosítja a legtisztább kódot.
9. Következtetés
Ebben a cikkben sokféle megoldást láttunk egy egyszerű probléma megoldására, beleértve a helytelen problémákat is. Elemeztük őket, hogy megtaláljuk a legjobb megoldást minden forgatókönyvre.
Szokás szerint a példák elérhetők a GitHub oldalon.