假设你需要有一个整数列表/数组,你需要频繁迭代,我的意思是非常频繁。原因可能各不相同,但可以说这是在一个大容量处理的最内部循环的核心。

通常情况下,人们会选择使用列表(List),因为它们在大小上具有灵活性。最重要的是,msdn文档声称列表在内部使用数组,并且应该执行得一样快(快速查看Reflector证实了这一点)。尽管如此,还是有一些开销。

有人测量过吗?在一个列表中迭代6M次是否与数组相同?


当前回答

测量结果很好,但是根据您在内部循环中所做的具体操作,您将得到显著不同的结果。衡量你自己的情况。如果您正在使用多线程,那么这本身就不是一个简单的活动。

其他回答

[另见此问题]

我修改了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();
    }
}
static long[] longs = new long[500000];
static long[] longs2 = {};
static List<long> listLongs = new List<long> { };
static void Main(string[] args)
{
    Console.CursorVisible = false;
    Stopwatch time = new Stopwatch();

    time.Start();
    for (int f = 50000000; f < 50255000; f++)
    {
        listLongs.Add(f);
    }

    //List  Time: 1ms    Count : 255000
    Console.WriteLine("List Time: " + time.ElapsedMilliseconds + " | Count: " + listLongs.Count());

    time.Restart();
    time.Start();
    for (long i = 1; i < 500000; i++)
    {
        longs[i] = i * 200;
    }

    //Array Time: 2ms Length: 500000 (Unrealistic Data)
    Console.WriteLine("Array Time: " + time.ElapsedMilliseconds + " | Length: " + longs.Length);

    time.Restart();
    time.Start();
    for (int i = 50000000; i < 50055000; i++)
    {
        longs2 = longs2.Append(i).ToArray();
    }

    //Array Time: 17950ms Length: 55000
    Console.WriteLine("Array Append Time: " + time.ElapsedMilliseconds + " | Length: " + longs2.Length);

    Console.ReadLine();
}
Type Time Len
Array 2ms 500000
List 1ms 255000
Array Append 17950ms 55000

如果您计划不断地向数组中添加少量数据,那么list更快

这实际上取决于你将如何使用数组。

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

使用不可预测的输入(随机) 运行计算结果并将结果打印到控制台 每次重复修改输入数据

结果是,直接数组的性能比访问封装在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方法,该方法在底层数组中进行查找。所以你需要一个额外的方法调用。另一方面,编译器可能会识别出这一点,并优化“不必要的”调用。 如果编译器知道数组的大小,它可能会做一些特殊的优化,而对于一个未知长度的列表,它就不能这样做。如果列表中只有几个元素,这可能会带来一些性能改进。

要检查它是否对您有任何影响,最好将发布的计时函数调整为您计划使用的大小列表,并查看您的特殊情况的结果如何。

如果你只是从其中一个中获得一个值(不是在循环中),那么两者都进行边界检查(记住,你在托管代码中),只是列表做了两次。 请参阅后面的注释,了解为什么这可能不是什么大问题。

如果你正在使用你自己的for(int int i = 0;i < x.[Length/Count];i++)则键差如下所示:

数组: 边界检查被移除 列表 执行边界检查

如果你使用foreach,关键区别如下:

数组: 没有分配对象来管理迭代 边界检查被移除 List通过一个已知为List的变量。 迭代管理变量是堆栈分配的 执行边界检查 列表通过一个已知为IList的变量。 迭代管理变量是堆分配的 执行边界检查 also Lists的值在foreach过程中不能改变,而数组的值可以改变。

边界检查通常不是什么大问题(特别是如果您在一个具有深层管道和分支预测的cpu上——这是目前大多数情况下的常态),但只有您自己的分析才能告诉您这是否是一个问题。 如果你在代码中避免堆分配(很好的例子是库或hashcode实现),那么确保变量类型为List而不是IList将避免这个陷阱。 和往常一样,如果重要的话。