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

Question

我正在制作一个程序，可以实时从互联网连续接收数据（字符串类型）。为了更好的性能，它将新数据存储在列表（内存）中，并且每天只将其写入文件一次。

我想知道列表的大小是否越大，向其添加新值所需的时间就越长。例如，在性能方面，向大小为 10 的列表添加新数据与向大于 3000000 的列表执行相同操作之间有什么区别吗？我想知道如果我从一开始就设置列表的默认大小，例如new List<string>(3000000).

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

Answer 1

这是将项目添加到列表的实际源代码，您可以在此处找到list.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);

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

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