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

Question

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

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

Кто-нибудь на самом деле измерял это? будет ли повторение 6M раз по списку занимать то же время, что и массив?

Answer 1

Очень легко измерить ...

В небольшом количестве кодов обработки с обратной связью , где я знаю, что длина фиксирована Я использую массивы для этого крошечного кусочка микро-оптимизации; массивы могут быть незначительно быстрее , если вы используете индексатор / для формы - но IIRC полагает, что это зависит от типа данных в массиве. Но если вам не нужно для микрооптимизации, сохраняйте простоту и используйте List<T> и т. Д.

Конечно, это применимо, только если вы читаете все данные; словарь будет быстрее для поиска по ключу.

Вот мои результаты с использованием "int" (второе число - контрольная сумма, чтобы убедиться, что все они проделали одинаковую работу):

(отредактировано для исправления ошибки)

List/for: 1971ms (589725196)
Array/for: 1864ms (589725196)
List/foreach: 3054ms (589725196)
Array/foreach: 1860ms (589725196)

на основе испытательного стенда:

using System;
using System.Collections.Generic;
using System.Diagnostics;
static class Program
{
    static void Main()
    {
        List<int> list = new List<int>(6000000);
        Random rand = new Random(12345);
        for (int i = 0; i < 6000000; i++)
        {
            list.Add(rand.Next(5000));
        }
        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++)
        {
            for (int i = 0; i < arr.Length; 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.ReadLine();
    }
}

Answer 2

Краткий ответ:

Более подробный ответ Вы найдете по следующей ссылке: https://stackoverflow.com/a/29263914/4423545

Answer 3

Я думаю, что производительность будет очень похожа. Служебная нагрузка, которая возникает при использовании List против Array, - IMHO, когда вы добавляете элементы в список, и когда список должен увеличивать размер используемого им массива, когда достигается емкость массива.

Предположим, у вас есть список с вместимостью 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 раз. Результаты:

повторение списка заняло 67146 мс итерация массива заняла 40821 мсек

Теперь, вариация уже не так велика, но все же ...

Поэтому я запустил .NET Reflector, и получатель индексатора класса List выглядит следующим образом:

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

Как вы можете видеть, когда вы используете индексатор List, List выполняет проверку, не выходите ли вы за пределы внутреннего массива. Эта дополнительная проверка поставляется с оплатой.

Answer 4

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

Если вы используете свой собственный для (int int i = 0; i

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

Если вы используете foreach, то ключевое отличие заключается в следующем:

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

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

Answer 5

[ См. Также этот вопрос ]

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

Результаты:

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

(Checksum: -1000038876)

Скомпилировано как выпуск под VS 2008 SP1. Работает без отладки на Q6600 @ 2,40 ГГц, .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();
    }
}

Answer 6

Не пытайтесь увеличить емкость, увеличив количество элементов.

Производительность

List For Add: 1ms
Array For Add: 2397ms

---

    Stopwatch watch;
        #region --> List For Add <--

        List<int> intList = new List<int>();
        watch = Stopwatch.StartNew();
        for (int rpt = 0; rpt < 60000; rpt++)
        {
            intList.Add(rand.Next());
        }
        watch.Stop();
        Console.WriteLine("List For Add: {0}ms", watch.ElapsedMilliseconds);
        #endregion

        #region --> Array For Add <--

        int[] intArray = new int[0];
        watch = Stopwatch.StartNew();
        int sira = 0;
        for (int rpt = 0; rpt < 60000; rpt++)
        {
            sira += 1;
            Array.Resize(ref intArray, intArray.Length + 1);
            intArray[rpt] = rand.Next();

        }
        watch.Stop();
        Console.WriteLine("Array For Add: {0}ms", watch.ElapsedMilliseconds);

        #endregion

Answer 7

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

Answer 8

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

Answer 9

Я беспокоился, что тесты, опубликованные в других ответах, все равно оставят компилятору возможность оптимизировать, устранить или объединить циклы, поэтому я написал такую, которая:

