왜 HashSet인가

왜 HashSet인가 HashSet보다 훨씬 느리다?

---

중복을 허용하지 않고 일부 픽셀 위치를 저장하고 싶었으므로 가장 먼저 생각해야 할 것은 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)권투 변환의 양이 증가 하기 때문에 문제를 악화시킵니다 .

Also note that the hash code of Point is computed by x ^ y. This produces very little dispersion in your data range, and therefore the buckets of the HashSet are overpopulated — something that doesn't happen with string, where the dispersion of the hashes is much larger.

You can solve that problem by implementing your own Point struct (trivial) and using a better hash algorithm for your expected data range, e.g. by shifting the coordinates:

(x << 16) ^ y

For some good advice when it comes to hash codes, read Eric Lippert's blog post on the subject.

참고URL : https://stackoverflow.com/questions/46142734/why-is-hashsetpoint-so-much-slower-than-hashsetstring