Существуют ли какие-либо ресурсы об асимптотической сложности (большие-O и остальные) методов классов .NET-классов (Dictionary<K,V>, List<T> и т.д.)?
Я знаю, что документация по C5-библиотеке содержит некоторую информацию об этом (пример), но меня тоже интересуют стандартные .NET-коллекции... (и информация PowerCollections также будет приятной).
MSDN Выводит список:
Dictionary<,>List<>SortedList<,> (изменить: неверная ссылка; здесь общая версия)SortedDictionary<,>и т.д.. Например:
Тип сортировки (TKey, TValue) class является двоичным деревом поиска с O (log n), где n - количество элементов в словаре. В этом он аналогичен SortedDictionary (TKey, TValue) общий класс. Эти два класса аналогичны объектные модели, и оба имеют O (log n) поиск. Где два класса различия в использовании памяти и скорости вставка и удаление:
SortedList (TKey, TValue) использует меньше памяти, чем SortedDictionary (TKey, TValue).
SortedDictionary (TKey, TValue) имеет более быстрая установка и удаление операции для несортированных данных, O (log n) в отличие от O (n) для SortedList (TKey, TValue).
Если список заселен одновременно из отсортированных данных, SortedList (TKey, TValue) быстрее, чем SortedDictionary (TKey, TValue).
Эта страница обобщает некоторые из компонентов времени для различных типов коллекций с Java, хотя они должны быть точно такими же для .NET.
Я взял таблицы с этой страницы и изменил/расширил их для платформы .NET. См. Также страницы MSDN для SortedDictionary и SortedList, которые подробно временные сложности, необходимые для различных операций.
Type of Search/Collection Types Complexity Comments Linear search Array/ArrayList/LinkedList O(N) Unsorted data. Binary search sorted Array/ArrayList/ O(log N) Requires sorted data. Search Hashtable/Dictionary<T> O(1) Uses hash function. Binary search SortedDictionary/SortedKey O(log N) Sorting is automated.
Operation Array/ArrayList LinkedList SortedDictionary SortedList Access back O(1) O(1) O(log N) O(log N) Access front O(1) O(1) N.A. N.A. Access middle O(1) O(N) N.A. N.A. Insert at back O(1) O(1) O(log N) O(N) Insert at front O(N) O(1) N.A. N.A. Insert in middle O(N) O(1) N.A. N.A.
Удаление должно иметь такую же сложность, как и вставка для соответствующей коллекции.
SortedList имеет несколько примечательных особенностей для вставки и извлечения.
Вставка (метод добавления):
Этот метод является операцией O (n) для unsorted data, где n - Count. это операция O (log n), если новая элемент добавляется в конце список. Если вставка вызывает изменение размера, операция O (n).
Извлечение (свойство Item):
Извлечение значения этого свойства является операцией O (log n), где n является Граф. Установка свойства - это O (log n), если ключ уже в SortedList < (Of < (TKey, TValue > ) > ). Если ключ не находится в список, устанавливающий свойство O (n) операция для несортированных данных или O (log n), если новый элемент добавлен в конец списка. Если вставка вызывает изменение размера, операция O (n).
Обратите внимание, что ArrayList эквивалентно List<T> с точки зрения сложности всех операций.
Я вообще не знаю (другой ответ, который только что был опубликован, дает вам именно то, что вам нужно), но вы можете отразить этот и другие методы, конечно, используя ILSpy (немного неудобно с кодом FSharp, true) и это в конечном итоге дает эту функцию как С#:
internal static a maximumElementAux<a>(SetTree<a> s, a n)
{
while (true)
{
SetTree<a> setTree = s;
if (setTree is SetTree<a>.SetOne)
{
break;
}
if (setTree == null)
{
return n;
}
SetTree<a>.SetNode setNode = (SetTree<a>.SetNode)s;
SetTree<a> arg_23_0 = setNode.item3;
n = setNode.item1;
s = arg_23_0;
}
return ((SetTree<a>.SetOne)s).item;
return n;
}
Хорошо, так что это не совсем "правильный" код в терминах С#, но наличие цикла while(true) подразумевает, что он не может быть O (1) по крайней мере; что на самом деле... ну, у меня слишком много боли, чтобы узнать:)
На этой странице представлены короткие заметки о некоторых ключевых плюсах и минусах для большинства коллекций .NET:
Нет такой вещи, как "сложность классов коллекции". Скорее, разные операции над этими коллекциями имеют разные сложности. Например, добавление элемента в Dictionary<K, V> ...
... приближается к операции O (1). Если емкость должна быть увеличена для размещения нового элемента, этот метод станет операцией O (n), где
n-Count.
В то время как извлечение элемента из Dictionary<K, V> ...
... приближается к операции O (1).
В документации говорится, что он построен на двоичном дереве и не упоминает отслеживание максимального элемента. Если документация правильная, значит, она должна быть O (log n). В документации по коллекциям (как правило, в виде дерева с двоичным поиском) использовалась хотя бы одна ошибка, но она была исправлена.