SortedList <>, SortedDictionary <> и словарь <>

Я нахожу, что SortedList<TKey, TValue> SortedDictionary<TKey, TValue> и Dictionary<TKey, TValue> реализуют те же интерфейсы.

  • Когда следует выбрать SortedList и SortedDictionary над Dictionary?
  • В чем разница между SortedList и SortedDictionary с точки зрения приложения?

Ответы

Ответ 1

  • При повторении элементов в любом из двух элементов будут отсортированы. Не так с Dictionary<T,V>.

  • MSDN описывает разницу между SortedList<T,V> и SortedDictionary<T,V>:

Общий класс SortedDictionary (TKey, TValue) представляет собой двоичный поиск дерево с извлечением O (log n), где n - количество элементов в словарь. В этом отношении он похож на SortedList (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).

Ответ 2

enter image description here

Я бы назвал разницу между словарями.

Над изображением показано, что Dictionary<K,V> равно или быстрее в каждом случае, чем Sorted аналоговый, но если требуется порядок элементов, например. для печати, Sorted выбирается один.

Src: http://people.cs.aau.dk/~normark/oop-csharp/html/notes/collections-note-time-complexity-dictionaries.html

Ответ 3

  • Если вы хотите, чтобы коллекция сортировалась по ключу, когда вы перебираете ее. Если вам не нужны ваши данные для сортировки, вам лучше всего использовать словарь, он будет иметь лучшую производительность.

  • SortedList и SortedDictionary в значительной степени выполняют одно и то же, но реализуются по-разному, поэтому имеют разные сильные и слабые стороны здесь объясняется.

Ответ 4

Чтобы суммировать результаты Performance Test - SortedList против SortedDictionary vs. Dictionary против Hashtable, результаты от самого лучшего до худшего для разных сценарии:

Использование памяти:

SortedList<T,T>
Hashtable
SortedDictionary<T,T>
Dictionary<T,T>

Вставки:

Dictionary<T,T>
Hashtable
SortedDictionary<T,T>
SortedList<T,T>

Операции поиска:

Hashtable
Dictionary<T,T>
SortedList<T,T>
SortedDictionary<T,T>

операции цикла foreach

SortedList<T,T>
Dictionary<T,T>
Hashtable
SortedDictionary<T,T>