detalhe da implementação removeIf

9

Tenho uma pequena pergunta detalhada sobre a implementação que não consigo entender ArrayList::removeIf. Eu não acho que posso simplesmente colocar do jeito que está, sem algumas pré-condições primeiro.

Como tal: a implementação é basicamente em massa remove , ao contrário ArrayList::remove. Um exemplo deve facilitar muito a compreensão das coisas. Digamos que eu tenho esta lista:

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);

E eu gostaria de remover todos os elementos que são iguais. Eu poderia fazer:

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

Ou :

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

O resultado será o mesmo, mas a implementação é muito diferente. Como iteratoré uma visão do ArrayList, toda vez que eu chamo remove, o subjacente ArrayListdeve ser levado a um estado "bom", o que significa que a matriz interna realmente mudará. Novamente, em cada chamada de remove, haverá chamadas System::arrayCopyinternamente.

Pelo contrário, removeIfé mais inteligente. Como faz a iteração internamente, pode tornar as coisas mais otimizadas. A maneira como faz isso é interessante.

Primeiro calcula os índices de onde os elementos devem ser removidos. Isso é feito computando primeiro uma minúscula BitSetmatriz de longvalores em que, em cada índice, reside um 64 bitvalor (a long). Vários 64 bitvalores tornam isso a BitSet. Para definir um valor em um deslocamento específico, primeiro você precisa descobrir o índice na matriz e depois definir o bit correspondente. Isso não é muito complicado. Digamos que você queira definir os bits 65 e 3. Primeiro, precisamos de um long [] l = new long[2](porque fomos além de 64 bits, mas não mais que 128):

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

Você primeiro encontra o índice: 65 / 64(eles realmente o fazem 65 >> 6) e, em seguida, nesse índice ( 1) coloca o bit necessário:

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

A mesma coisa para 3. Como tal, essa matriz longa se tornará:

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

No código fonte, eles chamam isso de BitSet - deathRow(belo nome!).

Vamos pegar esse evenexemplo aqui, ondelist = 2, 4, 6, 5, 5

  • eles iteram a matriz e calculam isso deathRow(onde Predicate::testestá true).

deathRow = 7 (000 ... 111)

índices de significado = [0, 1, 2] devem ser removidos

  • agora eles substituem elementos na matriz subjacente com base nesse deathRow (sem entrar em detalhes como isso é feito)

matriz interna torna-se: [5, 5, 6, 5, 5]. Basicamente, eles movem os elementos que deveriam permanecer na frente da matriz.

Eu posso finalmente trazer a pergunta.

Neste momento, eles sabem:

 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

Para mim, há um único passo a ser feito aqui:

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

Em vez disso, isso acontece:

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;
}

Renomeei as variáveis ​​de propósito aqui.

Qual é o sentido de chamar:

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

Especialmente size - end, já que end é size o tempo todo - nunca é alterado (portanto, é sempre zero). Este é basicamente um NO-OP aqui. Que caso de esquina estou perdendo aqui?

java java-8 iterator Eugene
fonte
2
Acabei de desperdiçar 1/2 dia por entender esses detalhes, e isso é tão óbvio que esse método também é usado em outros lugares. Eu sou um idiota: |
Eugene
Honestamente, você me deixou confusa. Sua pergunta foi sobre o uso de System.arraycopy(es, end, es, w, size - end)como detalhes de implementação subjacentes removeIf? Eu quase senti que estava lendo uma resposta para outra pergunta no meio. (Lendo o comentário acima) Eu sinto que acabou em uma pergunta trivial finalmente. É assim mesmo?
Naman 04/02
@ Naman exatamente, era sobre isso temido System.arrayCopy. Não obstante, foi uma jornada divertida pelos detalhes (esse conjunto de bits interno acaba tendo a mesma idéia java.util.BitSet)
Eugene
@ Naman, se você quiser, pode fornecer uma resposta em que não seja um NOOP (dica: range...) e eu a aceitarei.
Eugene
11
@ Eugene em Java 8, ele usa java.util.BitSet. Para mim, a reimplementação das BitSetoperações não parece significativamente melhor que a original. A oportunidade de pular palavras inteiras foi perdida.
Holger

Respostas:

6

Você está analisando o caso específico (comum) em que a lista, você chama removeIf, é a mesma que a ArrayList. Somente neste caso, você pode assumir que endé sempre igual a size.

Um contra-exemplo seria:

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

Da mesma forma, removeAllchamará shiftTailOverGapcom um endargumento que pode diferir de sizequando aplicado a um subList.

Uma situação semelhante surge quando você liga clear(). Nesse caso, a operação real, executada ao chamá-la por ArrayListsi mesma, é tão trivial que nem chama o shiftTailOverGapmétodo. Somente ao usar algo como l.subList(a, b).clear(), ele terminará removeRange(a, b)em l, que por sua vez, como você já descobriu, invocará shiftTailOverGap(elementData, a, b)com um bque pode ser menor que size.

Holger
fonte