代码之家 › 专栏 › 技术社区 › maynull

列表的大小越大,添加新值所需的时间越多,这是真的吗?

list c#

maynull · 技术社区 · 6 年前

我正在制作一个程序,它不断地从互联网实时接收数据(字符串类型)。为了提高性能,它将新数据存储在一个列表(内存)中,并每天只将其写入一个文件。

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

如果我能得到一些更好的工作方法的建议,我将不胜感激。

2 回复 | 直到 6 年前

TheGeneral 6 年前

这是将项目添加到列表的实际源代码,您可以在此处找到该列表 list.cs - Reference Source - 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() 复制数据,速度非常快。

举个例子,这里有一个包含100000000个元素的字节数组,它在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);

如果我能得到一些更好的方法的建议,我会很感激的。工作

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

Lajos Arpad 6 年前

正如MichaelRandall在他精彩的回答(upvote)中指出的,实际问题的答案是肯定的。然而,即使我们知道一个列表变大会减慢添加项目的速度,我们仍然有一个问题。您可以创建列表列表。

为了简单起见,我将“外部列表”称为列表列表,“内部列表”称为外部列表中的列表。您将首先创建第一个内部列表,并让项目进入它,直到它变得相当大,比如说,10000个元素。然后,创建下一个内部列表,新项目将放在那里,直到达到极限。一天又一天。这意味着在一天结束时,你可能会有300个列表,每个列表有10000个元素。这会使你的工作稍微复杂一点,但是当你向它添加项目时,它会让你的性能下降。