[C#] HashSet <Point>가 HashSet <string>보다 너무 느린 이유는 무엇입니까?

C# / 글쓴이

중복을 허용하지 않고 일부 픽셀 위치를 저장하고 싶었으므로 가장 먼저 생각해야 할 것은 HashSet<Point>비슷한 클래스입니다. 그러나 이것은 같은 것에 비해 매우 느린 것 같습니다 HashSet<string>.

예를 들어이 코드는 다음과 같습니다.

HashSet<Point> points = new HashSet<Point>();
using (Bitmap img = new Bitmap(1000, 1000))
{
    for (int x = 0; x < img.Width; x++)
    {
        for (int y = 0; y < img.Height; y++)
        {
            points.Add(new Point(x, y));
        }
    }
}

약 22.5 초가 걸립니다.

다음 코드 (명백한 이유로 좋은 선택이 아님) 는 1.6 초 밖에 걸리지 않습니다.

HashSet<string> points = new HashSet<string>();
using (Bitmap img = new Bitmap(1000, 1000))
{
    for (int x = 0; x < img.Width; x++)
    {
        for (int y = 0; y < img.Height; y++)
        {
            points.Add(x + "," + y);
        }
    }
}

그래서 내 질문은 :

  • 그 이유가 있습니까? 이 답변을 확인 했지만 22.5 초는 해당 답변에 표시된 숫자보다 훨씬 큽니다.
  • 중복없이 포인트를 저장하는 더 좋은 방법이 있습니까?

답변

Point 구조체로 인해 두 가지 성능 문제가 발생합니다. Console.WriteLine(GC.CollectionCount(0));테스트 코드에 추가 할 때 볼 수있는 것 . 포인트 테스트에는 ~ 3720 모음이 필요하지만 문자열 테스트에는 ~ 18 모음 만 필요하다는 것을 알 수 있습니다. 무료가 아닙니다. 값 유형이 너무 많은 컬렉션을 유도하면 “아, 너무 복싱”이라고 결론을 내릴 필요가 있습니다.

문제는 작업을 완료 HashSet<T>해야한다는 IEqualityComparer<T>것입니다. 하나를 제공하지 않았으므로에 의해 반환 된 것으로 대체해야합니다 EqualityComparer.Default<T>(). 이 방법은 문자열에 좋은 일을 할 수 있으며 IEquatable을 구현합니다. 그러나 Point가 아니라 .NET 1.0에서 시작하여 제네릭 사랑을 얻지 못한 유형입니다. Object 메소드 만 사용하면됩니다.

다른 문제는 Point.GetHashCode ()가이 테스트에서 별다른 작업을 수행하지 않으며 너무 많은 충돌이 발생하므로 Object.Equals ()를 상당히 많이 망치는 것입니다. String은 훌륭한 GetHashCode 구현을 가지고 있습니다.

좋은 비교기를 HashSet에 제공하면 두 가지 문제를 모두 해결할 수 있습니다. 이 같은:

class PointComparer : IEqualityComparer<Point> {
    public bool Equals(Point x, Point y) {
        return x.X == y.X && x.Y == y.Y;
    }

    public int GetHashCode(Point obj) {
        // Perfect hash for practical bitmaps, their width/height is never >= 65536
        return (obj.Y << 16) ^ obj.X;
    }
}

그리고 그것을 사용하십시오 :

HashSet<Point> list = new HashSet<Point>(new PointComparer());

이제는 약 150 배 더 빨라져서 쉽게 문자열 테스트를 이길 수 있습니다.

답변

성능 저하의 주된 이유는 모든 권투가 계속되고 있기 때문입니다 ( Hans Passant의 답변 ).

그 외에도 해시 코드 알고리즘은 더 많은 호출을 유발하기 때문에 문제를 악화시킵니다. Equals(object obj) 권투 변환의 양이 증가 .

또한 의 해시 코드는Point 에 의해 계산됩니다 x ^ y. 이로 인해 데이터 범위에서 분산이 거의 HashSet발생하지 않으므로 string해시 분산이 훨씬 큰 버킷 이 과도하게 채워집니다.

자신의 Point구조체 (사소한) 를 구현 하고 예를 들어 좌표를 이동하여 예상 데이터 범위에 대해 더 나은 해시 알고리즘을 사용하여 문제를 해결할 수 있습니다 .

(x << 16) ^ y

해시 코드와 관련하여 좋은 조언을 얻으 려면 주제에 대한 Eric Lippert의 블로그 게시물을 읽으십시오 .

답변