Почему 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
c# .net c#-4.0

10 ответов:

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

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

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

80

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

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

17

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

6

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

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

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

5

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

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

4

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

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

2

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

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

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

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

1

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

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

Addrange Vs Foreach

0