Самый быстрый способ конвертировать IEnumerable <T>в список <T>в C # - PullRequest
Новая
       49

Самый быстрый способ конвертировать IEnumerable <T>в список <T>в C #

0 голосов
/ 22 января 2019

В C #, какой самый быстрый способ создания и заполнения Списка с использованием IEnumberable с точки зрения времени, необходимого для написания кода?Что с точки зрения времени, необходимого для выполнения?

Моя первая мысль была такой: 

List<int> list = new List<int>();
foreach(int number in iterator)
    list.Add(number);

Есть ли более быстрый способ?

1 Ответ

0 голосов
/ 22 января 2019

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

Создать пустое List<T> и заполнить его 

List<int> list = new List<int>(); // C
foreach(int i in iterator)
{
    list.Add(i); //n*C
}

Как вы можете видеть, этот подход занимает n * C + C времени, поэтому, если вы пренебрегаете C, сложность будет O (n).

Создать List<T> на основе другого IEnumerable<T>

List<int> list = new List<int>(iterator);

однако, есть небольшая разница в типе итератора:

  1. если итератор ICollection<T>

    var array = new T [ICollection.Count] // C ICollection.CopyTo (array) // по MSDN O (n)

  2. если итератор равен IEnumerable<T>, то же самое, что создание пустого элемента и добавление элемента по элементу

Итак, если вы проанализируете сложность, вы не сможете избежать сложности O (n).

НО ...

Существует одна оговорка с ростом и вместимостью List<T>, которая может повлиять на производительность. По умолчанию емкость List<T> равна 4, и если вы добавите более 4 элементов к List<T>, будет выделен новый базовый массив, в два раза больше текущего размера, и элементы будут скопированы ... этот процесс будет повторяться снова, когда мы достигаем емкости List<T>. Вы можете представить, сколько у вас может быть ненужного копирования. Для предотвращения этого лучше всего заранее инициализировать List<T> с емкостью или использовать List<T>(ICollection<T>) ctor. 

// benchmark example
var enumerable = Enumerable.Repeat(1, 1000000);
var collection = enumerable.ToList();

Stopwatch st = Stopwatch.StartNew();
List<int> copy1 = new List<int>(enumerable);
Console.WriteLine(st.ElapsedMilliseconds);

st = Stopwatch.StartNew();
List<int> copy2 = new List<int>(collection);
Console.WriteLine(st.ElapsedMilliseconds);
...