Почему AddRange быстрее, чем использование цикла foreach?

var fillData = new List<int>();
for (var i = 0; i < 100000; i++)
{
     fillData.Add(i);
}

var stopwatch1 = new Stopwatch();
stopwatch1.Start();
var autoFill = new List<int>();
autoFill.AddRange(fillData);
stopwatch1.Stop();

var stopwatch2 = new Stopwatch();
stopwatch2.Start();
var manualFill = new List<int>();
foreach (var i in fillData)
{
    manualFill.Add(i);
}
stopwatch2.Stop();

Когда я принимаю 4 результаты от stopwach1 и stopwach2, stopwatch1 всегда имеет меньшее значение, чем stopwatch2. Это означает, что addrange всегда быстрее, чем foreach. Кто-нибудь знает, почему?

Ответы

Ответ 1

Потенциально, AddRange может проверить, где переданное значение реализует IList или IList<T>. Если это так, он может узнать, сколько значений находится в диапазоне, и, следовательно, сколько места ему нужно выделить... тогда как цикл foreach может потребоваться перераспределить несколько раз.

Кроме того, даже после выделения List<T> может использовать IList<T>.CopyTo для выполнения массовой копии в базовом массиве (для диапазонов, которые реализуют IList<T>, из Конечно.)

Я подозреваю, что вы обнаружите, что если вы снова попробуете свой тест, но используете Enumerable.Range(0, 100000) для fillData вместо List<T>, то два будут занимать примерно одно и то же время.

Ответ 2

Если вы используете Add, он постепенно изменяет размер внутреннего массива по мере необходимости (удвоение), начиная с начального размера по умолчанию 10 (IIRC). Если вы используете:

var manualFill = new List<int>(fillData.Count);

Я ожидаю, что он радикально изменится (больше не изменится/копирование данных).

Из отражателя AddRange делает это внутренне, а не растет в удвоении:

ICollection<T> is2 = collection as ICollection<T>;
if (is2 != null)
{
    int count = is2.Count;
    if (count > 0)
    {
        this.EnsureCapacity(this._size + count);
        // ^^^ this the key bit, and prevents slow growth when possible ^^^

Ответ 3

Поскольку AddRange проверяет размер добавленных элементов и увеличивает размер внутреннего массива только один раз.

Ответ 4

Разборка из отражателя для метода List AddRange имеет следующий код

ICollection<T> is2 = collection as ICollection<T>;
if (is2 != null)
{
    int count = is2.Count;
    if (count > 0)
    {
        this.EnsureCapacity(this._size + count);
        if (index < this._size)
        {
            Array.Copy(this._items, index, this._items, index + count, this._size - index);
        }
        if (this == is2)
        {
            Array.Copy(this._items, 0, this._items, index, index);
            Array.Copy(this._items, (int) (index + count), this._items, (int) (index * 2), (int) (this._size - index));
        }
        else
        {
            T[] array = new T[count];
            is2.CopyTo(array, 0);
            array.CopyTo(this._items, index);
        }
        this._size += count;
    }
}

Как вы видите, есть некоторые оптимизации, такие как вызов EnsureCapacity() и использование Array.Copy().

Ответ 5

При использовании AddRange коллекция может увеличить размер массива один раз, а затем скопировать значения в него.

Используя оператор foreach, коллекции необходимо увеличить размер коллекции более одного раза.

Увеличение размера thr означает копирование полного массива, требующего времени.

Ответ 6

Это похоже на то, как просить официанта десять раз выпить вам пива и попросить его немедленно принести вам 10 пива.

Как вы думаете, быстрее?)

Ответ 7

Я предполагаю, что это результат оптимизации распределения памяти. для памяти AddRange выделяется только один раз, и в то время как foreach на каждой итерации выполняется перераспределение.

также могут быть некоторые оптимизации в реализации AddRange (например, memcpy)

Ответ 8

Попробуйте инициализировать емкость внутреннего списка перед добавлением вручную элементов:

var manualFill = new List<int>(fillData.Count);

Ответ 9

Это потому, что цикл Foreach добавит все значения, которые цикл получает один раз, и
метод AddRange() соберет все значения, которые он получает как "кусок", и сразу добавит этот фрагмент в указанное место.

Просто понимайте, это похоже на то, что у вас есть список из 10 предметов, которые можно вывести с рынка, что будет быстрее приносить все это за один или все за один раз.

Ответ 10

Расширение AddRange не выполняет итерацию по каждому элементу, но применяет каждый элемент в целом. Оба foreach и .AddRange имеют цель. Addrange выиграет конкурс скорости в вашей текущей ситуации.