• Использованы непредсказуемые входы (случайные)
• Запускает вычисленный результат с выводом на консоль
• Изменяет входные данные при каждом повторении

В результате прямой массив работает примерно на 250% быстрее, чем доступ к массиву, заключенному в IList:

• 1 миллиард обращений к массиву: 4000 мс
• 1 миллиард обращений к списку: 10000 мс
• 100 миллионов обращений к массиву: 350 мс
• 100 миллионов обращений к списку: 1000 мс

Вот код:

static void Main(string[] args) {
  const int TestPointCount = 1000000;
  const int RepetitionCount = 1000;

  Stopwatch arrayTimer = new Stopwatch();
  Stopwatch listTimer = new Stopwatch();

  Point2[] points = new Point2[TestPointCount];
  var random = new Random();
  for (int index = 0; index < TestPointCount; ++index) {
    points[index].X = random.NextDouble();
    points[index].Y = random.NextDouble();
  }

  for (int repetition = 0; repetition <= RepetitionCount; ++repetition) {
    if (repetition > 0) { // first repetition is for cache warmup
      arrayTimer.Start();
    }
    doWorkOnArray(points);
    if (repetition > 0) { // first repetition is for cache warmup
      arrayTimer.Stop();
    }

    if (repetition > 0) { // first repetition is for cache warmup
      listTimer.Start();
    }
    doWorkOnList(points);
    if (repetition > 0) { // first repetition is for cache warmup
      listTimer.Stop();
    }
  }

  Console.WriteLine("Ignore this: " + points[0].X + points[0].Y);
  Console.WriteLine(
    string.Format(
      "{0} accesses on array took {1} ms",
      RepetitionCount * TestPointCount, arrayTimer.ElapsedMilliseconds
    )
  );
  Console.WriteLine(
    string.Format(
      "{0} accesses on list took {1} ms",
      RepetitionCount * TestPointCount, listTimer.ElapsedMilliseconds
    )
  );

}

private static void doWorkOnArray(Point2[] points) {
  var random = new Random();

  int pointCount = points.Length;

  Point2 accumulated = Point2.Zero;
  for (int index = 0; index < pointCount; ++index) {
    accumulated.X += points[index].X;
    accumulated.Y += points[index].Y;
  }

  accumulated /= pointCount;

  // make use of the result somewhere so the optimizer can't eliminate the loop
  // also modify the input collection so the optimizer can merge the repetition loop
  points[random.Next(0, pointCount)] = accumulated;
}

private static void doWorkOnList(IList<Point2> points) {
  var random = new Random();

  int pointCount = points.Count;

  Point2 accumulated = Point2.Zero;
  for (int index = 0; index < pointCount; ++index) {
    accumulated.X += points[index].X;
    accumulated.Y += points[index].Y;
  }

  accumulated /= pointCount;

  // make use of the result somewhere so the optimizer can't eliminate the loop
  // also modify the input collection so the optimizer can merge the repetition loop
  points[random.Next(0, pointCount)] = accumulated;
}

Answer 10

Вот тот, который использует словари, IEnumerable:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

static class Program
{
    static void Main()
    {
        List<int> list = new List<int>(6000000);

        for (int i = 0; i < 6000000; i++)
        {
                list.Add(i);
        }
        Console.WriteLine("Count: {0}", list.Count);

        int[] arr = list.ToArray();
        IEnumerable<int> Ienumerable = list.ToArray();
        Dictionary<int, bool> dict = list.ToDictionary(x => x, y => true);

        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++)
        {
            for (int i = 0; i < arr.Length; 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 Ienumerable)
            {
                chk += i;
            }
        }

        Console.WriteLine("Ienumerable/for: {0}ms ({1})", watch.ElapsedMilliseconds, chk);

        chk = 0;
        watch = Stopwatch.StartNew();
        for (int rpt = 0; rpt < 100; rpt++)
        {
            foreach (int i in dict.Keys)
            {
                chk += i;
            }
        }

        Console.WriteLine("Dict/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);



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

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

        Console.ReadLine();
    }
}