2

我已经对 C# 中的列表进行了一些速度测试。这是我无法解释的结果。我希望有人能弄清楚发生了什么。

如果在 cloneList.Add(next) 之前调用 cloneList.RemoveAt(cloneList.Count - 1)，则 1000 次迭代的毫秒数：x 毫秒。

如果在 cloneList.Add(next) 之前未调用 cloneList.RemoveAt(cloneList.Count - 1)，则 1000 次迭代的毫秒数：至少20x毫秒。

似乎如果再有一条语句，我的代码会快 20 倍（请参见下面的代码）：

        Stopwatch stopWatch = new Stopwatch();
        Random random = new Random(100);

        TimeSpan caseOneTimeSpan = new TimeSpan();
        TimeSpan caseTwoTimeSpan = new TimeSpan();


        int len = 1000;

        List<int> myList = new List<int>();
        myList.Capacity = len + 1;

        // filling the list
        for (int i = 0; i < len; i++)
            myList.Add(random.Next(1000));

        // number of tests (1000)
        for (int i = 0; i < 1000; i++)
        {
            List<int> cloneList = myList.ToList();
            int next = random.Next();

            // case 1 - remove last item before adding the new item
            stopWatch.Start();
            cloneList.RemoveAt(cloneList.Count - 1);
            cloneList.Add(next);
            caseOneTimeSpan += stopWatch.Elapsed;

            // reset stopwatch and clone list

            stopWatch.Reset();
            cloneList = myList.ToList();

            // case 2 - add without removing
            stopWatch.Start();
            cloneList.Add(next);
            caseTwoTimeSpan += stopWatch.Elapsed;


            stopWatch.Reset();

        }

        Console.WriteLine("Case 1: " + caseOneTimeSpan.TotalMilliseconds);
        Console.WriteLine("Case 2: " + caseTwoTimeSpan.TotalMilliseconds);
        Console.WriteLine("Case 2 / Case 1: " + caseTwoTimeSpan.TotalMilliseconds / caseOneTimeSpan.TotalMilliseconds);
4

2 回答 2

3

当您将项目添加到列表时，有两种可能性：

  1. 内部缓冲区足够大，可以添加另一个项目。该项目被放置在下一个空闲位置。 速度：O(1)（这是最常见的情况。）
  2. 内部缓冲区不够大。创建一个新的更大的缓冲区。将旧缓冲区中的所有项目复制到新缓冲区。将下一项添加到新缓冲区。 速度：O(n)（这不应该经常发生）

虽然大多数Add调用将是 O(1)，但有些是 O(n)。

删除最后一项总是 O(1)。

由于Add有时取决于列表的大小，因此当列表较大时，它需要更长的时间（如果任何调用需要新的缓冲区）。如果您在添加新项目时总是删除项目，则可以确保内部缓冲区始终有足够的空间。

您可以查看 的Capacity属性List以查看内部缓冲区的当前大小并将其与 进行比较Count，后者是列表实际拥有的项目数。（因此Capacity-Count是缓冲区中空闲项目的数量。）虽然在实际程序中并不经常有用，但在调试或开发应用程序时查看这些工具可能有助于帮助您了解下面发生的事情。

于 2012-09-13T21:03:15.050 回答
0

这应该使差异消失：

        // reset stopwatch and clone list
        stopWatch.Reset();
        cloneList = myList.ToList();
        cloneList.Capacity = cloneList.Capacity + 1;   // add this

        // case 2 - add without removing
        stopWatch.Start();
        cloneList.Add(next);
        caseTwoTimeSpan += stopWatch.Elapsed;
于 2012-09-13T21:08:49.410 回答