Как правильно выбрать коллекцию в .NET?
.NET Framework содержит множество классов коллекций. Это может затруднить решение, когда какой использовать. Группировка их вместе на основе их свойств может значительно облегчить выбор для конкретного сценария. Именно это мы и сделаем в этой статье. Так же рекомендуем прочитать статью где мы сравнивали коллекции IEnumerable и IQueryable
.NET Collection Class - Общие коллекции
Большинство классов коллекции размещены в пространствах имен System.Collections и System.Collections.Generic, но многие из них также размещены в других пространствах имен. Хотя в большинстве случаев следует рассматривать только коллекции в пространстве имен System.Collections.Generic.
Все коллекции в System.Collections не являются универсальными, они возникли в то время, когда генерики были добавлены в C # с выпуском .NET Framework 2.0 и C # 2.0. Если вы не поддерживаете легаси-код, вам следует избегать их, поскольку они не обеспечивают безопасность типов и имеют наихудшую производительность по сравнению с их общими аналогами при использовании с типами значений.
Коллекции в других пространствах имен являются узкоспециализированными для конкретных сценариев и обычно не применимы к коду из других проблемных доменов. Например класс System.Dynamic.ExpandoObject реализует несколько интерфейсов коллекции, но в первую очередь предназначен для реализации динамического связывания.
Даже если рассматривать только общие коллекции в пространстве имен System.Collections.Generic, выбор может показаться огромным.
К счастью, коллекции могут быть легко сгруппированы в несколько категорий на основе интерфейсов, которые они реализуют. Они определяют, какие операции поддерживаются коллекцией и, следовательно, в каких сценариях их можно использовать.
Общий интерфейс для коллекций - интерфейс ICollection <T>. Он наследуется от интерфейса IEnumerable <T>, который предоставляет средства для итерации элементов коллекции:
IEnumerable<int> enumerable = new List<int>() { 1, 2, 3, 4, 5 };
foreach(var item in enumerable)
{
// process items
}
Интерфейс ICollection <T> добавляет свойство Count и методы для изменения коллекции:
ICollection<int> collection = new List<int>() { 1, 2, 3, 4, 5 };
var count = collection.Count;
collection.Add(6);
collection.Remove(2);
collection.Clear();
Авторы Base Class Library (BCL) считают, что этого достаточно для реализации простой колекции. Три разничных интерфейса по-разному расширяют этот базовый интерфейс, обеспечивая дополнительные функциональные возможности.
Lists
Интерфейс IList <T> описывает коллекции с элементами, доступ к которым можно получить по их индексу. Для этого он добавляет индексатор для получения и записи значения:
IList<int> list = new List<int> { 1, 2, 3, 4, 5 };
var item = list[2]; // item = 3
list[2] = 6; // list = { 1, 2, 6, 4, 5 }
Он также включает методы для вставки и удаления значения по определенному индексу:
list.Insert(2, 0); // list = { 1, 2, 0, 6, 4, 5 }
list.RemoveAt(2); // list = { 1, 2, 6, 4, 5 }
Наиболее часто используемый класс, реализующий интерфейс IList<T>, - это List<T>.
Это будет прекрасно работать в большинстве сценариев, но есть и другие реализации, доступные для более специфических требований. Например, SynchronizedCollection<T> имеет встроенный объект синхронизации, который можно использовать для обеспечения его поточной безопасности.
Sets
Интерфейс ISet<T> описывает набор уникальных элементов, которые не гарантируют сохранение их порядка в списке. Метод Add все еще можно использовать для добавления отдельных элементов в коллекцию:
ISet<int> set = new HashSet<int> { 1, 2, 3, 4, 5 };
var added = set.Add(0);
Тем не менее, он будет добавлять элемент в коллекцию, только если он еще не присутствует в нем. Возвращаемое значение будет указывать, был ли элемент добавлен.
Остальные методы интерфейса реализуют различные стандартные операции над множествами из теории множеств. Следующие методы модифицируют существующую коллекцию:
ISet<int> set = new HashSet<int> { 1, 2, 3, 4, 5 };
set.UnionWith(new[] { 5, 6 }); // set = { 1, 2, 3, 4, 5, 6 }
set.IntersectWith(new[] { 3, 4, 5, 6, 7 }); // set = { 3, 4, 5, 6 }
set.ExceptWith(new[] { 6, 7 }); // set = { 3, 4, 5 }
set.SymmetricExceptWith(new[] { 4, 5, 6 }); // set = { 3, 6 }
Остальные только выполняют проверки над колекцией и возвращают логическое значение (bool):
ISet<int> set = new HashSet<int> { 1, 2, 3, 4, 5 };
var isSubset = set.IsSubsetOf(new[] { 1, 2, 3, 4, 5 }); // = true
var isProperSubset = set.IsProperSubsetOf(new[] { 1, 2, 3, 4, 5 }); // = false
var isSuperset = set.IsSupersetOf(new[] { 1, 2, 3, 4, 5 }); // = true
var isProperSuperset = set.IsProperSupersetOf(new[] { 1, 2, 3, 4, 5 }); // = false
var equals = set.SetEquals(new[] { 1, 2, 3, 4, 5 }); // = true
var overlaps = set.Overlaps(new[] { 5, 6 }); // = true
Самая базовая реализация ISet<T> - это класс HashSet<T>. Если вы хотите, чтобы элементы в наборе были отсортированы, вы можете использовать SortedSet<T>.
Dictionaries
IDictionary<TKey, TValue> - это третий интерфейс, расширяющий интерфейс ICollection<T>. В отличие от предыдущих двух, этот предназначен для хранения пар ключ-значение вместо отдельных значений, т.е. он использует KeyValuePair<TKey, TValue> в качестве универсального параметра в ICollection<T>
IDictionary<string, string> dictionary = new Dictionary<string, string>
{
["one"] = "odin",
["two"] = "dva",
["three"] = "tri",
["four"] = "4itiri",
["five"] = "pyat"
};
var value = dictionary["two"];
dictionary["zero"] = "0" ;
Для добавления пары в коллекцию можно использовать метод Add. В отличие от предыдущего метода, он выдаст исключение, если ключ уже находится в коллекции.
dictionary.Add("zero", "zero");
Конечно, есть методы для проверки наличия ключа в коллекции и удаления существующей пары на основе значения ключа:
var contains = dictionary.ContainsKey("two");
var removed = dictionary.Remove("two");
Последний вернет значение, указывающее, был ли удален ключ, так как его может не быть в словаре.
Есть также свойства, доступные для извлечения отдельных коллекций ключей и значений:
ICollection<int> keys = dictionary.Keys;
ICollection<string> values = dictionary.Values;
Для сценариев без особых излишеств класс Dictionary<TKey, TValue> является готовой реализацией интерфейса IDictionary<TKey, TValue>.
Для сортировки ключей доступны две разные реализации (SortedDictionary<TKey, TValue> и SortedList<TKey, TValue>), каждая из которых имеет свои преимущества и недостатки.
Многие другие реализации интерфейса доступны в Base Class Library .
Queue и Stack
Стоит упомянуть два класса коллекций, которые, в отличие от других, не реализуют ни один из специализированных интерфейсов, полученных из интерфейса ICollection<T>.
Класс Queue<T> реализует принцип FIFO (first in, first out) - первым пришел, первым вышел.
Прямо достучатся можно только к 1 обэекту в этой колекции, к тому который находится в ней дольше всего. Методы добавления и удаления элемента:
var queue = new Queue<int>(new[] { 1, 2, 3, 4, 5 });
queue.Enqueue(6);
var dequeuedItem = queue.Dequeue();
Существует также метод Peek, который возвращает тот же элемент, что и метод Dequeue, но оставляет его в коллекции:
var peekedItem = queue.Peek();
Класс Stack<T> похож на класс Queue<T>, но он реализует принцип LIFO (последний пришел, первый вышел). Единственный элемент, который непосредственно доступен в этой коллекции, - это тот, который был добавлен совсем недавно. Пример:
var stack = new Stack<int>(new[] { 1, 2, 3, 4, 5 });
stack.Push(6);
var poppedItem = stack.Pop();
var peekedItem = stack.Peek();
Потокобезопасность
Обычные generic классы в Base Class Library имеют один очень важный недостаток, если вам нужно использовать их в многопоточных приложениях: они не являются поточно-ориентированными или по крайней мере, не полностью потокобезопасные.
Хотя большинство из них поддерживает несколько одновременных чтений, операции чтения по-прежнему не являются поточно-ориентированными, так как одновременный доступ к записи не разрешен.
Как только коллекция должна быть изменена, любой доступ к ней из нескольких потоков должен быть синхронизирован.
Простейший подход к реализации такой синхронизации потока включает использование оператора блокировки с общим объектом синхронизации:
public class DictionaryWithLock<TKey, TValue>
{
private readonly object syncObject = new object();
private readonly Dictionary<TKey, TValue> dictionary;
public DictionaryWithLock()
{
dictionary = new Dictionary<TKey, TValue>();
}
public TValue this[TKey key]
{
get
{
lock (syncObject)
{
return dictionary[key];
}
}
set
{
lock (syncObject)
{
dictionary[key] = value;
}
}
}
public void Add(TKey key, TValue value)
{
lock (syncObject)
{
dictionary.Add(key, value);
}
}
}
Не смотря на то чтоэтот подход будет работать, он не оптимален.
Весь доступ к внутреннему словарю полностью сериализован, то есть следующая операция может начаться только после завершения предыдущей. Поскольку коллекция допускает несколько одновременных считывателей, она может значительно повысить производительность, если она учитывает это и ограничивает только одновременный доступ для операций записи.
Base Class Library содержит класс ReaderWriterLockSlim, который можно использовать для реализации этой конкретной функции относительно простым способом:
public class DictionaryWithReaderWriterLock<TKey, TValue>
{
private readonly ReaderWriterLockSlim dictionaryLock = new ReaderWriterLockSlim();
private readonly Dictionary<TKey, TValue> dictionary;
public DictionaryWithReaderWriterLock()
{
dictionary = new Dictionary<TKey, TValue>();
}
public TValue this[TKey key]
{
get
{
dictionaryLock.EnterReadLock();
try
{
return dictionary[key];
}
finally
{
dictionaryLock.ExitReadLock();
}
}
set
{
dictionaryLock.EnterWriteLock();
try
{
dictionary[key] = value;
}
finally
{
dictionaryLock.ExitWriteLock();
}
}
}
public void Add(TKey key, TValue value)
{
dictionaryLock.EnterWriteLock();
try
{
dictionary.Add(key, value);
}
finally
{
dictionaryLock.ExitWriteLock();
}
}
}
В зависимости от типа синхронизируемой операции используются два разных метода блокировки: чтение или запись.
Класс разрешит любое количество одновременных операций чтения. С другой стороны, блокировка записи будет эксклюзивной и не позволит одновременно использовать любой другой доступ для чтения или записи.
Concurrent Collections
Даже с использованием примитивов синхронизации, предоставляемых C # и .NET Framework, написание кода синхронизации является достаточно сложным. Оба класса-оболочки которые описаны выше реализуют синхронизацию только для небольшого подмножества операций.
Параллельные коллекции в пространстве имен System.Collections.Concurrent покрывают все кейсы. Они предоставляют поточно-ориентированные реализации интерфейсов коллекции.
Исключениями являются классы ConcurrentQueue <T> и ConcurrentStack <T>, которые предоставляют независимые реализации, аналогичные их непараллельным аналогам Queue <T> и Stack <T>, поскольку в .NET Framework нет подходящих интерфейсов для реализации.
Классы concurrent коллекции можно безопасно использовать в многопоточных приложениях. У них даже есть дополнительные члены в дополнение к тем из реализованных интерфейсов, которые могут оказаться полезными в многопоточных сценариях.
Тем не менее, при использовании этих коллекций есть небольшие предостережения. Например, класс ConcurrentDictionary <TKey, TValue> включает методы, которые не являются полностью атомарными. Перегрузки методов GetOrAdd и AddOrUpdate, которые принимают делегатов в качестве параметров, вызовут этих делегатов вне блокировок синхронизации.
давайте расмотрим пример для того что б понять о чем мы говорим
var resource = concurrentDictionary.GetOrAdd(newKey, key => ExpensiveResource.Create(key));
Такие вызовы методов распространены, когда словарь используется в качестве кэша для экземпляров классов, которые могут быть дорогостоящими в создании, но могут безопасно использоваться из нескольких потоков.
Не зная подробностей о том, как реализован ConcurrentDictionary<TKey, TValue>, можно предположить, что эта строка кода либо возвратит экземпляр из кэша, либо создаст один новый экземпляр, используя предоставленный делегат, когда в экземпляре еще нет соответствующего экземпляра толковый словарь. Затем он должен вернуть этот экземпляр на все последующие запросы.
Однако, поскольку делегат вызывается вне блокировки синхронизации, он может быть вызван из нескольких разных потоков, если его еще нет в словаре, когда достигается эта строка кода.
Хотя в итоге в словаре будет храниться только один из созданных экземпляров, может быть проблема в том, что было создано несколько экземпляров. По крайней мере, это повлияет на производительность, если создание займет много времени. Если метод фабрики должен вызываться только один раз для определенного ключа, вам нужно будет самостоятельно написать дополнительный код синхронизации.
Важно всегда тщательно читать документацию для всех одновременных классов коллекций, чтобы знать о таких деталях реализации.
Immutable Collections
Immutable (неизменяемые) коллекции не включены в библиотеку базовых классов. Чтобы использовать их в проекте должен быть установлен пакет NuGet System.Collections.Immutable.
Они используют другой подход к созданию коллекций поточно-ориентированных. Вместо использования синхронизирующих блокировок, как это делают параллельные коллекции, неизменяемые коллекции не могут быть изменены после их создания. Это автоматически делает их безопасными для использования в многопоточных сценариях, поскольку другой поток не может изменить их и сделать состояние несовместимым.
Это фундаментальное проектное решение влияет на API классов неизменяемой коллекции. У них даже нет общественных конструкторов. Есть два других способа создать новый экземпляр:
Обычную коллекцию можно преобразовать в неизменяемую, используя метод расширения:
var immutableList = new[] { 1, 2, 3, 4, 5 }.ToImmutableList();
Пустую коллекцию, к которой можно доступится через статическое свойство, можно изменить, добавив в нее новые элементы:
var immutableList = ImmutableList<int>.Empty.AddRange(new[] { 1, 2, 3, 4, 5 });
Все операции, которые обычно изменяют коллекцию, возвращают новый экземпляр. Важно помнить, что возвращаемое значение должно использоваться вместо исходного экземпляра:
immutableList = immutableList.Add(6);
То, что каждый метод возвращает новый экземпляр одного и того же класса, облегчает объединение нескольких вызовов методов:
immutableList = immutableList
.Add(6)
.Add(7)
.Add(8);
Однако такого подхода следует избегать всякий раз, когда это возможно, потому что каждый вызов метода в такой цепочке создает новый экземпляр коллекции. Хотя неизменяемые коллекции реализованы таким образом, чтобы при создании нового экземпляра можно было использовать как можно больше исходной коллекции, некоторые выделения памяти все еще требуются. Это означает больше работы для сборщика мусора.
Лучший способ минимизировать эту проблему - использовать методы, которые могут выполнить необходимые изменения за один вызов. Приведенную выше цепочку вызовов методов можно заменить, например, следующим единственным вызовом метода:
immutableList = immutableList.AddRange(new[] { 6, 7, 8 });
К сожелению специализированные методы не доступны для всех типов сложных модификаций. Например, нет единого метода, доступного для добавления и удаления определенных элементов, как показано ниже:
immutableList = immutableList
.Add(6)
.Remove(2);
В таких случаях вместо этого может использоваться Builder:
var builder = immutableList.ToBuilder();
builder.Add(6);
builder.Remove(2);
immutableList = builder.ToImmutable();
Метод ToBuilder создаст builder для неизменяемой коллекции, который будет реализовывать интерфейс соответствующей изменяемой коллекции. Его внутренняя структура памяти будет по-прежнему соответствовать одной неизменной коллекции, но операции изменят один и тот же экземпляр, вместо того, чтобы всегда создавать новый. Только при вызове метода ToImmutable экземпляр будет снова имутабельным. Это позволит максимально сократить объем работы сборщика мусора.
Итак, когда следует использовать Immutable коллекции вместо обычных или Concurrent коллекций?
Типичным случаем использования являются многопоточные приложения, особенно когда поток не должен иметь доступ к последнему состоянию коллекции и может использовать потенциально устаревший неизменный экземпляр, который был первоначально передан ему. В этом случае неизменяемые коллекции могут обеспечивать более высокую производительность, несмотря на дополнительную работу для сборщика мусора, поскольку не требуются блокировки синхронизации.
Если приложению необходимо отменить операции над коллекциями, может иметь смысл использовать неизменяемые коллекции даже в однопоточных сценариях. Снимки предыдущих состояний являются побочным продуктом неизменяемых коллекций и не требуют дополнительных ресурсов для создания. Они могут, например, храниться в стеке, чтобы отменить последнее изменение:
snapshots.Push(immutableList);
immutableList = immutableList.Add(6);
immutableList = snapshots.Pop(); // undo: revert list to previous state
To achieve the same functionality with mutable collections, copies must be created before each modification:
snapshots.Push(list.ToList());
list.Add(6);
list = snapshots.Pop();
Мало того, что создание копий занимает много времени, копии также требуют больше памяти, чем их неизменные аналоги. Копии изменяемых коллекций не разделяют память между ними, в отличие от неизменяемых коллекций, которые часто делятся большими частями, когда они были созданы с помощью модификаций.
Итоги
Выбирая коллекцию для использования в своем коде, всегда начинайте с размышлений о том, какие операции вам нужно будет выполнить с этой коллекцией. Исходя из этого, вы можете выбрать наиболее подходящий интерфейс коллекции.
Если у вас нет каких-либо особых требований, используйте реализацию из пространства имен System.Collections.Generic. Если вы пишете многопоточное приложение и вам нужно изменить коллекцию из нескольких потоков, выберите вместо этого параллельную реализацию одного и того же интерфейса. Рассмотрите имутабельные коллекции, если их поведение и производительность лучше всего соответствуют вашим требованиям.