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

165

Quería almacenar algunas ubicaciones de píxeles sin permitir duplicados, por lo que lo primero que me viene a la mente son las HashSet<Point>clases similares. Sin embargo, esto parece ser muy lento en comparación con algo así 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));
        }
    }
}

Toma alrededor de 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?
Ahmed Abdelhameed
fuente
¿Cuáles son estas "razones obvias" para no usar cadenas concatenadas? ¿Cuál es la mejor manera de hacerlo si no quiero implementar mi propio IEqualityComparer?
Ivan Yurchenko

Respuestas:

290

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 veas que un tipo de valor induce tantas colecciones, entonces debes 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 tuvo 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 golpea Object.Equals () bastante fuertemente. 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.

Hans Passant
fuente
26
+1 para proporcionar la implementación del método GetHashCode. Solo por curiosidad, ¿cómo llegaste a una obj.X << 16 | obj.Y;implementación particular ?
Akash KC
32
Se inspiró en la forma en que el mouse pasa su posición en las ventanas. Es un hash perfecto para cualquier mapa de bits que quiera mostrar.
Hans Passant
2
Es bueno saberlo. ¿Alguna documentación o la mejor guía para escribir hashcode como el tuyo? En realidad, todavía me gustaría saber si el código hash anterior viene con tu experiencia o con alguna directriz que sigas.
Akash KC
55
@AkashKC No tengo mucha experiencia con C #, pero que yo sepa, los enteros son generalmente de 32 bits. En este caso, desea el hash de 2 números y al desplazar hacia la izquierda uno de 16 bits, se asegura de que los 16 bits "inferiores" de cada número no "afecten" al otro |. Para 3 números, podría tener sentido usar 22 y 11 como desplazamiento. Para 4 números, sería 24, 16, 8. Sin embargo, todavía habrá colisiones, pero solo si los números aumentan. Pero también depende de manera crucial de la HashSetimplementación. Si usa direccionamiento abierto con "truncamiento de bits" (¡no creo que lo haga!), El enfoque de desplazamiento a la izquierda podría ser malo.
MSeifert
3
@HansPassant: Me pregunto si usar XOR en lugar de OR en GetHashCode podría ser un poco mejor, en el caso de que las coordenadas de los puntos puedan exceder los 16 bits (quizás no en pantallas comunes, sino en un futuro próximo). // XOR suele ser mejor en funciones hash que OR, ya que pierde menos información, es reversibke, etc. // por ejemplo, si se permiten coordenadas negativas, considere qué sucede con la contribución X si Y es negativo.
Krazy Glew
85

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, ya que provoca más llamadas para Equals(object obj)aumentar así la cantidad de conversiones de boxeo.

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

Puede resolver ese problema implementando su propia Pointestructura (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, lea la publicación de blog de Eric Lippert sobre el tema .

Entre
fuente
44
Mirando la fuente de referencia de Point the GetHashCoderealiza: unchecked(x ^ y)mientras que para stringparece mucho más complicado ..
Gilad Green
2
Hmm ... bueno, para verificar si su suposición es correcta, intenté usar en su HashSet<long>()lugar y list.Add(unchecked(x ^ y));agregué valores al HashSet. En realidad, esto fue incluso más rápido que HashSet<string> (345 ms) . ¿Es esto de alguna manera diferente de lo que describiste?
Ahmed Abdelhameed
44
@AhmedAbdelhameed probablemente se deba a que está agregando menos miembros a su conjunto de hash de lo que cree (nuevamente debido a la horrible dispersión del algoritmo de código hash). ¿De qué se trata listcuando hayas terminado de poblarlo?
InBetween
44
@AhmedAbdelhameed Su prueba está mal. Está agregando los mismos largos una y otra vez, por lo que en realidad solo hay algunos elementos que está insertando. Al insertar point, HashSetse llamará internamente GetHashCodey para cada uno de esos puntos con el mismo código hash, se llamará Equalspara determinar si ya existe
Ofir Winegarten
49
No es necesario implementar Pointcuando puede crear una clase que implemente IEqualityComparer<Point>y mantenga la compatibilidad con otras cosas con las que trabaja Pointmientras obtiene el beneficio de no tener a los pobres GetHashCodey la necesidad de encajonar Equals().
Jon Hanna