Методы расширения ToArray и ToList — удобный способ быстро преобразовать перечисляемую последовательность (например, Linq-запрос) в массив или в список. Однако, в них есть кое-что беспокоящее меня: оба эти метода очень неэффективны, если они не знают количество элементов в последовательности (что почти всегда происходит, когда вы используете их в Linq-запросе). Давайте сперва рассмотрим метод ToArray (ToList имеет несколько отличий, но принцип практически такой же).
В своей основе, ToArray берет последовательность и возвращает массив, который содержит все элементы исходной последовательности. Если последовательность реализовывает интерфейс ICollection<T>, ToArray использует свойство Count для размещения в памяти массива правильного размера и копирует в него элементы последовательности. Например, преобразуем в массив список пользователей:
List<User> users = GetUsers();
User[] array = users.ToArray();
В этом случае ToArray довольно эффективен. Давайте изменим код так, чтобы из списка пользователей извлекались только их имена и преобразовались в массив:
List<User> users = GetUsers();
string[] array = users.Select(u => u.Name).ToArray();
Теперь, аргументом для ToArray является тип IEnumerable<User>, возвращенный методом Select. IEnumerable<User> не реализовывает интерфейс ICollection<User>, поэтому ToArray не знает количества элементов и не может разместить в памяти массив подходящего размера. Он делает следующее:
- Сначала в памяти размещается массив маленького размера (4 элемента в текущей реализации)
- В массив копируются элементы, пока он не заполнится
- Если в источнике больше нет элементов, производится переход к п. 7
- В противном случае, в памяти размещается новый массив, в два раза больше предыдущего
- Элементы из предыдущего массива копируются в новый
- Производится переход к п. 2 и все повторяется
- Если в результате массив оказался больше чем количество элементов, он усекается: в памяти размещается новый массив с правильным размером и в него копируются элементы
- Полученный массив возвращается методом
Если в источнике всего несколько элементов, то этот алгоритм проходит вполне безболезненно, но для очень большого числа элементов он становится довольно неэффективным из-за большого числа выделений памяти и копирования элементов.
Раздражает то, что в большинстве случаем мы знаем исходное количество элементов! В примере выше, мы используем Select, который не меняет количество элементов в последовательности, и мы знаем, что их остается такое же количество. Но ToArray об этом не знает, потому что для него этой информации нет. Был бы у нас способ предоставить ему это самостоятельно…
Хорошо, на самом деле, сделать это довольно легко: нужно всего лишь написать свой метод расширения, который принимает количество элементов в качестве параметра. Он может выглядеть вот так:
public static TSource[] ToArray<TSource>(this IEnumerable<TSource> source, int count)
{
if (source == null) throw new ArgumentNullException("source");
if (count < 0) throw new ArgumentOutOfRangeException("count");
var array = new TSource[count];
int i = 0;
foreach (var item in source)
{
array[i++] = item;
}
return array;
}
Теперь мы можем оптимизировать наш пример таким образом:
List<User> users = GetUsers();
string[] array = users.Select(u => u.Name).ToArray(users.Count);
Обратите внимание, что если вы передадите меньшее количество элементов, чем на самом деле, вы получите IndexOutOfRangeException. Вы обязаны предоставить методу правильное число.
Итак, какую производительность мы теперь получим? По моим тестам эта версия ToArray приблизительно в два раза быстрее стандартной версии для больших последовательностей (тесты запускались на 1,000,000 элементов). Довольно неплохо!
Заметьте, что мы можем улучшить метод ToList похожим способом, используя конструктор класса List<T>, который позволяет задать начальную емкость списка:
public static List<TSource> ToList<TSource>(this IEnumerable<TSource> source, int count)
{
if (source == null) throw new ArgumentNullException("source");
if (count < 0) throw new ArgumentOutOfRangeException("count");
var list = new List<TSource>(count);
foreach (var item in source)
{
list.Add(item);
}
return list;
}
В этом случае наблюдается не такой большой рост производительности, как в случае с ToArray (примерно 25% вместо 50%), вероятно из-за того, что список не нужно подвергать усечению.
Очевидно, что такую же оптимизацию можно применить и к методу ToDictionary, поскольку класс Dictionary<TKey, TValue> также предоставляет конструктор с указанием начальной емкости словаря.
Улучшенные версии методов ToArray and ToList доступны в моей Linq.Extras библиотеке, которая также предоставляет много других полезных методов для работы с последовательностями и с коллекциями.
Автор: Charoplet
