假设你需要有一个整数列表/数组,你需要频繁迭代,我的意思是非常频繁。原因可能各不相同,但可以说这是在一个大容量处理的最内部循环的核心。
通常情况下,人们会选择使用列表(List),因为它们在大小上具有灵活性。最重要的是,msdn文档声称列表在内部使用数组,并且应该执行得一样快(快速查看Reflector证实了这一点)。尽管如此,还是有一些开销。
有人测量过吗?在一个列表中迭代6M次是否与数组相同?
假设你需要有一个整数列表/数组,你需要频繁迭代,我的意思是非常频繁。原因可能各不相同,但可以说这是在一个大容量处理的最内部循环的核心。
通常情况下,人们会选择使用列表(List),因为它们在大小上具有灵活性。最重要的是,msdn文档声称列表在内部使用数组,并且应该执行得一样快(快速查看Reflector证实了这一点)。尽管如此,还是有一些开销。
有人测量过吗?在一个列表中迭代6M次是否与数组相同?
当前回答
不要试图通过增加元素数量来增加容量。
性能
List For Add: 1ms
Array For Add: 2397ms
Stopwatch watch;
#region --> List For Add <--
List<int> intList = new List<int>();
watch = Stopwatch.StartNew();
for (int rpt = 0; rpt < 60000; rpt++)
{
intList.Add(rand.Next());
}
watch.Stop();
Console.WriteLine("List For Add: {0}ms", watch.ElapsedMilliseconds);
#endregion
#region --> Array For Add <--
int[] intArray = new int[0];
watch = Stopwatch.StartNew();
int sira = 0;
for (int rpt = 0; rpt < 60000; rpt++)
{
sira += 1;
Array.Resize(ref intArray, intArray.Length + 1);
intArray[rpt] = rand.Next();
}
watch.Stop();
Console.WriteLine("Array For Add: {0}ms", watch.ElapsedMilliseconds);
#endregion
其他回答
如果你只是从其中一个中获得一个值(不是在循环中),那么两者都进行边界检查(记住,你在托管代码中),只是列表做了两次。 请参阅后面的注释,了解为什么这可能不是什么大问题。
如果你正在使用你自己的for(int int i = 0;i < x.[Length/Count];i++)则键差如下所示:
数组: 边界检查被移除 列表 执行边界检查
如果你使用foreach,关键区别如下:
数组: 没有分配对象来管理迭代 边界检查被移除 List通过一个已知为List的变量。 迭代管理变量是堆栈分配的 执行边界检查 列表通过一个已知为IList的变量。 迭代管理变量是堆分配的 执行边界检查 also Lists的值在foreach过程中不能改变,而数组的值可以改变。
边界检查通常不是什么大问题(特别是如果您在一个具有深层管道和分支预测的cpu上——这是目前大多数情况下的常态),但只有您自己的分析才能告诉您这是否是一个问题。 如果你在代码中避免堆分配(很好的例子是库或hashcode实现),那么确保变量类型为List而不是IList将避免这个陷阱。 和往常一样,如果重要的话。
我担心在其他答案中发布的基准测试仍然会为编译器留下优化,消除或合并循环的空间,所以我写了一个:
使用不可预测的输入(随机) 运行计算结果并将结果打印到控制台 每次重复修改输入数据
结果是,直接数组的性能比访问封装在IList中的数组要好250%:
10亿次数组访问:4000毫秒 10亿次列表访问:10000毫秒 1亿个数组访问:350毫秒 1亿次列表访问:1000毫秒
代码如下:
static void Main(string[] args) {
const int TestPointCount = 1000000;
const int RepetitionCount = 1000;
Stopwatch arrayTimer = new Stopwatch();
Stopwatch listTimer = new Stopwatch();
Point2[] points = new Point2[TestPointCount];
var random = new Random();
for (int index = 0; index < TestPointCount; ++index) {
points[index].X = random.NextDouble();
points[index].Y = random.NextDouble();
}
for (int repetition = 0; repetition <= RepetitionCount; ++repetition) {
if (repetition > 0) { // first repetition is for cache warmup
arrayTimer.Start();
}
doWorkOnArray(points);
if (repetition > 0) { // first repetition is for cache warmup
arrayTimer.Stop();
}
if (repetition > 0) { // first repetition is for cache warmup
listTimer.Start();
}
doWorkOnList(points);
if (repetition > 0) { // first repetition is for cache warmup
listTimer.Stop();
}
}
Console.WriteLine("Ignore this: " + points[0].X + points[0].Y);
Console.WriteLine(
string.Format(
"{0} accesses on array took {1} ms",
RepetitionCount * TestPointCount, arrayTimer.ElapsedMilliseconds
)
);
Console.WriteLine(
string.Format(
"{0} accesses on list took {1} ms",
RepetitionCount * TestPointCount, listTimer.ElapsedMilliseconds
)
);
}
private static void doWorkOnArray(Point2[] points) {
var random = new Random();
int pointCount = points.Length;
Point2 accumulated = Point2.Zero;
for (int index = 0; index < pointCount; ++index) {
accumulated.X += points[index].X;
accumulated.Y += points[index].Y;
}
accumulated /= pointCount;
// make use of the result somewhere so the optimizer can't eliminate the loop
// also modify the input collection so the optimizer can merge the repetition loop
points[random.Next(0, pointCount)] = accumulated;
}
private static void doWorkOnList(IList<Point2> points) {
var random = new Random();
int pointCount = points.Count;
Point2 accumulated = Point2.Zero;
for (int index = 0; index < pointCount; ++index) {
accumulated.X += points[index].X;
accumulated.Y += points[index].Y;
}
accumulated /= pointCount;
// make use of the result somewhere so the optimizer can't eliminate the loop
// also modify the input collection so the optimizer can merge the repetition loop
points[random.Next(0, pointCount)] = accumulated;
}
实际上,如果在循环中执行一些复杂的计算,那么数组索引器与列表索引器的性能可能会非常小,最终,这无关紧要。
测量结果很好,但是根据您在内部循环中所做的具体操作,您将得到显著不同的结果。衡量你自己的情况。如果您正在使用多线程,那么这本身就不是一个简单的活动。
由于List<>在内部使用数组,因此基本性能应该是相同的。为什么这个列表可能会稍微慢一些,有两个原因:
要在列表中查找元素,调用list方法,该方法在底层数组中进行查找。所以你需要一个额外的方法调用。另一方面,编译器可能会识别出这一点,并优化“不必要的”调用。 如果编译器知道数组的大小,它可能会做一些特殊的优化,而对于一个未知长度的列表,它就不能这样做。如果列表中只有几个元素,这可能会带来一些性能改进。
要检查它是否对您有任何影响,最好将发布的计时函数调整为您计划使用的大小列表,并查看您的特殊情况的结果如何。