¿Por qué el HashSet es mucho más lento que el HashSet?

Quería almacenar algunas ubicaciones de píxeles sin permitir duplicados, por lo que lo primero que me viene a la mente es HashSet<Point> o clases similares. Sin embargo, esto parece ser muy lento en comparación con algo como HashSet<string>.

Por ejemplo, este código:

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

Tarda unos 22,5 segundos.

Mientras que el siguiente código (que no es una buena opción por razones obvias) toma solo 1.6 segundos: 

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

Entonces, mis preguntas son:

  • hay una razón ¿por eso? Revisé esta respuesta, pero 22.5 segundos es mucho más que los números mostrados en esa respuesta.
  • ¿Hay una mejor manera de almacenar puntos sin duplicados?
Author: Ahmed Abdelhameed, 2017-09-10
Source

2 answers

Hay dos problemas perf inducidos por la estructura Point. Algo que se puede ver cuando se agrega Console.WriteLine(GC.CollectionCount(0)); al código de prueba. Verás que la prueba de puntos requiere ~3720 colecciones, pero la prueba de cadenas solo necesita ~18 colecciones. No gratis. Cuando ves que un tipo de valor induce tantas colecciones, entonces necesitas concluir "uh-oh, demasiado boxeo".

En cuestión es que HashSet<T> necesita un IEqualityComparer<T> para hacer su trabajo. Dado que no proporcionó uno, debe volver a uno devuelto por EqualityComparer.Default<T>(). Ese método puede hacer un buen trabajo para string, implementa IEquatable. Pero no para el punto, es un tipo que se remonta a. NET 1.0 y nunca consiguió el amor genéricos. Todo lo que puede hacer es usar los métodos Object.

La otra cuestión es ese punto.GetHashCode () no hace un trabajo estelar en esta prueba, demasiadas colisiones, por lo que martillea Object.Es igual a () bastante fuerte. String tiene una excelente implementación de GetHashCode.

Puede resolver ambos problemas proporcionando el HashSet con un buen comparador. Como este:

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

Y úsalo: 

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

Y ahora es aproximadamente 150 veces más rápido, superando fácilmente la prueba de cadenas.

 276
Author: Hans Passant,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-09-13 08:19:05

La razón principal de la caída de rendimiento es todo el boxeo en curso (como ya se explicó en Hans Passant respuesta).

Aparte de eso, el algoritmo de código hash empeora el problema, porque causa más llamadas a Equals(object obj) aumentando así la cantidad de conversiones de boxeo.

También tenga en cuenta que el código hash de Point se calcula por x ^ y. Esto produce muy poca dispersión en su rango de datos, y por lo tanto los cubos de HashSet están superpoblados - algo que no sucede con string, donde la dispersión de los hashes es mucho mayor.

Puede resolver ese problema implementando su propia estructura Point (trivial) y utilizando un mejor algoritmo hash para su rango de datos esperado, por ejemplo, cambiando las coordenadas: 

(x << 16) ^ y

Para algunos buenos consejos cuando se trata de códigos hash, lee La entrada del blog de Eric Lippert sobre el tema.

 86
Author: InBetween,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-09-16 22:22:42