为什么这个List 。IndexOf代码比List 和手动比较快得多？

我在这段代码上运行AQTime，我发现.IndexOf需要16％的时间而接近80％的其他部分……他们似乎使用相同的IsEqual和其他例程。 被称为116,000次，插入30,000件物品。 List 对象都没有超过200个元素。 （我可能错误地使用AQTime，我正在研究这个）

class PointD : IEquatable { public double X, Y, Z; bool IEquatable.Equals(PointD other) { return ((X == other.X) && (Y == other.Y) && (Z == other.Z)); } } class PerfTest { readonly List _pCoord3Points = new List(); public int NewPoints; public int TotalPoints; public PerfTest() { NewPoints = 0; TotalPoints = 0; } public int CheckPointIndexOf(PointD pt) { int retIndex = _pCoord3Points.IndexOf(pt); if (retIndex < 0) { _pCoord3Points.Add(pt); NewPoints++; } TotalPoints++; return retIndex; } public int CheckPointForBreak(PointD pt) { int retIndex = -1; for (int i = 0; i < _pCoord3Points.Count; i++) { PointD otherPt = _pCoord3Points[i]; if ((pt.X == otherPt.X) && (pt.Y == otherPt.Y) && (pt.Z == otherPt.Z)) { retIndex = i; break; } } if (retIndex == -1) { NewPoints++; _pCoord3Points.Add(pt); } TotalPoints++; return retIndex; } static void Main() { const int xmax = 300; const int ymax = 10; const int zmax = 10; const int imax = 4; var test = new PerfTest(); //test.Init(); Stopwatch sw = Stopwatch.StartNew(); for (int i = 0; i < imax; i++) { for (int x = 0; x < xmax; x++) { for (int y = 0; y < ymax; y++) { for (int z = 0; z < zmax; z++) { var pt = new PointD { X = x, Y = y, Z = z }; test.CheckPointIndexOf(pt); } } } } sw.Stop(); string output = string.Format("Total: {0:0} New: {1:0} IndexOf: ", test.TotalPoints, test.NewPoints); Console.Write(output); Console.WriteLine(sw.Elapsed); test = new PerfTest(); sw = Stopwatch.StartNew(); for (int i = 0; i < imax; i++) { for (int x = 0; x < xmax; x++) { for (int y = 0; y < ymax; y++) { for (int z = 0; z < zmax; z++) { var pt = new PointD { X = x, Y = y, Z = z }; test.CheckPointForBreak(pt); } } } } sw.Stop(); output = string.Format("Total: {0:0} New: {1:0} PointD[] ", test.TotalPoints, test.NewPoints); Console.Write(output); Console.WriteLine(sw.Elapsed); Console.ReadLine(); } } 

Answer 1

我做了以下假设：

• PointD是一个结构
• IndexOf确实比手动迭代列表慢

您可以通过实现IEquatable接口来加速IndexOf ：

 struct PointD : IEquatable { public int X; public int Y; public int Z; public bool Equals(PointD other) { return (this.X == other.X) && (this.Y == other.Y) && (this.Z == other.Z); } } 

如果不实现IEquatable接口， IndexOf将使用ValueType.Equals(object other)比较两个PointD元素，这涉及昂贵的装箱操作。

IEquatable接口的文档说明：

当在Contains ， IndexOf ， LastIndexOf和Remove等方法中测试相等性时， IEquatable接口由generics集合对象（如Dictionary ， List和LinkedList使用。 它应该针对可能存储在generics集合中的任何对象实现。

这是我完整的基准代码：

 using System; using System.Collections.Generic; using System.Diagnostics; struct PointD { public int X; public int Y; public int Z; } class PerfTest { List _pCoord3Points = new List(); int checkPointIndexOf(PointD pt) { return _pCoord3Points.IndexOf(pt); } int checkPointForBreak(PointD pt) { int retIndex = -1; for (int i = 0; i < _pCoord3Points.Count; i++) { PointD otherPt = _pCoord3Points[i]; if ((pt.X == otherPt.X) && (pt.Y == otherPt.Y) && (pt.Z == otherPt.Z)) retIndex = i; break; } return retIndex; } void init() { for (int x = 0; x < 100; x++) { for (int y = 0; y < 10; y++) { for (int z = 0; z < 10; z++) { PointD pt = new PointD() { X = x, Y = y, Z = z }; _pCoord3Points.Add(pt); } } } } static void Main(string[] args) { PerfTest test = new PerfTest(); test.init(); Stopwatch sw = Stopwatch.StartNew(); for (int x = 0; x < 100; x++) { for (int y = 0; y < 10; y++) { for (int z = 0; z < 10; z++) { PointD pt = new PointD() { X = x, Y = y, Z = z }; test.checkPointIndexOf(pt); } } } sw.Stop(); Console.WriteLine(sw.Elapsed); sw = Stopwatch.StartNew(); for (int x = 0; x < 100; x++) { for (int y = 0; y < 10; y++) { for (int z = 0; z < 10; z++) { PointD pt = new PointD() { X = x, Y = y, Z = z }; test.checkPointForBreak(pt); } } } sw.Stop(); Console.WriteLine(sw.Elapsed); } } 

在Windows 7，x64，.NET 4.0 x64版本上，我得到以下时间（约）：

 IndexOf：00：00：04.8096623
 For Loop：00：00：00.0014203

将PointD转换为class ，时间会变为

 IndexOf：00：00：01.0703627
 For Loop：00：00：00.0014190

当使用实现IEquatable的struct PointD我得到更多“相似”的结果，但IndexOf仍然更慢（现在使用class时没有显着差异）：

 IndexOf：00：00：00.3904615
 For Loop：00：00：00.0015218

Answer 2

通常，在访问数组元素之前，它会检查以确保索引> = 0且

毋庸置疑，如果循环中的代码非常少，则会妨碍性能。 为了减轻这个问题，JIT编译器优化了forms的for (i = 0; i < array.Length; i++) { array[i]; }循环for (i = 0; i < array.Length; i++) { array[i]; } - 即，访问数组的所有索引从0到长度的任何循环 - 1.它省略了对这种情况的边界检查。 （如果您访问array [i + 1]之类的内容，优化将失败，因为您可能会超越边界。）

不幸的是，这仅适用于数组，而不适用于List <>。 所以你的后一个代码不会被优化。

但由于List <>内部包含一个数组，而List.IndexOf（）使用循环直接访问数组中的每个值，因此可以对其进行优化。

顺便说一句，最好说for (int i = 0; i < array.Length; i++) { }不是说int length = array.Length; for(int i = 0; i < length; i++) { } int length = array.Length; for(int i = 0; i < length; i++) { } - 因为它无法确定length真的是数组的长度。

编辑：使用Reflector查看IndexOf代码，循环确实会优化，但正如其他人提到的那样，它调用Equals（） - 这需要vtable查找和各种健全性检查。 因此，在这种情况下，当您没有使用分析器运行时，IndexOf实际上可能会更慢。

反汇编的代码：

 internal virtual int IndexOf(T[] array, T value, int startIndex, int count) { int num = startIndex + count; for (int i = startIndex; i < num; i++) { if (this.Equals(array[i], value)) { return i; } } return -1; } 

Answer 3

_pCoord3Points的类型是_pCoord3Points ？ 如果元素类型是仅覆盖Equals(object)的值类型，那么IndexOf可能会重复装箱值以检查是否相等。 这可能解释了它。 尽管如此，这只是猜测……如果你能提供一个简短但完整的程序来certificate这个问题，那将会更容易帮助你。