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(gdziePredicate::testjesttrue).
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?
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
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)
range...), a ja ją zaakceptuję.
java.util.BitSet. Dla mnie ponowna realizacja BitSetoperacji nie wygląda znacznie lepiej niż oryginał. Nie udało się pominąć całych słów.