четверг, 24 октября 2013 г.

Какие структуры данных используются в .NET

Я собрал некоторую информацию о временной сложности и о базовых структурах данных лежащих в основе простых коллекций и словарей в .NET. Было сложно найти эту информацию как в официальных источниках, таких как MSDN так и на не официальных источниках, так как информация отличалась, поэтому я использовал Reflector и фактически использовал реализацию классов для подтверждения информации.

Простые коллекции

Тип
Структура данных
Пояснение
List<T>
Массив
Обычный список использующий динамический массив
SortedSet<T>
Красно-черное дерево
Список использующий красно-черное дерево

Временная сложность

Тип
Получить i - элемент
Поиск
Добавление в конец
Вставка
Удаление
List<T>
O(1)
O(n)
O(1)*
O(n)
O(n)
SortedSet<T>
Не доступно
O(log n)
O(log n)
O(log n)
O(log n)

* Сложность метода List.Add является линейной O(n) когда добавление элемента требует увеличение размера массива лежащего в основе списка.

Словари
Словари или хеш-таблицы идеально подходят в тех случаях когда вам необходим доступ к элементу по ключу или когда вам надо быстрое удаление или вставка. Обратите внимание этот раздел не относится к классу Lookup который хранит для каждого ключа коллекцию значений.

Тип
Структура данных
Пояснение
HashSet<T>
Хеш таблица
Хеш таблица ключом которой является сам объект
Dictionary<TKey, TValue>
Хеш таблица
Хеш таблица у которой ключ не обязательно является хранящимся объектом
SortedList<TKey, TValue>
Массив
Тоже самое, что и Dictionary за исключением того, что элементы и их ключи хранятся в отсортированных массивах
SortedDictionary<TKey, TValue>
Красно-черное дерево
Тоже самое, что и Dictionary за исключением того, что элементы и их ключи хранятся в красно-черных деревьях. Внутри себя использует SortedSet 

Временная сложность

Тип
Поиск по ключу
Удаление элемента
Добавление элемента
HashSet
O(1)*
O(1)*
O(1)**
Dictionary
O(1)*
O(1)*
O(1)**
SortedList
O(log n)
O(n)
O(n)
SortedDictionary
O(log n)
O(log n)
O(log n)

* O(n) с коллизиями
** O(n) с коллизиями или когда добавление элемента требует увеличение размера массива лежащего в основе.

SortedList против SortedDictionary
SortedList и SortedDictionary лучше всего подходят когда вам необходимо хранить элементы в отсортированном порядке. Вот сравнение этих классов от Microsoft:

SortedList<TKey, TValue> - обобщенный класс состоящий из массивов пар ключ/значение c временной сложностью поиска равной O(logn), где n - количество элементов в словаре. В этом он похож на обобщенный класс SortedDictionary<TKey, TValue> . Эти два класса имеют похожую объектную модель, и сложность поиска у обоих равна O(logn). Однако эти классы различаются в количестве используемой памяти и скорости вставки и удаления элементов:

  • SortedList<TKey, TValue> использует меньше памяти чем SortedDictionary<TKey, TValue>;
  • SortedDictionary<TKey, TValue> выполняет быстрее операции удаления и вставки для не отсортированных данных, O(logn) против O(n) для SortedList<TKey, TValue>;
  • Если список состоит из отсортированных данных то SortedList<TKey, TValue> быстрее чем SortedDictionary<TKey, TValue>.

Другое отличие между классами SortedList<TKey, TValue> и SortedDictionary<TKey, TValue> заключается в том, что класс SortedList<TKey, TValue> обеспечивает эффективное индексирование ключей и значений возвращенных через свойства Keys и Values. Открытых свойств не достаточно для изменения списков, так как они являются просто обертками для внутренних массивов ключей и значений.

Комментариев нет:

Отправить комментарий