arrays与列表的性能

假设你需要有一个你需要经常迭代的整数列表，而且我的意思是非常频繁的。 原因可能会有所不同，但可以说它是高容量处理的最核心环节。

一般来说，由于其大小的灵活性，可以select使用列表（列表）。 最重要的是，msdn文档声明列表在内部使用数组，并且执行速度一样快（使用Reflector快速查看）。 没关系，有一些额外的开销。

有没有人真的衡量这个？ 会通过列表6M次迭代与数组相同的时间？

Answer 1

非常容易测量…

在我知道长度固定的less量紧密处理代码中，我使用数组来进行微小的优化; 如果使用索引器/表单，数组可能会稍微快一些 – 但是IIRC相信它取决于数组中的数据types。 但是除非你需要微调，否则保持简单，使用List<T>等

当然，这只适用于阅读所有数据; 一个字典会更快的基于键的查找。

这是我的结果使用“int”（第二个数字是校验和来validation他们都做了同样的工作）：

（编辑修复bug）

 List/for: 1971ms (589725196) Array/for: 1864ms (589725196) List/foreach: 3054ms (589725196) Array/foreach: 1860ms (589725196) 

基于testing装备：

 using System; using System.Collections.Generic; using System.Diagnostics; static class Program { static void Main() { List<int> list = new List<int>(6000000); Random rand = new Random(12345); for (int i = 0; i < 6000000; i++) { list.Add(rand.Next(5000)); } int[] arr = list.ToArray(); int chk = 0; Stopwatch watch = Stopwatch.StartNew(); for (int rpt = 0; rpt < 100; rpt++) { int len = list.Count; for (int i = 0; i < len; i++) { chk += list[i]; } } watch.Stop(); Console.WriteLine("List/for: {0}ms ({1})", watch.ElapsedMilliseconds, chk); chk = 0; watch = Stopwatch.StartNew(); for (int rpt = 0; rpt < 100; rpt++) { for (int i = 0; i < arr.Length; i++) { chk += arr[i]; } } watch.Stop(); Console.WriteLine("Array/for: {0}ms ({1})", watch.ElapsedMilliseconds, chk); chk = 0; watch = Stopwatch.StartNew(); for (int rpt = 0; rpt < 100; rpt++) { foreach (int i in list) { chk += i; } } watch.Stop(); Console.WriteLine("List/foreach: {0}ms ({1})", watch.ElapsedMilliseconds, chk); chk = 0; watch = Stopwatch.StartNew(); for (int rpt = 0; rpt < 100; rpt++) { foreach (int i in arr) { chk += i; } } watch.Stop(); Console.WriteLine("Array/foreach: {0}ms ({1})", watch.ElapsedMilliseconds, chk); Console.ReadLine(); } } 

Answer 2

我认为performance会非常相似。 使用列表与数组相关的开销是，当您向列表中添加项目时，恕我直言，当列表需要增加内部使用的数组的大小时，达到数组的容量。

假设你有一个容量为10的List，那么一旦你想添加第11个元素，List将增加它的容量。 您可以通过将列表的容量初始化为容纳的项目数来降低性能影响。

但是，为了弄清楚迭代List是否像遍历数组一样快，为什么不对它进行基准testing？

 int numberOfElements = 6000000; List<int> theList = new List<int> (numberOfElements); int[] theArray = new int[numberOfElements]; for( int i = 0; i < numberOfElements; i++ ) { theList.Add (i); theArray[i] = i; } Stopwatch chrono = new Stopwatch (); chrono.Start (); int j; for( int i = 0; i < numberOfElements; i++ ) { j = theList[i]; } chrono.Stop (); Console.WriteLine (String.Format("iterating the List took {0} msec", chrono.ElapsedMilliseconds)); chrono.Reset(); chrono.Start(); for( int i = 0; i < numberOfElements; i++ ) { j = theArray[i]; } chrono.Stop (); Console.WriteLine (String.Format("iterating the array took {0} msec", chrono.ElapsedMilliseconds)); Console.ReadLine(); 

在我的系统上 迭代数组需要33毫秒; 遍历列表需要66毫秒。

说实话，我没有想到变化会是那么多。 所以，我把我的迭代放在一个循环中：现在，我执行两次迭代1000次。 结果是：

