HashSet.removeAll 메서드가 놀라울 정도로 느리다.

HashSet.removeAll 메서드가 놀라울 정도로 느리다.

Jon Sket은 최근 블로그에서 흥미로운 프로그래밍 토픽을 제기했습니다. "내 추상화에 구멍이 있어, 사랑하는 라이자, 사랑하는 라이자" (강조 추가):

세트가 있습니다.HashSet,실은.일부 아이템을 삭제하고 싶은데 많은 아이템이 존재하지 않을 수 있습니다.실제로 테스트 케이스에서는 "제거" 컬렉션에 포함된 아이템은 원래 세트에 포함되지 않습니다.이것은 매우 쉽게 코드화할 수 있는 것처럼 들립니다.결국, 우리는 우리를 도와야 해요, 그렇죠?

명령줄에서 "source" 세트의 크기와 "removals" 컬렉션의 크기를 지정하여 둘 다 구축합니다.소스 세트에는 음수가 아닌 정수만 포함되며 제거 세트에는 음수 정수만 포함됩니다.모든 요소를 제거하는 데 걸리는 시간을 측정합니다.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만 아이템의 소스와 제거할 아이템 30만 아이템의 소스는 어떻습니까?

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

음, 그래도 꽤 빠른 것 같네요지금 나는 내가 그 모든 것을 제거해달라고 부탁하는 것이 좀 잔인했다고 느낀다.좀 더 쉽게 설명합시다.30,000개의 소스 아이템과 300,000개의 삭제:

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

네? 뭐라고요?거의 3분?이런! 우리가 38ms에 관리했던 것보다 적은 컬렉션에서 아이템을 삭제하는 것이 더 쉬울 것 같은데?

누가 왜 이런 일이 일어나는지 설명해 줄 수 있나요?왜?HashSet<T>.removeAll방법이 너무 느려요?

동작은 javadoc에 기재되어 있습니다.

이 실장에서는 이 세트와 지정된 컬렉션 중 어떤 것이 작은지 각각에 대해 size 메서드를 호출하여 판별합니다.이 세트에 포함되는 요소가 적은 경우, 이 세트에 대해서 실장이 반복되어 지정된 컬렉션에 포함되어 있는지를 확인하기 위해서, 반복자에 의해서 반환되는 각 요소가 차례로 체크됩니다.포함된 경우 반복자 제거 방법으로 이 세트에서 제거됩니다.지정된 컬렉션에 포함된 요소가 적은 경우 구현은 지정된 컬렉션에 걸쳐 반복되며 이 세트의 제거 메서드를 사용하여 반복자가 반환하는 각 요소를 이 세트에서 제거합니다.

「 」라고 하는 은, 「 」라고 의 의미입니다.source.removeAll(removals);

• removals가 컬션 collect collect source , . . . . . . . .remove의 of의 HashSet이치노

• removals컬렉션은 같은 크기 또는 더 큰 크기입니다.source , , , 「 」removals.contains가 호출됩니다.「Array List(어레이 리스트)」를 참조.

빠른 수정:

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

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