Производительность массивов по сравнению со списками

Начиная с List<> массивы использования внутренне, основная производительность должна быть тем же. Две причины, почему Список мог бы быть немного медленнее:

• Для поиска элемента в списке метод Списка называют, который приводит в порядок взгляд в основном массиве. Таким образом, Вам нужен вызов дополнительного метода там. С другой стороны, компилятор мог бы распознать это и оптимизировать "ненужный" вызов далеко.
• компилятор мог бы сделать некоторую специальную оптимизацию, если он знает размер массива, который он не может сделать для списка неизвестной длины. Это могло бы принести некоторое повышение производительности, если у Вас только есть несколько элементов в Вашем списке.

, Чтобы проверить, имеет ли это какое-либо значение для Вас, это является, вероятно, лучшим, корректируют отправленные функции синхронизации к списку размера, который Вы планируете использовать и видеть, как результаты для Вашего особого случая.

Измерения хороши, но Вы собираетесь получить существенно отличающиеся результаты в зависимости от того, что Вы делаете точно в Вашем внутреннем цикле. Измерьте свою собственную ситуацию. Если Вы используете многопоточность, которая один является нетривиальным действием.

[ Видят также этот вопрос ]

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

Результаты:

         for      foreach
Array : 1575ms     1575ms (+0%)
List  : 1630ms     2627ms (+61%)
         (+3%)     (+67%)

(Checksum: -1000038876)

Скомпилированный как Выпуск под VS 2008 SP1. Работая, не отлаживая на Q6600@2.40GHz.NET 3,5 SP1.

Код:

class Program
{
    static void Main(string[] args)
    {
        List<int> list = new List<int>(6000000);
        Random rand = new Random(1);
        for (int i = 0; i < 6000000; i++)
        {
            list.Add(rand.Next());
        }
        int[] arr = list.ToArray();

        int chk = 0;
        Stopwatch watch = Stopwatch.StartNew();
        for (int rpt = 0; rpt < 100; rpt++)
        {
            int len = list.Count;
            for (int i = 0; i < len; i++)
            {
                chk += list[i];
            }
        }
        watch.Stop();
        Console.WriteLine("List/for: {0}ms ({1})", watch.ElapsedMilliseconds, chk);

        chk = 0;
        watch = Stopwatch.StartNew();
        for (int rpt = 0; rpt < 100; rpt++)
        {
            int len = arr.Length;
            for (int i = 0; i < len; i++)
            {
                chk += arr[i];
            }
        }
        watch.Stop();
        Console.WriteLine("Array/for: {0}ms ({1})", watch.ElapsedMilliseconds, chk);

        chk = 0;
        watch = Stopwatch.StartNew();
        for (int rpt = 0; rpt < 100; rpt++)
        {
            foreach (int i in list)
            {
                chk += i;
            }
        }
        watch.Stop();
        Console.WriteLine("List/foreach: {0}ms ({1})", watch.ElapsedMilliseconds, chk);

        chk = 0;
        watch = Stopwatch.StartNew();
        for (int rpt = 0; rpt < 100; rpt++)
        {
            foreach (int i in arr)
            {
                chk += i;
            }
        }
        watch.Stop();
        Console.WriteLine("Array/foreach: {0}ms ({1})", watch.ElapsedMilliseconds, chk);
        Console.WriteLine();

        Console.ReadLine();
    }
}

если Вы просто вытаскиваете единственное значение из любого (не в цикле) тогда, оба делают проверку границ (Вы находитесь в управляемом коде, помнят), это - просто список, делает это дважды. См. примечания позже для того, почему это вероятно не грандиозное предприятие.

, Если Вы используете свое собственное для (международный интервал i = 0; я < x. [Длина/Количество]; я ++), тогда основное отличие следующие:

• Массив:
  • проверка границ удалена
• Списки
  • , проверка границ выполняется

при использовании foreach тогда, основное отличие следующие:

• Массив:
  • никакой объект не выделяется для управления повторением
  • , проверка границ удалена
• Список через переменную, которая, как известно, была Списком.
  • итеративная переменная управления является стеком, выделенным
  • , проверка границ выполняется
• Список через переменную, которая, как известно, была IList.
  • итеративная переменная управления является "кучей", выделенной
  • , проверка границ выполняется, также значения Списков не могут быть изменены во время foreach, тогда как массив может быть.

проверка границ часто не является никаким грандиозным предприятием (особенно, если Вы находитесь на CPU с глубоким конвейером и предсказанием ветвлений - норма для больше всего в эти дни), но только Ваше собственное профилирование может сказать Вам, если это - проблема. Если Вы находитесь в частях Вашего кода, где Вы избегаете выделений "кучи" (хорошими примерами являются библиотеки или в реализациях хэш-кода), тогда обеспечение переменной вводится как Список не, IList избежит той ловушки. Как всегда профиль, если это имеет значение.

Я думаю, что производительность будет весьма схожа. Издержки, которые включены при использовании Списка по сравнению с Массивом, по моему скромному мнению, когда Вы добавляете объекты к списку, и когда список должен увеличить размер массива, который это использует внутренне, когда способность массива достигнута.

предположим у Вас есть Список со Способностью 10, тогда Список увеличится, это - способность, как только Вы хотите добавить 11-й элемент. Можно уменьшить влияние производительности путем инициализации Способности списка к количеству объектов, которые это будет содержать.

, Но, чтобы выяснить, выполняет ли итерация по Списку с такой скоростью, как итерации по массиву, почему Вы не сравниваете ее?

int numberOfElements = 6000000;

List<int> theList = new List<int> (numberOfElements);
int[] theArray = new int[numberOfElements];

for( int i = 0; i < numberOfElements; i++ )
{
    theList.Add (i);
    theArray[i] = i;
}

Stopwatch chrono = new Stopwatch ();

chrono.Start ();

int j;

 for( int i = 0; i < numberOfElements; i++ )
 {
     j = theList[i];
 }

 chrono.Stop ();
 Console.WriteLine (String.Format("iterating the List took {0} msec", chrono.ElapsedMilliseconds));

 chrono.Reset();

 chrono.Start();

 for( int i = 0; i < numberOfElements; i++ )
 {
     j = theArray[i];
 }

 chrono.Stop ();
 Console.WriteLine (String.Format("iterating the array took {0} msec", chrono.ElapsedMilliseconds));

 Console.ReadLine();

В моей системе; итерация по массиву заняла 33 мс; итерация по списку заняла 66 мс.

Честно говоря, я не ожидал, что изменение будет так очень. Так, я поместил свое повторение в цикл: теперь, я выполняю оба повторения 1000 раз. Результаты:

итерация Списка заняла 67 146 мс, выполняя итерации массива, взял 40 821 msec

Теперь, изменение больше не является настолько большим, но все еще...

Поэтому я запустил Отражатель.NET и метода get индексатора класса Списка, похож на это:

public T get_Item(int index)
{
    if (index >= this._size)
    {
        ThrowHelper.ThrowArgumentOutOfRangeException();
    }
    return this._items[index];
}

, Как Вы видите при использовании индексатора Списка Список выполняет проверку, не выходите ли Вы из границ внутреннего массива. Эта дополнительная проверка идет со стоимостью.

Действительно при выполнении некоторых сложных вычислений в цикле тогда производительность индексатора массива по сравнению с индексатором списка может быть столь незначительно маленькой, что в конечном счете, это не имеет значения.