removeIf détail d'implémentation

9

J'ai une petite question de détail d'implémentation que je n'arrive pas à comprendre ArrayList::removeIf. Je ne pense pas que je puisse simplement le dire tel qu'il est sans certaines conditions préalables.

En tant que tel: l'implémentation est fondamentalement un volume remove , contrairement à ArrayList::remove. Un exemple devrait rendre les choses beaucoup plus faciles à comprendre. Disons que j'ai cette liste:

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

Et je voudrais supprimer tous les éléments qui sont pairs. Je pourrais faire:

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

Le résultat sera le même, mais la mise en œuvre est très différente. Étant donné que le iteratorest une vue de la ArrayList, chaque fois que j'appelle remove, le sous-jacent ArrayListdoit être amené à un "bon" état, ce qui signifie que le tableau interne va réellement changer. Encore une fois, à chaque appel de remove, il y aura des appels en System::arrayCopyinterne.

Sur le contraste, removeIfc'est plus intelligent. Puisqu'il fait l'itération en interne, il peut rendre les choses plus optimisées. La façon dont cela se fait est intéressante.

Il calcule d'abord les index d'où les éléments sont censés être supprimés. Cela se fait en calculant d'abord un minuscule BitSet, un tableau de longvaleurs où à chaque index, réside une 64 bitvaleur (a long). Plusieurs 64 bitvaleurs en font un BitSet. Pour définir une valeur à un décalage particulier, vous devez d'abord trouver l'index dans le tableau, puis définir le bit correspondant. Ce n'est pas très compliqué. Disons que vous voulez définir les bits 65 et 3. Tout d'abord, nous avons besoin d'un long [] l = new long[2](car nous sommes allés au-delà de 64 bits, mais pas plus de 128):

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

Vous trouvez d'abord l'index: 65 / 64(ils le font en fait 65 >> 6) puis dans cet index ( 1) mettez le bit nécessaire:

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

Même chose pour 3. En tant que tel, ce long tableau deviendra:

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

Dans le code source, ils appellent ce BitSet - deathRow(joli nom!).

Prenons cet evenexemple ici, oùlist = 2, 4, 6, 5, 5

  • ils itèrent le tableau et le calculent deathRow(où Predicate::testest true).

deathRow = 7 (000 ... 111)

les indices de signification = [0, 1, 2] doivent être supprimés

  • ils remplacent désormais les éléments du tableau sous-jacent en fonction de ce deathRow (sans entrer dans les détails sur la façon de procéder)

tableau intérieur devient: [5, 5, 6, 5, 5]. Fondamentalement, ils déplacent les éléments qui sont censés rester devant le tableau.

Je peux enfin poser la question.

À ce stade, ils savent:

 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

Pour moi, il y a une seule étape à faire ici:

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

Au lieu de cela, cela se produit:

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

J'ai renommé les variables à dessein ici.

Quel est l'intérêt d'appeler:

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

Surtout size - end, puisque end c'est size tout le temps - il n'est jamais changé (donc c'est toujours zero). Il s'agit essentiellement d'un NO-OP ici. Quel étui d'angle me manque ici?

java java-8 iterator Eugène
la source
2
Je viens de perdre une demi-journée à comprendre ces détails, et c'est tellement évident, cette méthode est également utilisée dans d' autres endroits. Je suis un idiot: |
Eugene
Honnêtement, vous m'avez laissé confus. Votre question portait-elle sur l'utilisation de System.arraycopy(es, end, es, w, size - end)comme détails d'implémentation sous-jacents removeIf? J'avais presque l'impression de lire une réponse à une autre question entre les deux. (En lisant le commentaire ci-dessus) Je sens que cela a finalement abouti à une question banale. Est-ce vrai?
Naman
@Naman exactement, c'était à ce sujet redouté System.arrayCopy. Néanmoins, ce fut un voyage amusant à travers les détails (cet ensemble de bits interne s'avère avoir la même idée que java.util.BitSet)
Eugene
@Naman si vous le souhaitez, vous pouvez fournir une réponse lorsque ce n'est pas un NOOP (indice: range...) et je l'accepterai.
Eugene
1
@Eugene en Java 8, il utilise java.util.BitSet. Pour moi, la réimplémentation des BitSetopérations ne semble pas beaucoup mieux que l'original. L'occasion de sauter des mots entiers a été manquée.
Holger

Réponses:

6

Vous examinez le cas spécifique (commun) où la liste, que vous invoquez removeIf, est la même que la ArrayList. Seulement dans ce cas, vous pouvez supposer que endc'est toujours égal à size.

Un contre-exemple serait:

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

De même, removeAllappellera shiftTailOverGapavec un endargument qui peut différer de celui sizeappliqué à a subList.

Une situation similaire se produit lorsque vous appelez clear(). Dans ce cas, l'opération réelle, effectuée lors de son appel sur elle- ArrayListmême, est si triviale qu'elle n'appelle même pas la shiftTailOverGapméthode. Seulement lorsque vous utilisez quelque chose comme l.subList(a, b).clear(), il va finir à removeRange(a, b)sur l, qui à son tour, comme vous avez déjà trouvé vous - même, Invoke shiftTailOverGap(elementData, a, b)avec bqui peut être inférieure size.

Holger
la source