У меня есть маленький вопрос о деталях реализации, который я не понимаю в ArrayList::removeIf. Я не думаю, что я могу просто сказать так, как есть, без каких-либо предварительных условий.
Таким образом: реализация в основном представляет собой объем remove, в отличие от ArrayList::remove. Пример должен сделать вещи намного проще для понимания. Допустим, у меня есть этот список:
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);
И я хотел бы удалить каждый элемент, который является четным. Я мог бы сделать:
Iterator<Integer> iter = list.iterator();
while (iter.hasNext()) {
int elem = iter.next();
if (elem % 2 == 0) {
iter.remove();
}
}
Или :
list.removeIf(x -> x % 2 == 0);
Результат будет таким же, но реализация будет отличаться. Поскольку iterator является представлением ArrayList, каждый раз, когда я вызываю remove, базовый ArrayList должен быть приведен в "хорошее" состояние, означающее, что внутренний массив фактически изменится. Опять же, при каждом отдельном вызове remove будут внутренние вызовы System::arrayCopy.
На контрасте removeIf умнее. Поскольку он выполняет итерацию внутри, он может сделать вещи более оптимизированными. То, как это происходит, интересно.
Сначала вычисляются индексы, из которых элементы должны быть удалены. Для этого сначала вычисляется крошечный BitSet, массив значений long, где в каждом индексе находится значение 64 bit (long). Несколько значений 64 bit делают это BitSet. Чтобы установить значение с определенным смещением, сначала нужно найти индекс в массиве, а затем установить соответствующий бит. Это не очень сложно. Допустим, вы хотите установить биты 65 и 3. Сначала нам нужен long [] l = new long[2] (потому что мы вышли за пределы 64 бит, но не более 128):
|0...(60 more bits here)...000|0...(60 more bits here)...000|
Сначала вы найдете индекс: 65 / 64 (на самом деле они делают 65 >> 6), а затем в этом индексе (1) ставят необходимый бит:
1L << 65 // this will "jump" the first 64 bits, so this will actually become 00000...10.
То же самое для 3. Таким образом, длинный массив станет:
|0...(60 more bits here)...010|0...(60 more bits here)...1000|
В исходном коде они называют этот BitSet - deathRow (красивое имя!).
Давайте рассмотрим пример even здесь, где list = 2, 4, 6, 5, 5
- они повторяют массив и вычисляют это
deathRow (где Predicate::test равно true).
deathRow = 7 (000 ... 111)
означает, что индексы = [0, 1, 2] должны быть удалены
- теперь они заменяют элементы в базовом массиве на основе этот deathRow (не вдаваясь в детали, как это делается)
, внутренний массив становится: [5, 5, 6, 5, 5]. В основном они перемещают элементы, которые должны оставаться перед массивом.
Я, наконец, могу задать вопрос.
На данный момент они знают:
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
Для меня здесь есть один шаг:
void getRidOfElementsFromWToEnd() {
for(int i=w; i<end; ++i){
es[i] = null;
}
size = w;
}
Вместо этого это происходит:
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;
}
Я специально переименовал переменные здесь.
Какой смысл звонить:
System.arraycopy(es, end, es, w, size - end);
Особенно size - end, поскольку end - это size все время - оно никогда не меняется (так что всегда zero). Это в основном NO-OP здесь. В каком угловом случае я здесь скучаю?