java - El método HashSet<T>.removeAll es sorprendentemente lento

java set api 8

Question

Jon Skeet recientemente planteó un interesante tema de programación en su blog: "Hay un agujero en mi abstracción, querida Liza, querida Liza" (énfasis agregado):

Tengo un conjunto, un HashSet , de hecho. Quiero eliminar algunos elementos de él ... y muchos de los elementos pueden no existir. De hecho, en nuestro caso de prueba, ninguno de los elementos de la colección de "eliminaciones" estará en el conjunto original. Esto suena, y de hecho es , extremadamente fácil de codificar. Después de todo, tenemos Set<T>.removeAll para ayudarnos, ¿verdad?

Especificamos el tamaño del conjunto "fuente" y el tamaño de la colección "eliminaciones" en la línea de comando, y construimos ambos. El conjunto fuente contiene solo enteros no negativos; el conjunto de eliminaciones contiene solo enteros negativos. Medimos cuánto tiempo lleva eliminar todos los elementos usando System.currentTimeMillis() , que no es el cronómetro más preciso del mundo pero es más que adecuado en este caso, como verá. Aquí está el código:

import java.util.*;
public class Test 
{ 
    public static void main(String[] args) 
    { 
       int sourceSize = Integer.parseInt(args[0]); 
       int removalsSize = Integer.parseInt(args[1]); 

       Set<Integer> source = new HashSet<Integer>(); 
       Collection<Integer> removals = new ArrayList<Integer>(); 

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

Comencemos dándole un trabajo fácil: un conjunto de origen de 100 elementos y 100 para eliminar:

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

Bien, entonces no esperábamos que fuera lento ... claramente podemos acelerar un poco las cosas. ¿Qué tal una fuente de un millón de artículos y 300,000 artículos para eliminar?

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

Hmm Eso todavía parece bastante rápido. Ahora siento que he sido un poco cruel, pidiéndole que elimine todo eso. Hagámoslo un poco más fácil: 300,000 elementos de origen y 300,000 eliminaciones:

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

¿Perdóneme? ¿Casi tres minutos ? ¡Ay! ¿Seguramente debería ser más fácil eliminar elementos de una colección más pequeña que la que administramos en 38 ms?

¿Alguien puede explicar por qué sucede esto? ¿Por qué el HashSet<T>.removeAll es tan lento?

Answer 1

El comportamiento está (algo) documentado en el javadoc :

Esta implementación determina cuál es el más pequeño de este conjunto y la colección especificada, invocando el método de tamaño en cada uno. Si este conjunto tiene menos elementos , la implementación itera sobre este conjunto, verificando cada elemento devuelto por el iterador para ver si está contenido en la colección especificada . Si está contenido, se elimina de este conjunto con el método remove del iterador. Si la colección especificada tiene menos elementos, la implementación itera sobre la colección especificada, eliminando de este conjunto cada elemento devuelto por el iterador, utilizando el método remove de este conjunto.

Lo que esto significa en la práctica, cuando llama a source.removeAll(removals); :

• Si la colección de removals es de un tamaño menor que la source , se llama al método de HashSet de HashSet , que es rápido.

• si la colección de removals es de igual o mayor tamaño que la source , se llama a removals.contains , que es lento para una ArrayList.

Arreglo rapido:

Collection<Integer> removals = new HashSet<Integer>();

Tenga en cuenta que hay JDK-6982173 que es muy similar a lo que describe. La conclusión parece ser que probablemente sea una mala elección, pero no se puede cambiar porque está documentado en el javadoc.

Como referencia, este es el código de removeAll (en Java 8, no he verificado otras versiones):

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