[java] HashSet <T> .removeAll 메서드는 놀랍도록 느립니다.

Program / 글쓴이

Jon Skeet은 최근 자신의 블로그에서 흥미로운 프로그래밍 주제를 제기했습니다. “추상화에 구멍이 있습니다 . Liza에게, Liza에게” (강조 추가됨) :

나는 세트가있다 – HashSet사실. 일부 항목을 제거하고 싶습니다… 많은 항목이 존재하지 않을 수 있습니다. 사실, 우리의 테스트 케이스에, 아무도 은 “제거”컬렉션의 항목의 원래 세트에 없습니다. 이 소리 – 참하고 있습니다 매우 쉽게 코드 -. 결국 우리는 우리 Set<T>.removeAll를 도와야합니다, 그렇죠?

명령 줄에서 “소스”집합의 크기와 “제거”컬렉션의 크기를 지정하고 둘 다 빌드합니다. 소스 세트에는 음이 아닌 정수만 포함됩니다. 제거 세트에는 음의 정수만 포함됩니다. 를 사용하여 모든 요소를 ​​제거하는 데 걸리는 시간을 측정합니다. 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

좋아요, 그래서 우리는 속도가 느릴 것이라고 예상하지 못했습니다. 분명히 우리는 조금씩 증가시킬 수 있습니다. 100 만 개의 항목과 300,000 개의 항목을 제거해야하는 소스는 어떻습니까?

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

흠. 여전히 꽤 빠른 것 같습니다. 이제는 내가 조금 잔인하다고 느낍니다. 모든 제거 작업을 요청합니다. 좀 더 쉽게 만들어 보겠습니다. 소스 항목 300,000 개 및 제거 300,000 개 :

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

실례합니다? 거의 3 분 ? 이런! 38ms에서 관리 한 것보다 작은 컬렉션 에서 항목을 제거하는 것이 더 쉬울 까요?

누군가 이것이 왜 일어나는지 설명 할 수 있습니까? HashSet<T>.removeAll방법 이 왜 그렇게 느린가요?

답변

동작은 (다소) javadoc에 문서화되어 있습니다 .

이 구현은 각각에 대해 size 메서드를 호출하여이 집합과 지정된 컬렉션 중 더 작은 것을 결정합니다. 이 집합에 더 적은 요소가있는 경우 구현은이 집합을 반복하여 반복기가 반환 한 각 요소를 차례로 확인 하여 지정된 컬렉션에 포함되어 있는지 확인합니다 . 포함 된 경우 반복기의 remove 메서드를 사용하여이 집합에서 제거됩니다. 지정된 컬렉션에 더 적은 수의 요소가있는 경우 구현은 지정된 컬렉션을 반복하여이 집합의 remove 메서드를 사용하여이 집합에서 반환 된 각 요소를 제거합니다.

이것이 실제로 의미하는 바는 source.removeAll(removals);다음과 같습니다.

  • 경우 생성 removals컬렉션은보다 작은 크기 인 source상기 remove의 방법은 HashSet빠른 불린다.

  • 경우 생성 removals회수가 같거나 더 큰 크기이다 source후 removals.containsArrayList를 느린 인 불린다.

빠른 수정:

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

답변