Почему 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. Кто-нибудь знает почему?

10   53  

10 ответа:

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

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

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

если вы используете 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 ^^^

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

на декомпиляцию от рефлектора для список метод 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() и использование массива.Копия.)(

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

С помощью foreach оператор коллекции необходимо увеличить размер коллекции более одного раза.

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

Это все равно, что попросить официанта принести вам одно пиво десять раз и попросить его принести вам 10 пива сразу.

Как вы думаете, что быстрее :)

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

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

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

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

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

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

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

подробнее об этом здесь:

Addrange Vs Foreach