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

我想存储一些像素位置，不允许重复，所以第一件事就是 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);
}
}
}

所以，我的问题是:

  • 有什么原因吗？我查了 这个答案，但是22.5秒比答案中显示的数字要多得多。
  • 有没有更好的方法来存储没有重复的点？
11741 次浏览
小开

性能下降的主要原因是正在进行的所有装箱操作(正如在 汉斯 · 帕桑特的答案中已经解释的那样)。

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

还要注意，Point的哈希码是由 x ^ y计算的。这在您的数据范围内产生的分散性非常小，因此 HashSet的存储桶被过度填充了，这种情况在 string中不会发生，因为在 string中散列的分散性要大得多。

你可以通过实现你自己的 Point结构来解决这个问题(琐碎的) ，并且为你期望的数据范围使用一个更好的哈希算法，例如通过移动坐标:

(x << 16) ^ y

有关散列码的一些好建议，请阅读 埃里克 · 利伯特关于这个话题的博客文章。

小开
最佳答案

由 Point 结构引起的性能问题有两个。在将 Console.WriteLine(GC.CollectionCount(0));添加到测试代码时可以看到的内容。您将看到 Point 测试需要约3720个集合，而字符串测试只需要约18个集合。不是免费的。当您看到一个值类型导致如此多的集合时，您需要总结“啊哦，太多的装箱”。

问题是 HashSet<T>需要一个 IEqualityComparer<T>来完成它的工作。因为您没有提供一个，所以它需要返回到由 EqualityComparer.Default<T>()返回的一个。该方法可以很好地处理字符串，它实现了 IEquable。但对 Point 来说不是这样，它是一种。NET 1.0，从来没有得到泛型的爱。它所能做的就是使用 Object 方法。

另一个问题是 Point。GetHashCode ()在这个测试中没有完成一个恒星的工作，太多的碰撞，所以它锤击对象。等于()相当严重。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倍，轻而易举地击败了弦乐测试。


提交答案