阵列与列表的性能

Question

假设您需要有一个需要经常迭代的整数列表/数组,我的意思是非常频繁.原因可能有所不同,但它说它是高容量处理的最内循环的核心.

通常,由于其大小的灵活性,人们会选择使用列表(列表).最重要的是,msdn文档声称列表在内部使用数组,并且应该执行速度快(使用Reflector快速查看确认这一点).不用说,有一些开销.

有没有人真正测量过这个？通过列表迭代6M次与阵列相同的时间？

Answer 1

很容易衡量......

在少量紧密循环处理代码中,我知道长度是固定的,我使用数组进行微小优化; 如果使用索引器/表单,数组可以略微加快- 但IIRC认为它取决于数组中的数据类型.但除非你需要微观优化,保持简单和使用等.List<T>

当然,这只适用于您阅读所有数据的情况; 对于基于密钥的查找,字典会更快.

这是我使用"int"的结果(第二个数字是校验和来验证它们都做了同样的工作):

(编辑修复bug)

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

基于试验台:

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

简短回答:

您将通过以下链接找到更详细的答案:https://stackoverflow.com/a/29263914/4423545

Answer 3

我认为性能会非常相似.使用List vs a Array时所涉及的开销是,当您向列表中添加项目时,恕我直言,以及当列表必须增加其内部使用的数组的大小时,达到数组的容量时.

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

但是,为了弄清楚迭代List是否与迭代数组一样快,为什么不对它进行基准测试呢？

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 4

如果你只是从中获取单个值(不在循环中),那么两者都进行边界检查(你在托管代码中记得)它就是列表执行两次.稍后请参阅说明,了解为什么这可能不是什么大问题.

如果您使用自己的(int int i = 0; i <x.[Length/Count]; i ++),那么关键区别如下:

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

如果您使用的是foreach,那么关键区别如下:

• 阵:
  • 没有分配对象来管理迭代
  • 边界检查被删除
• 通过已知为List的变量列出.
  • 迭代管理变量是堆栈分配的
  • 执行边界检查
• 通过已知为IList的变量列出.
  • 迭代管理变量是堆分配的
  • 也执行边界检查列表值在foreach期间不能更改,而数组可以.

边界检查通常没什么大不了的(特别是如果你在具有深度管道和分支预测的cpu上 - 这些日子大多数都是常规)但只有你自己的分析可以告诉你这是否是一个问题.如果你在代码的一部分中避免堆分配(很好的例子是库或哈希码实现),那么确保变量被输入为List而不是IList将避免这个陷阱.如果重要的话,一如既往.

Answer 5

[ 另见这个问题 ]

我修改了Marc的答案,使用实际的随机数,实际上在所有情况下做同样的工作.

结果:

         for      foreach
Array : 1575ms     1575ms (+0%)
List  : 1630ms     2627ms (+61%)
         (+3%)     (+67%)

(Checksum: -1000038876)

在VS 2008 SP1下编译为发行版.在Q6600@2.40GHz,.NET 3.5 SP1上无需调试即可运行.

码:

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();
    }
}