迭代列表花了67146毫秒迭代数组花了40821毫秒

现在，变化不再那么大了，但仍然…

因此，我启动了.NET Reflector，并且List类的索引器的getter如下所示：

 public T get_Item(int index) { if (index >= this._size) { ThrowHelper.ThrowArgumentOutOfRangeException(); } return this._items[index]; } 

正如你所看到的，当你使用List的索引器的时候，List将检查你是否不在内部数组的边界之外。 这额外的检查来了一个成本。

Answer 3

如果你只是得到一个单一的价值（不是在一个循环），然后都做边界检查（你在托pipe代码记住）这只是列表做了两次。 后来看到这些笔记为什么这可能不是一个大问题。

如果你使用自己的（int int i = 0; i <x。[Length / Count]; i ++），那么关键的区别如下：

• 阵：
  • 边界检查被删除
• 清单
  • 执行边界检查

如果你使用的是foreach，那么关键的区别如下：

• 阵：
  • 没有对象被分配来pipe理迭代
  • 边界检查被删除
• 通过已知为List的variables列表。
  • 迭代pipe理variables是堆栈分配的
  • 执行边界检查
• 通过已知的IList列表进行列表。
  • 迭代pipe理variables是堆分配
  • 边界检查也执行列表值可能不会在foreach中更改，而数组的可以。

边界检查通常没有什么大不了的（尤其是如果你在一个有深度stream水线和分支预测的CPU上 – 现在大多数情况下是这样的），但是只有你自己的分析可以告诉你这是否是一个问题。 如果你在你的代码中避免堆分配的部分（好的例子是库或哈希码实现），那么确保variables的types为List不IList将避免这种陷阱。 一如既往的configuration文件

Answer 4

[ 也见这个问题 ]

我修改了Marc的答案，使用实际的随机数字，并且在所有情况下都做了相同的工作。

结果：

         为foreach
arrays：1575ms 1575ms（+ 0％）
列表：1630ms 2627ms（+ 61％）
          （升百分之三）（+百分之六十七）

 （校验和：-1000038876）

编译为VS 2008 SP1下的发行版。 在Q6600@2.40GHz，.NET 3.5 SP1上运行而不进行debugging。

码：

 class Program { static void Main(string[] args) { List<int> list = new List<int>(6000000); Random rand = new Random(1); for (int i = 0; i < 6000000; i++) { list.Add(rand.Next()); } int[] arr = list.ToArray(); int chk = 0; Stopwatch watch = Stopwatch.StartNew(); for (int rpt = 0; rpt < 100; rpt++) { int len = list.Count; for (int i = 0; i < len; i++) { chk += list[i]; } } watch.Stop(); Console.WriteLine("List/for: {0}ms ({1})", watch.ElapsedMilliseconds, chk); chk = 0; watch = Stopwatch.StartNew(); for (int rpt = 0; rpt < 100; rpt++) { int len = arr.Length; for (int i = 0; i < len; i++) { chk += arr[i]; } } watch.Stop(); Console.WriteLine("Array/for: {0}ms ({1})", watch.ElapsedMilliseconds, chk); chk = 0; watch = Stopwatch.StartNew(); for (int rpt = 0; rpt < 100; rpt++) { foreach (int i in list) { chk += i; } } watch.Stop(); Console.WriteLine("List/foreach: {0}ms ({1})", watch.ElapsedMilliseconds, chk); chk = 0; watch = Stopwatch.StartNew(); for (int rpt = 0; rpt < 100; rpt++) { foreach (int i in arr) { chk += i; } } watch.Stop(); Console.WriteLine("Array/foreach: {0}ms ({1})", watch.ElapsedMilliseconds, chk); Console.WriteLine(); Console.ReadLine(); } } 

Answer 5

简短的回答：

更详细的答案你会发现通过以下链接： https : //stackoverflow.com/a/29263914/4423545

Answer 6

测量结果很好，但是根据你在内部循环中做什么，你会得到明显不同的结果。 衡量你自己的情况。 如果你使用的是multithreading，那么这是一个不重要的活动。

Answer 7

事实上，如果你在循环内部执行一些复杂的计算，那么数组索引器相对于列表索引器的性能可能会非常小，最终，这并不重要。

Answer 8

不要通过增加元素的数量来增加容量。

性能

 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 

Answer 9

