removeIf detalle de implementación

9

Tengo una pequeña pregunta detallada de implementación que no puedo entender ArrayList::removeIf. No creo que pueda decirlo simplemente sin algunas condiciones previas.

Como tal: la implementación es básicamente masiva remove , a diferencia ArrayList::remove. Un ejemplo debería hacer las cosas mucho más fáciles de entender. Digamos que tengo 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);

Y me gustaría eliminar cada elemento que sea par. Yo podría hacer:

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

O :

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

El resultado será el mismo, pero la implementación es muy diferente. Dado que iteratores una vista de ArrayList, cada vez que llamo remove, el subyacente ArrayListtiene que ser llevado a un estado "bueno", lo que significa que la matriz interna realmente cambiará. Nuevamente, en cada llamada de remove, habrá llamadas System::arrayCopyinternas.

En el contraste removeIfes más inteligente. Como realiza la iteración internamente, puede hacer las cosas más optimizadas. La forma en que lo hace es interesante.

Primero calcula los índices de los que se supone que deben eliminarse los elementos. Esto se hace calculando primero una pequeña BitSet, una matriz de longvalores donde en cada índice reside un 64 bitvalor (a long). Múltiples 64 bitvalores hacen esto a BitSet. Para establecer un valor en un desplazamiento particular, primero necesita encontrar el índice en la matriz y luego establecer el bit correspondiente. Esto no es muy complicado. Digamos que desea establecer el bit 65 y 3. Primero necesitamos un long [] l = new long[2](porque fuimos más allá de 64 bits, pero no más de 128):

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

Primero encuentra el índice: 65 / 64(en realidad lo hacen 65 >> 6) y luego en ese índice ( 1) ponga el bit necesario:

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

Lo mismo para 3. Como tal, ese conjunto largo se convertirá en:

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

En el código fuente lo llaman BitSet - deathRow(¡buen nombre!).

Tomemos ese evenejemplo aquí, dondelist = 2, 4, 6, 5, 5

  • iteran la matriz y calculan esto deathRow(donde Predicate::testestá true).

deathRow = 7 (000 ... 111)

los índices de significado = [0, 1, 2] deben eliminarse

  • ahora reemplazan elementos en la matriz subyacente en función de ese DeathRow (sin entrar en detalles sobre cómo se hace)

matriz interna se convierte en: [5, 5, 6, 5, 5]. Básicamente, mueven los elementos que se supone que permanecen delante de la matriz.

Finalmente puedo traer la pregunta.

En este momento, ellos saben:

 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 mí, hay un solo paso para hacer aquí:

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

En cambio, esto sucede:

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

He cambiado el nombre de las variables a propósito aquí.

¿Cuál es el punto en llamar:

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

Especialmente size - end, ya que end es size todo el tiempo, nunca se cambia (por lo que esto es siempre zero). Esto es básicamente un NO-OP aquí. ¿Qué caso de esquina me estoy perdiendo aquí?

java java-8 iterator Eugene
fuente
2
Acabo de perder 1/2 día entendiendo estos detalles, y esto es tan obvio que este método también se usa en otros lugares. Soy un idiota: |
Eugene
Honestamente, me dejaste confundido. ¿Fue su pregunta sobre el uso de System.arraycopy(es, end, es, w, size - end)los detalles de implementación subyacentes removeIf? Casi sentí que estaba leyendo una respuesta a alguna otra pregunta en el medio. (Leyendo el comentario anterior) Siento que finalmente terminó en una pregunta trivial. ¿Es eso así?
Naman
@Naman exactamente, se trataba de eso temido System.arrayCopy. Sin embargo, fue un viaje divertido a través de los detalles (ese conjunto de bits internos resulta tener la misma idea que java.util.BitSet)
Eugene
@Naman si lo desea, puede proporcionar una respuesta donde eso no es un NOOP (pista: range...) y lo aceptaré.
Eugene
1
@Eugene en Java 8, sí utiliza java.util.BitSet. Para mí, la reimplementación de las BitSetoperaciones no se ve significativamente mejor que la original. Se ha perdido la oportunidad de saltear palabras enteras.
Holger

Respuestas:

6

Estás viendo el caso específico (común) en el que la lista, que llamas removeIf, es la misma que ArrayList. Solo en este caso, puede asumir que endsiempre es igual a size.

Un contraejemplo sería:

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

Del mismo modo, removeAllllamará shiftTailOverGapcon un endargumento que puede diferir de sizecuando se aplica a subList.

Una situación similar surge cuando llamas clear(). En ese caso, la operación real, realizada cuando se llama en ArrayListsí misma, es tan trivial que ni siquiera llama al shiftTailOverGapmétodo. Solo cuando se usa algo así l.subList(a, b).clear(), terminará removeRange(a, b)encendido l, lo que a su vez, como ya lo descubrió, invocará shiftTailOverGap(elementData, a, b)con un bque puede ser más pequeño que size.

Holger
fuente