mvc - hashset vs dictionary c#

¿Por qué HashSet<Point> es mucho más lento que HashSet<string>?

Question

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.

Si bien el siguiente código (que no es una buena opción por razones obvias) solo lleva 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 alguna razón para eso? Verifiqué esta respuesta , pero 22.5 segundos es mucho más que los números que se muestran en esa respuesta.
• ¿Hay una mejor manera de almacenar puntos sin duplicados?

Answer 1

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

El problema es que HashSet<T> necesita un IEqualityComparer<T> para hacer su trabajo. Como no proporcionó uno, debe recurrir a uno devuelto por EqualityComparer.Default<T>() . Ese método puede hacer un buen trabajo para la cadena, implementa IEquatable. Pero no para Point, es un tipo que se inspira en .NET 1.0 y nunca recibió el amor genérico. Todo lo que puede hacer es usar los métodos Object.

El otro problema es que Point.GetHashCode () no hace un trabajo estelar en esta prueba, demasiadas colisiones, por lo que martilla bastante Object.Equals (). String tiene una excelente implementación de GetHashCode.

Puede resolver ambos problemas proporcionando al HashSet un buen comparador. Como éste:

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 cuerda.

Answer 2

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

Además de eso, el algoritmo de código hash empeora el problema, porque causa más llamadas a Equals(object obj) lo que aumenta 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 del HashSet están superpoblados, algo que no sucede con la 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 obtener buenos consejos cuando se trata de códigos hash, lea la publicación de blog de Eric Lippert sobre el tema .