这是一个使用字典，IEnumerable：

 using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; static class Program { static void Main() { List<int> list = new List<int>(6000000); for (int i = 0; i < 6000000; i++) { list.Add(i); } Console.WriteLine("Count: {0}", list.Count); int[] arr = list.ToArray(); IEnumerable<int> Ienumerable = list.ToArray(); Dictionary<int, bool> dict = list.ToDictionary(x => x, y => true); int chk = 0; Stopwatch watch = Stopwatch.StartNew(); for (int rpt = 0; rpt < 100; rpt++) { int len = list.Count; for (int i = 0; i < len; i++) { chk += list[i]; } } watch.Stop(); Console.WriteLine("List/for: {0}ms ({1})", watch.ElapsedMilliseconds, chk); chk = 0; watch = Stopwatch.StartNew(); for (int rpt = 0; rpt < 100; rpt++) { for (int i = 0; i < arr.Length; i++) { chk += arr[i]; } } watch.Stop(); Console.WriteLine("Array/for: {0}ms ({1})", watch.ElapsedMilliseconds, chk); chk = 0; watch = Stopwatch.StartNew(); for (int rpt = 0; rpt < 100; rpt++) { foreach (int i in Ienumerable) { chk += i; } } Console.WriteLine("Ienumerable/for: {0}ms ({1})", watch.ElapsedMilliseconds, chk); chk = 0; watch = Stopwatch.StartNew(); for (int rpt = 0; rpt < 100; rpt++) { foreach (int i in dict.Keys) { chk += i; } } Console.WriteLine("Dict/for: {0}ms ({1})", watch.ElapsedMilliseconds, chk); chk = 0; watch = Stopwatch.StartNew(); for (int rpt = 0; rpt < 100; rpt++) { foreach (int i in list) { chk += i; } } watch.Stop(); Console.WriteLine("List/foreach: {0}ms ({1})", watch.ElapsedMilliseconds, chk); chk = 0; watch = Stopwatch.StartNew(); for (int rpt = 0; rpt < 100; rpt++) { foreach (int i in arr) { chk += i; } } watch.Stop(); Console.WriteLine("Array/foreach: {0}ms ({1})", watch.ElapsedMilliseconds, chk); chk = 0; watch = Stopwatch.StartNew(); for (int rpt = 0; rpt < 100; rpt++) { foreach (int i in Ienumerable) { chk += i; } } watch.Stop(); Console.WriteLine("Ienumerable/foreach: {0}ms ({1})", watch.ElapsedMilliseconds, chk); chk = 0; watch = Stopwatch.StartNew(); for (int rpt = 0; rpt < 100; rpt++) { foreach (int i in dict.Keys) { chk += i; } } watch.Stop(); Console.WriteLine("Dict/foreach: {0}ms ({1})", watch.ElapsedMilliseconds, chk); Console.ReadLine(); } } 

Answer 10

由于List <>在内部使用数组，因此基本性能应该是相同的。 两个原因，为什么列表可能会稍微慢一些：

• 为了在列表中查找一个元素，调用一个List方法，在底层数组中查找。 所以你需要一个额外的方法调用。 另一方面，编译器可能会认识到这一点，并优化“不必要”的电话。
• 编译器可能会做一些特殊的优化，如果它知道数组的大小，它不能做一个未知长度的列表。 如果您的列表中只有less数元素，这可能会带来一些性能提升。

要检查它是否对你有什么影响，最好将已发布的计时函数调整到你打算使用的大小列表，并查看特殊情况下的结果如何。

Answer 11

我担心在其他答案中发布的基准仍然会为编译器留出空间来优化，消除或合并循环，所以我写了一个：

• 使用不可预知的input（随机）
• 运行结果打印到控制台
• 每次重复修改input数据

直接数组的性能比访问IList中包含的数组的性能高出250％：

• 10亿个arrays访问：4000毫秒
• 10亿个列表访问：10000毫秒
• 1亿个arrays访问：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; } 

Answer 12

由于我有类似的问题，所以我得到了一个快速的开始。

我的问题更具体一些，“自反arrays实现的最快方法是什么”

Marc Gravell所做的testing显示了很多，但不完全是访问时间。 他的计时包括循环数组和列表。 因为我想出了第三种方法，我想testing一个“字典”，只是为了比较，我扩展了组织testing代码。

