我想存储一些像素位置而不允许重复,所以首先想到的是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); } } }
所以,我的问题是:
Point 结构引发了两个性能问题。Console.WriteLine(GC.CollectionCount(0));添加到测试代码时可以看到的内容。您会看到 Point 测试需要 ~3720 个集合,但字符串测试只需要 ~18 个集合。不是免费的。当您看到一个值类型引发了如此多的集合时,您需要得出结论“呃,哦,太多的装箱”。
Console.WriteLine(GC.CollectionCount(0));
问题是HashSet<T>需要一个IEqualityComparer<T>来完成它的工作。由于您没有提供一个,它需要回退到由EqualityComparer.Default<T>(). 该方法可以很好地处理字符串,它实现了 IEquatable。但不适用于 Point,它是一种来自 .NET 1.0 的类型,并且从未得到泛型的喜爱。它所能做的就是使用 Object 方法。
HashSet<T>
IEqualityComparer<T>
EqualityComparer.Default<T>()
另一个问题是 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 倍,轻松击败了字符串测试。