为什么此列表<>。索引代码比列表[i]和手册比较快得多？
https://stackoverflow.com/questions/3663014
-
01-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我在这件代码上运行AQTime，我发现.indexof的时间的16％，而另一件则接近80％……它们似乎使用了相同的iSequal和其他例程。称为116,000次插入30,000件物品。列表<>对象都没有超过200个元素。 （我可能错误地使用了AQTime，我正在调查）
class PointD : IEquatable<PointD>
{
public double X, Y, Z;
bool IEquatable<PointD>.Equals(PointD other)
{
return ((X == other.X) && (Y == other.Y) && (Z == other.Z));
}
}
class PerfTest
{
readonly List<PointD> _pCoord3Points = new List<PointD>();
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();
}
}
解决方案
我做出了以下假设：
PointD是一个结构IndexOf确实比手动迭代列表要慢
你可以加快 IndexOf 通过实施 IEquatable<T> 界面：
struct PointD : IEquatable<PointD>
{
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<T> 界面， IndexOf 将比较两者 PointD 使用的元素 ValueType.Equals(object other) 涉及昂贵的拳击操作。
文档 IEquatable<T> 接口状态：
这
IEquatable<T>界面由通用集合对象（例如Dictionary<TKey, TValue>,List<T>, ， 和LinkedList<T>在测试以这样的方法测试平等时Contains,IndexOf,LastIndexOf, ， 和Remove. 它应该针对可能存储在通用集合中的任何对象实现。
这是我完整的基准代码：
using System;
using System.Collections.Generic;
using System.Diagnostics;
struct PointD
{
public int X;
public int Y;
public int Z;
}
class PerfTest
{
List<PointD> _pCoord3Points = new List<PointD>();
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
使用时 struct PointD 实施 IEquatable<PointD> 我得到了更多的“类似”结果，但是 IndexOf 仍然较慢（使用时没有显着差异 class 现在）：
IndexOf: 00:00:00.3904615 For Loop: 00:00:00.0015218
其他提示
通常，在访问数组元素之前，它会检查以确保索引> = 0 and <长度 - 这样您就不会读取或覆盖不属于您的内存。除其他外，它消除了许多称为严重的安全缺陷 缓冲区溢出.
不用说，如果您的循环中的代码很少，这会阻碍性能。为了减轻此问题，JIT编译器优化了表单 for (i = 0; i < array.Length; i++) { array[i]; } - 也就是说，任何访问数组的所有索引从0到长度的循环 - 1。它省略了此情况的边界检查。 （如果您访问诸如数组[i + 1]之类的内容，则优化将失败，原因是您可以跨越界限。）
不幸的是，这仅适用于数组，而不适合列表<> s。因此，您的后一个代码不会被优化。
但是，由于列表<>内部包含一个数组，并且list.indexof（）使用循环直接访问数组中的每个值，因此可以优化。
顺便说一句，最好说 for (int i = 0; i < array.Length; i++) { } 比说 int length = array.Length; for(int i = 0; i < length; i++) { } - 因为不能确定 length 确实是阵列的长度。
编辑：使用反射器查看索引代码，循环确实会优化，但是正如这里的其他人所提到的那样，它调用Equals（） - 它需要一个 可vtable查找 和各种理智检查。因此，在这种情况下，当您不使用Profiler运行它时，索引实际上可能会更慢。
分解的代码：
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;
}
什么类型 _pCoord3Points？如果元素类型是仅覆盖的值类型 Equals(object) 那可能 IndexOf 是反复的拳击值以检查平等。那 可能 解释一下。不过，这实际上只是猜测工作……如果您可以提供一个简短但完整的程序来证明问题，那将使您更容易为您提供帮助。
