День 1164. #ЗаметкиНаПолях #AsyncTips
Неизменяемые списки
Задача: нужна структура данных с возможностью индексирования, которая изменяется не слишком часто и допускает безопасные обращения из нескольких потоков.
Решение
Список — структура данных общего назначения, которая может использоваться для хранения разнообразных данных состояния приложения. Неизменяемые списки поддерживают индексирование, однако вы должны учитывать их характеристики быстродействия. Они не должны рассматриваться как тривиальная замена для List<T>.
ImmutableList<T> из пространства имён System.Collections.Immutable поддерживает примерно те же методы, что и List<T>:
var list = ImmutableList<int>.Empty;
list = list.Insert(0, 13);
list = list.Insert(0, 7);
// Выводит "7", затем "13".
foreach (int item in list)
Console.WriteLine(item);
list = list.RemoveAt(1);
ImmutableList<T> не имеет открытого конструктора; вы начинаете с извлечения пустого ImmutableList<T> с помощью ImmutableList<T>.Empty. Затем можете вызвать методы, такие как Add и AddRange, для заполнения коллекции. Обратите внимание, что эти методы возвращают новый объект. Когда вы добавляете или удаляете элементы из неизменяемого списка, создается копия исходного списка с добавленными или удаленными элементами, а исходный список не изменяется.
Во внутренней реализации неизменяемого списка используется двоичное дерево, чтобы экземпляры могли максимизировать объем памяти, используемый совместно с другими экземплярами. В результате для некоторых распространенных операций существуют различия в быстродействии.
Быстродействие List<T>:
Add ~ O(1)
Insert - O(N)
RemoveAt - O(N)
Item[индекс] - O(1)
Быстродействие ImmutableList<T> - O(log N) для всех операций, а не O(1), как можно было бы ожидать. Если вы замените List<T> на ImmutableList<T> в существующем коде, следует учесть, как ваши алгоритмы обращаются к элементам коллекции.
Например, следует использовать foreach вместо for там, где это возможно. Цикл foreach по ImmutableList<T> выполняется за время O(N), тогда как цикл for по той же коллекции выполняется за время O(N * log N).
ImmutableList<T> — хорошая структура данных общего назначения, но из-за различий в быстродействии вы не можете бездумно заменить ей все List<T>. List<T> часто используется по умолчанию — именно эту структуру данных следует использовать, если только у вас нет веских причин для выбора другой коллекции. Коллекция ImmutableList<T> не настолько распространена; следует тщательно проанализировать другие неизменяемые коллекции и выбрать ту, которая лучше всего подходит для вашей ситуации.
В документации ImmutableList<T>.Builder в MSDN рассматривается эффективный способ заполнения неизменяемых списков.
См. также Неизменяемые стеки и очереди
Источник: Стивен Клири “Конкурентность в C#”. 2-е межд. изд. — СПб.: Питер, 2020. Глава 9.
