HashSet

HashSet.removeAll 메서드가 놀랍도록 느립니다.

---

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);다음과 같습니다.

• if the removals collection is of a smaller size than source, the remove method of HashSet is called, which is fast.

• if the removals collection is of equal or larger size than the source, then removals.contains is called, which is slow for an ArrayList.

Quick fix:

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

Note that there is an open bug that is very similar to what you describe. The bottom line seems to be that it is probably a poor choice but can't be changed because it is documented in the javadoc.

---

For reference, this is the code of removeAll (in Java 8 - haven't checked other 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;
}

참고URL : https://stackoverflow.com/questions/28671903/the-hashsett-removeall-method-is-surprisingly-slow