Firts，我使用一个常量来做一个testing，这给了我一定的时间，包括循环。 这是一个“裸”的时机，不包括实际的访问。 然后我做一个访问主题结构的testing，这给我和'开销包括'的时间，循环和实际访问。

“裸”时机和“开机时间”时机之间的区别给了我“结构访问”时机的指示。

但这个时机有多准确？ 在testing过程中，窗户会做一些时间切割。 我没有关于时间分片的信息，但我假设它在testing期间是均匀分布的，并且是几十毫秒的数量级，这意味着时序的精确度应该在+/- 100毫秒左右。 有点粗略的估计？ 无论如何，系统测量错误的来源。

而且，testing是在“debugging”模式下完成的，没有最优化。 否则，编译器可能会更改实际的testing代码。

所以，我得到了两个结果，一个是常量，标记为“（c）”，另一个是标记为“（n）”的访问，差异“dt”告诉我实际访问需要多less时间。

这是结果：

  Dictionary(c)/for: 1205ms (600000000) Dictionary(n)/for: 8046ms (589725196) dt = 6841 List(c)/for: 1186ms (1189725196) List(n)/for: 2475ms (1779450392) dt = 1289 Array(c)/for: 1019ms (600000000) Array(n)/for: 1266ms (589725196) dt = 247 Dictionary[key](c)/foreach: 2738ms (600000000) Dictionary[key](n)/foreach: 10017ms (589725196) dt = 7279 List(c)/foreach: 2480ms (600000000) List(n)/foreach: 2658ms (589725196) dt = 178 Array(c)/foreach: 1300ms (600000000) Array(n)/foreach: 1592ms (589725196) dt = 292 dt +/-.1 sec for foreach Dictionary 6.8 7.3 List 1.3 0.2 Array 0.2 0.3 Same test, different system: dt +/- .1 sec for foreach Dictionary 14.4 12.0 List 1.7 0.1 Array 0.5 0.7 

通过更好地估计时间误差（如何消除由于时间片导致的系统测量误差？），可以对结果做更多​​的说明。

它看起来像列表/ foreach有最快的访问，但开销正在杀死它。

List / for和List / foreach之间的区别是stange。 也许一些兑现是参与？

此外，对于访问数组，使用for循环或foreach循环无关紧要。 时间结果及其准确性使得结果“可比较”。

使用字典是最慢的，我只考虑它，因为在左侧（索引器）我有一个稀疏的整数列表，而不是在这个testing中使用的范围。

