Dictionary ‹Tkey, TValue›, List ‹T› и другие реализации / время выполнения коллекций

О List<T>:

List<T> имеет два свойства, Capacity и Count, которые помогают выяснить, когда происходит изменение размера. Capacity - длина внутреннего массива в любой момент времени, а Count - количество элементов, добавленных в список. Если у вас есть оценка количества элементов, которые будут добавлены в список, Capacity можно инициализировать (выбрав соответствующий конструктор), что приведет к меньшему количеству или отсутствию изменений размера и, следовательно, к повышению производительности.

Изменение размера (то есть создание нового большего массива и копирование элементов по одному в новый массив) происходит, когда вызывается метод Add<T>() и массив уже заполнен (Count == Capacity). Емкость нового массива удваивается (изначально, если она не установлена ​​пользователем, она начинается с 0, затем с 4, а затем удваивается каждый раз, когда требуется больше места):

List<int> list = new List<int>();
//Capacity = 0, Count = 0

list.Add(52);
//Capacity = 4, Count = 1

list.Add(34);
list.Add(2);
list.Add(87);
//Capacity = 4, Count = 4

list.Add(56);
//Capacity = 8, Count = 5

Для больших n временная сложность добавления нового элемента амортизируется постоянной O (1). Поиск по индексу - это постоянный O (1), а вставка или удаление элемента по данному индексу - линейный O (n), поскольку он включает в себя сдвиг остальной части элементы на одну позицию (вправо или влево соответственно). пространство, используемое для внутреннего массива, конечно, линейно по отношению к элементам массива, варьируется от n до 2n (или, если это имеет смысл: Math.Pow(2, Math.Ceiling(Math.Log(n, 2))) :).

О Queue<T> и Stack<T>:

Изменение размера внутреннего массива Queue и Stack работает аналогично тому, что описано для List<T>. Общие операции эффективны O (1) (внутри сохраняются индексы для элементов head и tail Queue). Таким образом, для постановки элемента в очередь или вставки в стек требуется амортизированное постоянное время, для вывода из очереди / вставки требуется постоянное время.

О Dictionary<TKey, TValue>:

Словарь работает иначе, и он хорошо описан здесь.

Точные детали реализации каждого из них потребуют долгого объяснения (для каждого из них). Вместо этого я бы отослал вас к книге Дж. Альбахари C # 5.0 In a Nutshell.

Тем не менее, я могу дать вам таблицу для учета памяти / времени для общих операций для Dictonary классов. Это время производительности в миллисекундах для выполнения 50 000 операций со словарем с целочисленными ключами и значениями на ПК с тактовой частотой 1,5 ГГц.

Type                Internal         Retrieve by     Memeory         Speed Random        Speed Seq        Speed Retrieval 
                    Structure        Index?          Overhead        Insertion           Insertion        by Key
Unsorted
Dictionary<T>       Hashtable        No              22              30                  30               20
Hashtable           Hashtable        No              38              50                  50               30
ListDictonary       Linked List      No              36              50,000              50,000           50,000
OrderedDictionary   Hashtable +      Yes             59              70                  70               40
                    Array
Sorted
SortedDictionary    Red-Black        No              20              130                 100              120 
<K, V>              Tree
SortedList <K, V>   2xArray          Yes             2               3,300               30               40
SortedList          2xArray          Yes             27              4,500               100              180

Извините, я не могу предоставить это другим вам.

Я надеюсь, что это будет полезно.