La méthode HashSet removeAll est étonnamment lente

J’ai un ensemble – un HashSet Je veux en supprimer certains éléments – aucun des éléments de la collection “removals” ne se trouvera dans le jeu d’origine.

Je spécifie la taille de l’ensemble “source” et la taille de la collection “removals” sur la ligne de commande, et je les construis tous les deux. L’ensemble source ne contient que des entiers non négatifs; l’ensemble de suppressions ne contient que des entiers négatifs. Je mesure le temps qu’il faut pour supprimer tous les éléments en utilisant System.currentTimeMillis (), qui n’est pas le chronomètre le plus précis au monde, mais qui est plus que suffisant dans ce cas, comme vous le verrez. Voici le code:

import java.util.*; public class Test { public static void main(Ssortingng[] args) { int sourceSize = Integer.parseInt(args[0]); int removalsSize = Integer.parseInt(args[1]); Set source = new HashSet(); Collection removals = new ArrayList(); for (int i = 0; i < sourceSize; i++) { source.add(i); } for (int i = 1; i <= removalsSize; i++) { removals.add(-i); } long start = System.currentTimeMillis(); source.removeAll(removals); long end = System.currentTimeMillis(); System.out.println("Time taken: " + (end – start) + "ms"); } } 

Commençons par lui donner un travail facile: un ensemble de 100 éléments source et 100 pour supprimer:

  c:UsersJonTest>java Test 100 100 Time taken: 1ms 

Ok, c’est rapide comme je m’y attendais.

Ensuite, j’ai essayé la source d’un million d’éléments et 300 000 articles à supprimer?

 c:UsersJonTest>java Test 1000000 300000 Time taken: 38ms 

Cela semble toujours assez rapide. Maintenant, rendez-vous un peu plus facile – 300 000 sources et 300 000 entrées:

 c:UsersJonTest>java Test 300000 300000 Time taken: 178131ms 

Près de trois minutes?

Vraiment confus !! Quelqu’un peut-il expliquer pourquoi cela se produit?

Le comportement est (quelque peu) documenté dans le javadoc :

Cette implémentation détermine quel est le plus petit de cet ensemble et la collection spécifiée, en appelant la méthode de taille sur chacun. Si cet ensemble contient moins d’éléments , l’implémentation effectue une itération sur cet ensemble, vérifiant tour à tour chaque élément renvoyé par l’iterator pour voir s’il est contenu dans la collection spécifiée . S’il est ainsi contenu, il est supprimé de cet ensemble avec la méthode remove de l’iterator. Si la collection spécifiée contient moins d’éléments, l’implémentation effectue une itération sur la collection spécifiée, supprimant de cet ensemble chaque élément renvoyé par l’iterator, en utilisant la méthode remove de cet ensemble.

Qu’est-ce que cela signifie en pratique, lorsque vous appelez source.removeAll(removals); :

  • Si la collection de removals est de taille inférieure à la source , la méthode remove de HashSet est appelée, ce qui est rapide.

  • Si la collection de removals est de taille égale ou supérieure à la source , alors removals.contains est appelée, ce qui est lent pour une ArrayList.

Solution rapide:

 Collection removals = new HashSet(); 

Notez qu’il existe un bogue ouvert très similaire à ce que vous décrivez. L’essentiel semble être que c’est probablement un mauvais choix, mais qu’il ne peut être modifié car il est documenté dans le javadoc.


Pour référence, ceci est le code de removeAll (dans Java 8 – n’a pas vérifié les autres versions):

 public boolean removeAll(Collection c) { Objects.requireNonNull(c); boolean modified = false; if (size() > c.size()) { for (Iterator i = c.iterator(); i.hasNext(); ) modified |= remove(i.next()); } else { for (Iterator i = iterator(); i.hasNext(); ) { if (c.contains(i.next())) { i.remove(); modified = true; } } } return modified; }