这是修改后的testing代码。

 Dictionary<int, int> dict = new Dictionary<int, int>(6000000); List<int> list = new List<int>(6000000); Random rand = new Random(12345); for (int i = 0; i < 6000000; i++) { int n = rand.Next(5000); dict.Add(i, n); list.Add(n); } int[] arr = list.ToArray(); int chk = 0; Stopwatch watch = Stopwatch.StartNew(); for (int rpt = 0; rpt < 100; rpt++) { int len = dict.Count; for (int i = 0; i < len; i++) { chk += 1; // dict[i]; } } watch.Stop(); long c_dt = watch.ElapsedMilliseconds; Console.WriteLine(" Dictionary(c)/for: {0}ms ({1})", c_dt, chk); chk = 0; watch = Stopwatch.StartNew(); for (int rpt = 0; rpt < 100; rpt++) { int len = dict.Count; for (int i = 0; i < len; i++) { chk += dict[i]; } } watch.Stop(); long n_dt = watch.ElapsedMilliseconds; Console.WriteLine(" Dictionary(n)/for: {0}ms ({1})", n_dt, chk); Console.WriteLine("dt = {0}", n_dt - c_dt); watch = Stopwatch.StartNew(); for (int rpt = 0; rpt < 100; rpt++) { int len = list.Count; for (int i = 0; i < len; i++) { chk += 1; // list[i]; } } watch.Stop(); c_dt = watch.ElapsedMilliseconds; Console.WriteLine(" List(c)/for: {0}ms ({1})", c_dt, chk); watch = Stopwatch.StartNew(); for (int rpt = 0; rpt < 100; rpt++) { int len = list.Count; for (int i = 0; i < len; i++) { chk += list[i]; } } watch.Stop(); n_dt = watch.ElapsedMilliseconds; Console.WriteLine(" List(n)/for: {0}ms ({1})", n_dt, chk); Console.WriteLine("dt = {0}", n_dt - c_dt); chk = 0; watch = Stopwatch.StartNew(); for (int rpt = 0; rpt < 100; rpt++) { for (int i = 0; i < arr.Length; i++) { chk += 1; // arr[i]; } } watch.Stop(); c_dt = watch.ElapsedMilliseconds; Console.WriteLine(" Array(c)/for: {0}ms ({1})", c_dt, chk); chk = 0; watch = Stopwatch.StartNew(); for (int rpt = 0; rpt < 100; rpt++) { for (int i = 0; i < arr.Length; i++) { chk += arr[i]; } } watch.Stop(); n_dt = watch.ElapsedMilliseconds; Console.WriteLine("Array(n)/for: {0}ms ({1})", n_dt, chk); Console.WriteLine("dt = {0}", n_dt - c_dt); chk = 0; watch = Stopwatch.StartNew(); for (int rpt = 0; rpt < 100; rpt++) { foreach (int i in dict.Keys) { chk += 1; // dict[i]; ; } } watch.Stop(); c_dt = watch.ElapsedMilliseconds; Console.WriteLine("Dictionary[key](c)/foreach: {0}ms ({1})", c_dt, chk); chk = 0; watch = Stopwatch.StartNew(); for (int rpt = 0; rpt < 100; rpt++) { foreach (int i in dict.Keys) { chk += dict[i]; ; } } watch.Stop(); n_dt = watch.ElapsedMilliseconds; Console.WriteLine("Dictionary[key](n)/foreach: {0}ms ({1})", n_dt, chk); Console.WriteLine("dt = {0}", n_dt - c_dt); chk = 0; watch = Stopwatch.StartNew(); for (int rpt = 0; rpt < 100; rpt++) { foreach (int i in list) { chk += 1; // i; } } watch.Stop(); c_dt = watch.ElapsedMilliseconds; Console.WriteLine(" List(c)/foreach: {0}ms ({1})", c_dt, chk); chk = 0; watch = Stopwatch.StartNew(); for (int rpt = 0; rpt < 100; rpt++) { foreach (int i in list) { chk += i; } } watch.Stop(); n_dt = watch.ElapsedMilliseconds; Console.WriteLine(" List(n)/foreach: {0}ms ({1})", n_dt, chk); Console.WriteLine("dt = {0}", n_dt - c_dt); chk = 0; watch = Stopwatch.StartNew(); for (int rpt = 0; rpt < 100; rpt++) { foreach (int i in arr) { chk += 1; // i; } } watch.Stop(); c_dt = watch.ElapsedMilliseconds; Console.WriteLine(" Array(c)/foreach: {0}ms ({1})", c_dt, chk); chk = 0; watch = Stopwatch.StartNew(); for (int rpt = 0; rpt < 100; rpt++) { foreach (int i in arr) { chk += i; } } watch.Stop(); n_dt = watch.ElapsedMilliseconds; Console.WriteLine("Array(n)/foreach: {0}ms ({1})", n_dt, chk); Console.WriteLine("dt = {0}", n_dt - c_dt); 

Answer 13

在一些简短的testing中，我发现两者的结合在我所说的合理密集的math中会更好：

types： List<double[]>

时间：00：00：05.1861300

types： List<List<double>>

时间：00：00：05.7941351

types： double[rows * columns]

时间：00：00：06.0547118

运行代码：

 int rows = 10000; int columns = 10000; IMatrix Matrix = new IMatrix(rows, columns); Stopwatch stopwatch = new Stopwatch(); stopwatch.Start(); for (int r = 0; r < Matrix.Rows; r++) for (int c = 0; c < Matrix.Columns; c++) Matrix[r, c] = Math.E; for (int r = 0; r < Matrix.Rows; r++) for (int c = 0; c < Matrix.Columns; c++) Matrix[r, c] *= -Math.Log(Math.E); stopwatch.Stop(); TimeSpan ts = stopwatch.Elapsed; Console.WriteLine(ts.ToString()); 

我希望我们有一些顶尖的硬件加速matrix类，如.NET团队已经完成System.Numerics.Vectors类！

C＃可能是最好的ML语言，在这方面多一点工作！