Pourquoi HashSet <Point> est-il tellement plus lent que HashSet <string>?

165

Je voulais stocker certains emplacements de pixels sans autoriser les doublons, donc la première chose qui me vient à l'esprit est HashSet<Point>ou des classes similaires. Cependant, cela semble être très lent par rapport à quelque chose comme HashSet<string>.

Par exemple, ce code:

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

prend environ 22,5 secondes.

Alors que le code suivant (qui n'est pas un bon choix pour des raisons évidentes) ne prend que 1,6 seconde:

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

Donc, mes questions sont:

  • Y at-il une raison à cela? J'ai vérifié cette réponse , mais 22,5 secondes est bien plus que les chiffres indiqués dans cette réponse.
  • Existe-t-il une meilleure façon de stocker des points sans doublons?
Ahmed Abdelhameed
la source
Quelles sont ces «raisons évidentes» pour ne pas utiliser de chaînes concaténées? Quelle est la meilleure façon de le faire si je ne veux pas implémenter mon propre IEqualityComparer?
Ivan Yurchenko

Réponses:

290

Il y a deux problèmes de perf induits par la structure Point. Quelque chose que vous pouvez voir lorsque vous ajoutez Console.WriteLine(GC.CollectionCount(0));au code de test. Vous verrez que le test Point nécessite ~ 3720 collections, mais le test de chaîne n'a besoin que d'environ 18 collections. Pas gratuitement. Quand vous voyez un type de valeur induire autant de collections, vous devez conclure "euh-oh, trop de boxe".

Le problème est qu'il a HashSet<T>besoin d'un IEqualityComparer<T>pour faire son travail. Puisque vous n'en avez pas fourni, il doit revenir à celui renvoyé par EqualityComparer.Default<T>(). Cette méthode peut faire du bon travail pour la chaîne, elle implémente IEquatable. Mais pas pour Point, c'est un type qui provient de .NET 1.0 et n'a jamais eu l'amour des génériques. Tout ce qu'il peut faire est d'utiliser les méthodes Object.

L'autre problème est que Point.GetHashCode () ne fait pas un travail stellaire dans ce test, trop de collisions, donc il martèle Object.Equals () assez lourdement. String a une excellente implémentation GetHashCode.

Vous pouvez résoudre les deux problèmes en fournissant au HashSet un bon comparateur. Comme celui-ci:

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

Et utilisez-le:

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

Et il est maintenant environ 150 fois plus rapide, surpassant facilement le test des cordes.

Hans Passant
la source
26
+1 pour la mise en œuvre de la méthode GetHashCode. Juste par curiosité, comment en êtes-vous arrivé à une obj.X << 16 | obj.Y;mise en œuvre particulière .
Akash KC du
32
Il a été inspiré par la façon dont la souris passe sa position dans les fenêtres. C'est un hachage parfait pour tout bitmap que vous voudriez afficher.
Hans Passant le
2
Il est bon de savoir que. Une documentation ou une meilleure directive pour écrire un hashcode comme le vôtre? En fait, j'aimerais toujours savoir si le hashcode ci-dessus vient avec votre expérience ou toute directive que vous suivez.
Akash KC
5
@AkashKC Je n'ai pas beaucoup d'expérience avec C # mais pour autant que je sache, les entiers sont généralement 32 bits. Dans ce cas, vous voulez le hachage de 2 nombres et en décalant un 16 bits vers la gauche, vous vous assurez que les 16 bits «inférieurs» de chaque nombre n'affectent pas l'autre avec |. Pour 3 nombres, il pourrait être judicieux d'utiliser 22 et 11 comme décalage. Pour 4 numéros, ce serait 24, 16, 8. Cependant, il y aura encore des collisions, mais seulement si les nombres deviennent grands. Mais cela dépend aussi de manière cruciale de la HashSetmise en œuvre. S'il utilise l'adressage ouvert avec "troncature de bits" (je ne pense pas que ce soit le cas!), L'approche de décalage à gauche pourrait être mauvaise.
MSeifert
3
@HansPassant: Je me demande si utiliser XOR plutôt que OR dans GetHashCode pourrait être légèrement meilleur - dans le cas où les coordonnées de point pourraient dépasser 16 bits (peut-être pas sur les écrans courants, mais dans un avenir proche). // XOR est généralement meilleur dans les fonctions de hachage que OR, car il perd moins d'informations, est inversé, etc. // par exemple si les coordonnées négatives sont autorisées, considérez ce qui arrive à la contribution X si Y est négatif.
Krazy Glew
85

La principale raison de la baisse des performances est toute la boxe en cours (comme déjà expliqué dans la réponse de Hans Passant ).

En dehors de cela, l'algorithme de code de hachage aggrave le problème, car il provoque plus d'appels pour Equals(object obj)augmenter ainsi le nombre de conversions de boxe.

Notez également que le code de hachage dePoint est calculé par x ^ y. Cela produit très peu de dispersion dans votre plage de données, et par conséquent, les compartiments du HashSetsont surpeuplés - ce qui ne se produit pas avec string, où la dispersion des hachages est beaucoup plus grande.

Vous pouvez résoudre ce problème en implémentant votre propre Pointstruct (trivial) et en utilisant un meilleur algorithme de hachage pour votre plage de données attendue, par exemple en décalant les coordonnées:

(x << 16) ^ y

Pour de bons conseils en matière de codes de hachage, lisez le billet de blog d'Eric Lippert sur le sujet .

Entre
la source
4
En regardant la source de référence de Point, les GetHashCodeperformances: unchecked(x ^ y)alors que pour stringcela, cela semble beaucoup plus compliqué ..
Gilad Green
2
Hmm .. eh bien, pour vérifier si votre hypothèse est correcte, j'ai juste essayé d'utiliser à la HashSet<long>()place, et utilisé list.Add(unchecked(x ^ y));pour ajouter des valeurs au HashSet. C'était en fait encore plus rapide que HashSet<string> (345 ms) . Est-ce quelque peu différent de ce que vous avez décrit?
Ahmed Abdelhameed
4
@AhmedAbdelhameed c'est probablement parce que vous ajoutez beaucoup moins de membres à votre jeu de hachage que vous ne le pensez (encore une fois à cause de l'horrible dispersion de l'algorithme de code de hachage). Quel est le décompte listlorsque vous avez fini de le remplir?
Entre le
4
@AhmedAbdelhameed Votre test est faux. Vous ajoutez les mêmes longs encore et encore, il n'y a donc en fait que quelques éléments que vous insérez. Lors de l'insertion point, le HashSetappellera en interne GetHashCodeet pour chacun de ces points avec le même hashcode, appellera Equalspour déterminer s'il existe déjà
Ofir Winegarten
49
Il n'est pas nécessaire de mettre en œuvre Pointlorsque vous pouvez créer une classe qui implémente IEqualityComparer<Point>et conserve la compatibilité avec d'autres éléments qui fonctionnent Pointtout en bénéficiant de ne pas avoir les pauvres GetHashCodeet de la nécessité de se loger Equals().
Jon Hanna