Правда ли, что чем больше размер списка, тем больше времени требуется для добавления в него новых значений?

Question

Я делаю программу, которая постоянно получает данные (строковый тип) из Интернета в режиме реального времени.Для повышения производительности он сохраняет новые данные в списке (памяти) и записывает их в файл только один раз в день.

Интересно, чем больше размер списка, тем больше времени требуется для добавления в него новых значений.Например, есть ли разница в производительности по сравнению с добавлением новых данных в список, размер которого равен 10, и выполнением того же действия со списком, который больше 3000000?И я хотел бы знать, будет ли разница в производительности, если я установлю размер списка по умолчанию с самого начала, например new List<string>(3000000).

Я был бы признателен, если бы мог получить совето лучших способах сделать эту работу.

Answer 1

Как отметил Майкл Рэндалл в своем замечательном ответе (upvote), ответ на настоящий вопрос - да.Однако, несмотря на то, что мы знаем, что большой список будет добавлять элементы медленнее, у нас все еще есть проблема.Вы можете создать список списков.

Ради простоты я назову «внешний список» списком списков, а «внутренний список» списками внутри внешнего списка.Вы начнете с создания первого внутреннего списка и добавления элементов в него, пока он не станет достаточно большим, скажем, из 10 000 элементов.Затем вы создаете следующий внутренний список и новые элементы будут помещены туда, пока это не достигнет предела.И так далее.Это будет означать, что в конце дня у вас будет около 300 списков, каждый из которых содержит 10 000 элементов.Это немного усложнит вашу работу, но избавит вас от падения производительности при добавлении к нему элементов.

Answer 2

Это фактический исходный код для добавления элемента в список, который вы можете найти здесь 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 миллисекунд.также помните, что он будет расти только максимум примерно в 32 раза, пока не достигнет максимального значения массива .Net

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);

Я был бы признателен, если бы мог получить несколько советов по лучшим способамчтобы выполнить эту работу

Ну, если это действительно критически важные вещи и вы хотите сэкономить ресурсы и нагрузку на память для сборщика мусора и кучи больших объектов, просто создайте список с достаточно большой разовой емкостью.(или массив), и просто используйте его повторно.Однако, по моему честному мнению, есть еще кое-что, о чём вам стоит побеспокоиться.