Метод HashSet <T>.removeAll на удивление медленный

Джон Скит недавно поднял интересную тему программирования в своем блоге: "В моей абстракции есть дыра, дорогая Лиза, дорогая Лиза" (выделение добавлено):

У меня есть набор - HashSet, на самом деле. Я хочу удалить некоторые элементы из него... и многие элементы могут не существовать. Фактически, в нашем тестовом примере ни один из элементов в коллекции "пересылок" не будет в исходном наборе. Это звучит - и действительно - чрезвычайно легко кодировать. В конце концов, мы получили Set<T>.removeAll чтобы помочь нам, верно?

Мы указываем размер набора "source" и размер коллекции "removeals" в командной строке и собираем их оба. Исходный набор содержит только неотрицательные целые числа; набор удалений содержит только отрицательные целые числа. Мы измеряем, сколько времени требуется, чтобы удалить все элементы, используя System.currentTimeMillis(), которая не является самым точным секундомером в мире, но более чем адекватна в этом случае, как вы увидите. Вот код:
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"); 
    }
}
Давайте начнем с простой работы: исходный набор из 100 элементов и 100 для удаления:
c:UsersJonTest>java Test 100 100
Time taken: 1ms
Итак, мы не ожидали, что это будет медленно... очевидно, мы можем немного ускорить процесс. Как насчет источника одного миллиона предметов и 300 000 предметов для удаления?
c:UsersJonTest>java Test 1000000 300000
Time taken: 38ms
Хм. Это все еще кажется довольно быстрым. Теперь я чувствую себя немного жестоко, прося, чтобы он сделал все это, удаляя. Давайте сделаем это немного проще - 300 000 исходных предметов и 300 000 удалений:
c:UsersJonTest>java Test 300000 300000
Time taken: 178131ms
Извините меня? Почти три минуты? Хлоп! Конечно, должно быть легче удалить предметы из меньшей коллекции, чем та, которой мы управляли за 38 мс?

Может кто-нибудь объяснить, почему это происходит? Почему метод HashSet<T>.removeAll такой медленный?

Ответ 1

Поведение (несколько) описано в javadoc:

Эта реализация определяет, какая из них меньше этого набора и указанная коллекция, путем вызова метода размера для каждого из них. Если этот набор имеет меньше элементов, реализация выполняет итерацию по этому набору, проверяя каждый элемент, возвращаемый итератором, в свою очередь, чтобы увидеть , если он содержится в указанной коллекции. Если он содержится в нем, он удаляется из этого набора с помощью метода удаления итератора. Если указанная коллекция имеет меньшее количество элементов, то реализация выполняет итерацию по указанной коллекции, удаляя из этого набора каждый элемент, возвращаемый итератором, используя этот метод удаления.

Что это означает на практике, когда вы вызываете source.removeAll(removals);:

если коллекция removals имеет меньший размер, чем source, вызывается метод remove HashSet, который является быстрым.
если коллекция removals имеет равный или больший размер, чем source, тогда вызывается removals.contains, что является медленным для ArrayList.

Быстрое исправление:

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

Обратите внимание, что есть открытая ошибка, которая очень похожа на то, что вы описываете. Суть в том, что это, вероятно, плохой выбор, но не может быть изменен, поскольку он задокументирован в javadoc.

Для справки, это код removeAll (в Java 8 - не проверял другие версии):

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