c# - initialize - hashset.net core




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

Il y a deux problèmes de performance 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 ponctuel nécessite environ 3720 collections, mais que le test de chaîne ne nécessite que ~ 18 collections. Pas gratuitement. Quand vous voyez un type de valeur induire autant de collections, alors vous devez conclure "euh-oh, trop de boxe".

Le problème est que HashSet<T> besoin d'un IEqualityComparer<T> pour effectuer son travail. Puisque vous n'en avez pas fourni, il doit être remplacé par celui renvoyé par EqualityComparer.Default<T>() . Cette méthode peut faire du bon travail avec string, elle implémente IEquatable. Mais pas pour Point, c’est un type qui évoque .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 de GetHashCode.

Vous pouvez résoudre ces 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, battant facilement le test des cordes.

Je voulais stocker des emplacements de pixels sans permettre 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 comparé à 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.

Bien que le code suivant (qui n'est pas un bon choix pour des raisons évidentes) ne prenne 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, c'est beaucoup plus que les chiffres indiqués dans cette réponse.
  • Existe-t-il un meilleur moyen de stocker des points sans doublons?

La raison principale de la baisse de performance 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 à Equals(object obj) ce qui augmente le nombre de conversions de boxe.

Notez également que le code de hachage de Point est calculé par x ^ y . Cela produit très peu de dispersion dans votre plage de données et donc les HashSet du HashSet sont surpeuplés - ce qui n’arrive pas avec string , où la dispersion des hachages est beaucoup plus grande.

Vous pouvez résoudre ce problème en implémentant votre propre structure Point (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 .







hashset