列表的大小越大，向其添加新值所需的时间就越长，这是真的吗？

Question

我正在制作一个程序，可以连续地从互联网实时接收数据（字符串类型）。为了获得更好的性能，它将新数据存储在列表（内存）中，并且每天仅将其写入文件一次。我想知道列表的大小是否越大，向其添加新值所需的时间就越多。例如，在性能方面，向大小为 10 的列表添加新数据与对大于 3000000 的列表执行相同操作之间是否存在任何差异？我想知道如果我从一开始就设置列表的默认大小，性能是否会有任何差异，例如.new List<string>(3000000)如果我能得到一些关于更好地完成这项工作的建议，我将不胜感激。

Answer 1

这是将项目添加到列表的实际源代码，您可以在此处找到列表.cs - 参考源 - Microsoft

public void Add(T item)

{

   if (_size == _items.Length) EnsureCapacity(_size + 1);

   _items[_size++] = item;

   _version++;

}

private void EnsureCapacity(int min)

{

   if (_items.Length < min)

   {

      int newCapacity = _items.Length == 0 ? _defaultCapacity : _items.Length * 2;

      // Allow the list to grow to maximum possible capacity (~2G elements) before encountering overflow.

      // Note that this check works even when _items.Length overflowed thanks to the (uint) cast

      if ((uint)newCapacity > Array.MaxArrayLength) newCapacity = Array.MaxArrayLength;

      if (newCapacity < min) newCapacity = min;

      Capacity = newCapacity;

   }

}

public int Capacity

{

   ...

   set

   {

      ...

      if (value != _items.Length)

      {

         if (value > 0)

         {

            T[] newItems = new T[value];

            if (_size > 0)

            {

               Array.Copy(_items, 0, newItems, 0, _size);

            }

            _items = newItems;

         }

         else

         {

            _items = _emptyArray;

         }

      }

   }

}

总而言之，它每次都会使容量翻倍，这意味着它实际上只将阵列扩展了有限的次数。这样做，它会创建一个新数组，并用于复制数据，这是非常快的。Array.Copy()

举个例子，下面是一个包含 100，000，000 个元素的字节数组，它在 75 毫秒内复制它。还要记住，在达到.Net的最大数组限制之前，它最多只会增长约32倍。

var r = new Random();

var bytes = new byte[100000000];

var bytes2 = new byte[100000000];

r.NextBytes(bytes);

var sw = Stopwatch.StartNew();

Array.Copy(bytes,bytes2,bytes.Length);

sw.Stop();

Console.WriteLine(sw.ElapsedMilliseconds);

如果我能得到一些关于更好地完成这项工作的建议，我将不胜感激。

好吧，如果这真的是关键任务的东西，并且你想节省垃圾回收器和大型对象堆上的分配和内存压力，只需创建一个容量集足够大的列表（或一个数组），然后重用它。但是，在我看来，您可能还需要首先担心其他事情。

Answer 2

正如迈克尔·兰德尔（Michael Randall）在他精彩的答案（赞成票）中指出的那样，实际问题的答案是肯定的。但是，即使我们知道列表变大会增加项目的速度，但我们仍然有问题。您可以创建列表列表。

为了简单起见，我将“外部列表”称为列表列表，将“内部列表”称为外部列表内部列表。您可以从创建第一个内部列表并让项目进入它开始，直到它变得相当大，比如说，10 000个元素。然后，创建下一个内部列表，新项将放在那里，直到达到限制。等等。这意味着在一天结束时，您可能有300个列表，每个列表有10 000个元素。它会使您的工作变得复杂，但是当您向其添加项时，它会使您摆脱性能下降。