Все мы пользуемся стандартными коллекциями .Net: System.Collections, System.Collections.Generic, или даже System.Collections.ObjectModel. На днях меня озадачил вопрос: а что использовать более выгодно (с точки зрения производительности): List, ArrayList, или HashSet? Проведя небольшое исследование, я решил написать результаты в этой статье.
Сразу стоит сказать несколько слов о Generic коллекциях, которые появились в .Net, начиная с версии 2.0. Мало того, что они позволяют удобно обращаться к элементам коллекций (зная их тип), но и нам не приходится тратить время на упаковку(boxing) и распаковку (unboxing) элементов этой коллекции в общий тип Object, что становится существенно при частых обращениях к элементам этой коллекции. Конечно же, не стоит забывать и о том, что происходит на этапе JIT-компиляции (CLR генерирует машинный код для каждого сочетания «метод + тип»), что приводит к «распуханию кода»(code explosion), и в итоге существенно увеличивается рабочий набор приложения и производительность ухудшается. Но, к счастью, Microsoft позаботилась об этом и встроила в CLR несколько оптимизационных алгоритмов, нацеленных на борьбу именно с этой проблемой.
В целом, если нет необходимости в коллекции, состоящей из разных типов элементов – стоит использовать Generic аналог коллекции.
Самое полное сравнение сложности операций коллекций я нашел здесь.
Взятую там таблицу, с некоторыми замечаниями и дополнениями, я приведу ниже.
* — коллизии происходят при попытке добавить элемент с уже существующим хэш-кодом (описание метода перехэширования можно найти здесь)
Интересное замечание об использовании коллекции HashSet я нашел здесь. Там говорится, что итерация по этой коллекции может быть и не такой уж быстрой… Дело в том, что при удалении элемента из коллекции вместо него остается «дыра», которая тоже итерируется. В случае же, если в коллекцию добавлялось большое количество элементов, а затем почти все из него удалились, это заметно скажется на скорости «пробега» по коллекции.
По заказу Microsoft компания Wintellect создала библиотеку Power Collections, основная цель которой – сделать некоторые классы наборов из STL-библиотеки C++ доступными для CLR. Подробнее можно посмотреть на их Web-сайте или на CodePlex.
Некоторые из классов этой библиотеки:
Кроме того есть еще одна не менее известная сборка коллекций: C5 generic collections.
При работе с WPF или Silverlight есть смысл работать с ObservableCollection — коллекция, посылающая уведомления при добавлении/удалении одного из элементов, что позволяет автоматически обновлять отображение таких элементов, как ListBox, ListView, или TreeView. Для того, чтобы коллекция реагировала на изменения какого-либо свойства своего элемента класса T, необходимо реализовать механизм уведомления об изменении для этого свойства, например — INotifyPropertyChanged.
Дженерики
Сразу стоит сказать несколько слов о Generic коллекциях, которые появились в .Net, начиная с версии 2.0. Мало того, что они позволяют удобно обращаться к элементам коллекций (зная их тип), но и нам не приходится тратить время на упаковку(boxing) и распаковку (unboxing) элементов этой коллекции в общий тип Object, что становится существенно при частых обращениях к элементам этой коллекции. Конечно же, не стоит забывать и о том, что происходит на этапе JIT-компиляции (CLR генерирует машинный код для каждого сочетания «метод + тип»), что приводит к «распуханию кода»(code explosion), и в итоге существенно увеличивается рабочий набор приложения и производительность ухудшается. Но, к счастью, Microsoft позаботилась об этом и встроила в CLR несколько оптимизационных алгоритмов, нацеленных на борьбу именно с этой проблемой.
В целом, если нет необходимости в коллекции, состоящей из разных типов элементов – стоит использовать Generic аналог коллекции.
Алгоритмическая сложность
Самое полное сравнение сложности операций коллекций я нашел здесь.
Взятую там таблицу, с некоторыми замечаниями и дополнениями, я приведу ниже.
| Внутренний вид |
Add/ Insert |
Расширение коллекции |
Queue/ Push/ Dequeue/ Pop/ Peek |
Remove/ RemoveAt |
Item[i] |
Get Enumerator |
Move Next |
|
| T[] |
Массив |
— | — | — | — | O(1) |
— | — |
| List, ArrayList, Collection, Observable Collection |
Массив |
O(1)/ O(n) |
O(n) |
— | O(n) |
O(1) |
O(1) |
O(1) |
| LinkedList |
Двойной список |
O(1) До или после данного узла |
O(1) |
O(1) |
O(1) До или после данного узла |
O(n) |
O(1) |
O(1) |
| Stack, Queue |
Массив |
O(1) |
O(n) |
O(1) |
— | — | O(1) |
O(1) |
| Dictionary, HashSet |
Hashtable с ссылками на массив индексов в случае коллизии * |
O(1), O(n) – в случае коллизии * |
O(n) |
— | O(1),O(n) – в случае коллизии * |
O(1),O(n) – в случае коллизии * |
O(1) |
O(1) |
| Sorted Dictionary, SortedSet |
Красно-черное дерево |
O(logn) |
O(logn) |
— | O(logn) |
O(logn) |
O(logn) |
O(1) |
| SortedList |
Массив |
O(n) |
O(n) |
— | O(n) |
O(1) |
O(1) |
O(1) |
* — коллизии происходят при попытке добавить элемент с уже существующим хэш-кодом (описание метода перехэширования можно найти здесь)
Интересное замечание об использовании коллекции HashSet я нашел здесь. Там говорится, что итерация по этой коллекции может быть и не такой уж быстрой… Дело в том, что при удалении элемента из коллекции вместо него остается «дыра», которая тоже итерируется. В случае же, если в коллекцию добавлялось большое количество элементов, а затем почти все из него удалились, это заметно скажется на скорости «пробега» по коллекции.
Wintellect's Power Collections for .NET
По заказу Microsoft компания Wintellect создала библиотеку Power Collections, основная цель которой – сделать некоторые классы наборов из STL-библиотеки C++ доступными для CLR. Подробнее можно посмотреть на их Web-сайте или на CodePlex.
Некоторые из классов этой библиотеки:
| Класс набора |
Описание |
| BigList<T> |
Набор упорядоченных объектов T. Очень эффективен, когда объектов больше 100. |
| Bag<T> |
Набор неупорядоченных объектов T. Этот набор хешируется и допускает дублирование объектов. |
| OrderedBag<T> |
Набор упорядоченных объектов T. Допускается дублирование объектов. |
| Set<T> |
Набор неупорядоченных элементов T. Дублирование не поддерживается. |
| OrderedSet<T> |
Набор упорядоченных элементов T. Дублирование не поддерживается. |
| OrderedDictionary<TKey,TValue> |
Словарь с упорядоченными однозначными ключами. |
| MultiDictionary<TKey,TValue> |
Словарь с многозначными ключами. Ключи хешируются, допускается дублирование, элементы не упорядочены. |
| OrderedMultiDictionary<TKey,TValue> |
Словарь с упорядоченными многозначными ключами (также в отсортированном порядке). Ключи хешируются, допускается дублирование ключей |
Кроме того есть еще одна не менее известная сборка коллекций: C5 generic collections.
Еще несколько слов
При работе с WPF или Silverlight есть смысл работать с ObservableCollection — коллекция, посылающая уведомления при добавлении/удалении одного из элементов, что позволяет автоматически обновлять отображение таких элементов, как ListBox, ListView, или TreeView. Для того, чтобы коллекция реагировала на изменения какого-либо свойства своего элемента класса T, необходимо реализовать механизм уведомления об изменении для этого свойства, например — INotifyPropertyChanged.