Почему HashSet <Point> намного медленнее, чем HashSet <string>?

Я хотел сохранить некоторые пиксельные местоположения, не допуская дублирования, поэтому первое, что приходит на ум, - это 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));тестовый код. Вы увидите, что для теста Point требуется ~ 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 раз быстрее, легко обгоняя тест строки.

Основная причина снижения производительности - все происходящее в боксе (как уже объяснялось в ответе Ханса Пассанта ).

Кроме того, алгоритм хеш-кода усугубляет проблему, потому что он вызывает больше вызовов, Equals(object obj)тем самым увеличивая количество преобразований в бокс.

Также обратите внимание, что хэш-кодPoint вычисляется как x ^ y. Это приводит к очень небольшому разбросу в вашем диапазоне данных, и, следовательно, блоки HashSetпереполнены - то, чего не происходит string, где разброс хэшей намного больше.

Вы можете решить эту проблему, реализовав собственную Pointструктуру (тривиальную) и используя лучший алгоритм хеширования для ожидаемого диапазона данных, например, смещая координаты:

(x << 16) ^ y

Чтобы получить полезные советы по хэш-кодам, прочитайте сообщение Эрика Липперта в блоге на эту тему .