removeIf szczegóły implementacji

9

Mam małe szczegółowe pytanie dotyczące implementacji, w którym nie rozumiem ArrayList::removeIf. Nie sądzę, że mogę po prostu to po prostu przedstawić, tak jak jest, bez pewnych warunków wstępnych.

Jako taki: wdrożenie jest w zasadzie masowe remove , w przeciwieństwie do ArrayList::remove. Przykład powinien znacznie ułatwić zrozumienie. Powiedzmy, że mam tę listę:

List<Integer> list = new ArrayList<>(); // 2, 4, 6, 5, 5
list.add(2);
list.add(4);
list.add(6);
list.add(5);
list.add(5);

I chciałbym usunąć każdy element, który jest parzysty. Mógłbym zrobić:

Iterator<Integer> iter = list.iterator();
while (iter.hasNext()) {
    int elem = iter.next();
    if (elem % 2 == 0) {
         iter.remove();
    }
}

Lub :

list.removeIf(x -> x % 2 == 0);

Wynik będzie taki sam, ale wdrożenie jest bardzo różne. Ponieważ iteratorjest to widok za ArrayListkażdym razem, gdy dzwonię remove, podstawa ArrayListmusi być doprowadzona do „dobrego” stanu, co oznacza, że ​​wewnętrzny układ faktycznie się zmieni. Ponownie, przy każdym pojedynczym wywołaniu removebędą połączenia System::arrayCopywewnętrzne.

W przeciwieństwie do tego removeIfjest mądrzejszy. Ponieważ wykonuje iterację wewnętrznie, może zoptymalizować rzeczy. Sposób, w jaki to robi, jest interesujący.

Najpierw oblicza indeksy, z których elementy powinny zostać usunięte. Odbywa się to poprzez obliczenie najpierw małej BitSet, tablicy longwartości, gdzie przy każdym indeksie znajduje się 64 bitwartość (a long). Wiele 64 bitwartości sprawia, że ​​jest to a BitSet. Aby ustawić wartość dla określonego przesunięcia, najpierw musisz znaleźć indeks w tablicy, a następnie ustawić odpowiedni bit. To nie jest bardzo skomplikowane. Powiedzmy, że chcesz ustawić bit 65 i 3. Najpierw potrzebujemy long [] l = new long[2](ponieważ przekroczyliśmy 64 bity, ale nie więcej niż 128):

|0...(60 more bits here)...000|0...(60 more bits here)...000|

Najpierw znajdziesz indeks: 65 / 64(faktycznie tak robią 65 >> 6), a następnie w tym indeksie ( 1) umieść potrzebny bit:

1L << 65 // this will "jump" the first 64 bits, so this will actually become 00000...10.

To samo dotyczy 3. W ten sposób długa tablica stanie się:

|0...(60 more bits here)...010|0...(60 more bits here)...1000|

W kodzie źródłowym nazywają to BitSet - deathRow(ładna nazwa!).

Weźmy ten evenprzykład tutaj, gdzielist = 2, 4, 6, 5, 5

  • iterują tablicę i obliczają to deathRow(gdzie Predicate::testjest true).

deathRow = 7 (000 ... 111)

czyli indeksy = [0, 1, 2] należy usunąć

  • teraz zastępują elementy w podstawowej tablicy na podstawie tego deathRow (nie wchodząc w szczegóły, jak to się robi)

tablica wewnętrzna staje się: [5, 5, 6, 5, 5]. Zasadniczo poruszają elementy, które powinny pozostać przed tablicą.

Mogę wreszcie zadać pytanie.

W tym momencie wiedzą:

 w   ->  number of elements that have to remain in the list (2)
 es  ->  the array itself ([5, 5, 6, 5, 5])
 end ->  equal to size, never changed

Dla mnie jest tutaj jeden krok:

void getRidOfElementsFromWToEnd() {
    for(int i=w; i<end; ++i){
       es[i] = null;
    }
    size = w;
}

Zamiast tego dzieje się tak:

private void shiftTailOverGap(Object[] es, int w, int end) {
    System.arraycopy(es, end, es, w, size - end);
    for (int to = size, i = (size -= end - w); i < to; i++)
        es[i] = null;
}

Celowo zmieniłem nazwę zmiennych.

Jaki jest sens dzwonienia:

 System.arraycopy(es, end, es, w, size - end);

Zwłaszcza size - end, że end jest size cały czas - nigdy się nie zmienia (więc zawsze tak jest zero). Jest to w zasadzie NO-OP tutaj. Jakiego narożnika tu brakuje?

java java-8 iterator Eugene
źródło
2
Właśnie zmarnowałem 1/2 dnia na zrozumienie tych szczegółów, a to jest tak oczywiste, że ta metoda jest używana również w innych miejscach. Jestem idiotą: |
Eugene
Szczerze mówiąc, wprawiłeś mnie w zakłopotanie. Czy Twoje pytanie dotyczyło wykorzystania System.arraycopy(es, end, es, w, size - end)jako podstawowych szczegółów wdrożenia removeIf? Niemal poczułem, że czytam odpowiedź na jakieś inne pytanie pomiędzy. (Czytając powyższy komentarz) Wydaje mi się, że ostatecznie zadało to trywialne pytanie. Czy tak jest
Naman
@Naman dokładnie, chodziło o to, czego się obawiałem System.arrayCopy. Niemniej jednak była to zabawna podróż przez szczegóły (ten wewnętrzny zestaw bitów okazuje się mieć taki sam pomysł jak java.util.BitSet)
Eugene
@Naman, jeśli chcesz, możesz udzielić odpowiedzi tam, gdzie nie jest to NOOP (wskazówka: range...), a ja ją zaakceptuję.
Eugene
1
@Eugene w Javie 8, używa java.util.BitSet. Dla mnie ponowna realizacja BitSetoperacji nie wygląda znacznie lepiej niż oryginał. Nie udało się pominąć całych słów.
Holger

Odpowiedzi:

6

Patrzysz na konkretny (powszechny) przypadek, w którym wywoływana lista removeIfjest taka sama jak ArrayList. Tylko w tym przypadku możesz założyć, że endzawsze jest równa size.

Przykładem może być:

ArrayList<Integer> l = new ArrayList<>(List.of(1, 2, 3, 4, 5, 6, 7));
l.subList(2, 5).removeIf(i -> i%2 == 1);

Podobnie, removeAllzadzwoni shiftTailOverGapz endargumentem, który może różnić się od sizezastosowania w przypadku subList.

Podobna sytuacja powstaje podczas połączenia clear(). W takim przypadku faktyczna operacja wykonywana podczas wywoływania go ArrayListsama jest tak trywialna, że ​​nawet nie wywołuje shiftTailOverGapmetody. Tylko przy użyciu coś takiego l.subList(a, b).clear(), będzie to skończyć w removeRange(a, b)sprawie l, co z kolei, jak już okazało się, siebie, invoke shiftTailOverGap(elementData, a, b)z bktórego może być mniejsza niż size.

Holger
źródło