удалить если деталь реализации

9

У меня есть небольшой вопрос о реализации, который я не могу понять в 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значение (a 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 здесь. В каком угловом случае я здесь скучаю?

java java-8 iterator Евгений
источник
2
Я просто потратил половину дня на понимание этих деталей, и это настолько очевидно, что этот метод используется и в других местах. Я идиот: |
Евгений
Честно говоря, вы оставили меня в замешательстве. Был ли ваш вопрос об использовании в System.arraycopy(es, end, es, w, size - end)качестве основных деталей реализации removeIf? Я почти чувствовал, что я читал ответ на какой-то другой вопрос между ними. (Читая комментарий выше) Я чувствую, что в конечном итоге он оказался в тривиальном вопросе. Это так?
Наман
@ Точно, Наман, это было страшно System.arrayCopy. Тем не менее, это было забавное путешествие через детали (этот внутренний набор битов имеет ту же идею, что и java.util.BitSet)
Евгений
@ Наман, если хочешь, можешь дать ответ, где это не NOOP (подсказка: range...), и я приму его.
Евгений
1
@ Евгений в Java 8, он использует java.util.BitSet. Для меня повторная реализация BitSetопераций не выглядит значительно лучше, чем оригинал. Возможность пропустить целые слова была упущена.
Хольгер

Ответы:

6

Вы смотрите на конкретный (общий) случай, когда список, к которому вы обращаетесь removeIf, совпадает с ArrayList. Только в этом случае можно предположить, что endвсегда равноsize .

Контрпримером будет:

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

Аналогично, removeAllвызовет shiftTailOverGapс endаргументом, который может отличаться от sizeтого, который применяется кsubList .

Похожая ситуация возникает при звонке clear(). В этом случае фактическая операция, выполняемая при вызове ее ArrayListсамой, настолько тривиальна, что она даже не вызывает shiftTailOverGapметод. Только при использовании что - то подобное l.subList(a, b).clear(), это будет в конечном итоге на removeRange(a, b)на l, что, в свою очередь, как вы уже выяснили сами, вызывайте shiftTailOverGap(elementData, a, b)с bкоторой может быть меньше size.

Holger
источник