首页 文章

为什么HashSet <Point>比HashSet <string>慢得多？

提问于
浏览 次
159

我想存储一些像素位置而不允许重复，所以首先想到的是 HashSet<Point> 或类似的类 . 然而，与 HashSet<string> 相比，这似乎非常缓慢 .

例如，这段代码：

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

大约需要22.5秒 .

虽然以下代码（由于显而易见的原因不是一个好的选择）只需1.6秒：

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

So, my questions are:

  • 有这样的理由吗？我检查了this answer，但22.5秒比那个答案中显示的数字多 .

  • 有没有更好的方法来存储没有重复的点？

c# .net performance collections hashset

2 回答

  • 281

    Point结构引发了两个性能问题 . 将 Console.WriteLine(GC.CollectionCount(0)); 添加到测试代码时可以看到的内容 . 您会看到Point测试需要~3720个集合，但字符串测试只需要~18个集合 . 不是免费的 . 当您看到值类型导致如此多的集合时，您需要得出结论"uh-oh, too much boxing" .

    问题是 HashSet<T> 需要一个 IEqualityComparer<T> 来完成它的工作 . 由于你没有提供一个，它需要回退到 EqualityComparer.Default<T>() 返回的一个 . 该方法可以很好地完成字符串，它实现了IEquatable . 但不是Point，它是一种类似于.NET 1.0的类型，从来没有得到泛型的爱 . 它所能做的只是使用Object方法 .

    另一个问题是Point.GetHashCode（）在这个测试中没有做太多的工作，碰撞太多，所以它对Object.Equals（）非常重要 . String具有出色的GetHashCode实现 .

    您可以通过为HashSet提供一个好的比较器来解决这两个问题 . 像这个：

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

    并使用它：

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

    它现在大约快150倍，轻松击败字符串测试 .

    回复于
  • 86

    性能下降的主要原因是拳击正在进行（如Hans Passant's答案中已经解释的那样） .

    除此之外，哈希码算法会使问题恶化，因为它会导致更多的调用 Equals(object obj) ，从而增加了拳击转换的数量 .

    另请注意the hash code of Point由 x ^ y 计算 . 这会在您的数据范围内产生非常小的色散，因此 HashSet 的存储桶过多 - 这种情况在 string 中不会发生，其中散列的散射要大得多 .

    您可以通过实现自己的 Point 结构（平凡）并使用更好的哈希算法来解决该问题，例如预期的数据范围，例如：通过移动坐标：

    (x << 16) ^ y

    有关哈希码的一些好建议，请阅读Eric Lippert's blog post on the subject .

    回复于

相关问题