SortedList , SortedDictionary и словарь

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

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

  1. При итерации по элементам в любом из двух элементов будут отсортированы. Не так с Dictionary .

  2. MSDN обращается к разнице между SortedList и SortedDictionary :

Общий class SortedDictionary (TKey, TValue) представляет собой двоичное дерево поиска с извлечением O (log n), где n – количество элементов в словаре. В этом отношении он похож на общий class SortedList (TKey, TValue). Эти два classа имеют похожие объектные модели, и оба имеют O (log n). Если два classа отличаются друг от друга, это использование памяти и скорость вставки и удаления:

SortedList (TKey, TValue) использует меньше памяти, чем SortedDictionary (TKey, TValue).

SortedDictionary (TKey, TValue) имеет более быструю операцию вставки и удаления для несортированных данных: O (log n) в отличие от O (n) для SortedList (TKey, TValue).

Если список заполняется сразу из отсортированных данных, SortedList (TKey, TValue) быстрее, чем SortedDictionary (TKey, TValue).

введите описание изображения здесь

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

На приведенном выше рисунке показано, что Dictionary равен или быстрее в каждом случае, чем Sorted analog, но если требуется порядок элементов, например, для их печати, выбирается Sorted one.

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

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

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

 SortedList Hashtable SortedDictionary Dictionary 

Вставки:

 Dictionary Hashtable SortedDictionary SortedList 

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

 Hashtable Dictionary SortedList SortedDictionary 

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

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

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

Пытаясь присвоить оценку производительности каждому случаю, представленному @Lev, я использовал следующие значения:

  • O (1) = 3
  • O (log n) = 2
  • O (n) = 1
  • O (1) или O (n) = 2
  • O (log n) или O (n) = 1,5

Результаты (выше = лучше):

 Dictionary: 12.0 SortedDictionary: 9.0 SortedList: 6.5 

Конечно, каждый случай использования придаст больший вес определенным операциям.

Давайте будем гением компьютера.