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

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

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

2. 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).

Отмечу разницу между словарями.

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

Источник: http://people.cs.aau.dk/~normark/oop-csharp/html/notes/collections-note-time-complexity- dictionaries.html

Подводя итог результатам теста производительности - SortedList vs. SortedDictionary vs. Dictionary vs. 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>

Я вижу, что предлагаемые ответы сосредоточены на производительности. В статье, представленной ниже, нет ничего нового в отношении производительности, но в ней объясняются основные механизмы. Также обратите внимание, что он не фокусируется на трех Collectionтипах, упомянутых в вопросе, а обращается ко всем типам System.Collections.Genericпространства имен.

http://geekswithblogs.net/BlackRabbitCoder/archive/2011/06/16/c.net-fundamentals-choosing-the-right-collection-class.aspx

Выписки:

Словарь <>

Словарь, вероятно, является наиболее часто используемым ассоциативным контейнерным классом. Словарь - это самый быстрый класс для ассоциативного поиска / вставки / удаления, потому что он использует хеш-таблицу под обложками . Поскольку ключи хешированы, тип ключа должен правильно реализовывать GetHashCode () и Equals () соответствующим образом, или вы должны предоставить внешний IEqualityComparer для словаря при построении. Время вставки / удаления / поиска элементов в словаре амортизируется постоянным временем - O (1) - это означает, что независимо от того, насколько велик словарь, время, необходимое для поиска чего-либо, остается относительно постоянным. Это очень желательно для высокоскоростного поиска. Единственным недостатком является то, что словарь по своей природе использования хэш-таблицы неупорядочен, поэтомувы не можете легко перемещаться по элементам в Словаре по порядку .

Сортированный словарь <>

SortedDictionary похож на Dictionary по использованию, но сильно отличается по реализации. SortedDictionary использует бинарное дерево под одеялом , чтобы сохранить детали в порядке ключа . Как следствие сортировки, тип, используемый для ключа, должен правильно реализовывать IComparable, чтобы ключи могли быть правильно отсортированы. Сортированный словарь использует немного времени поиска для возможности поддерживать элементы в порядке, поэтому время вставки / удаления / поиска в отсортированном словаре является логарифмическим - O (log n). Вообще говоря, используя логарифмическое время, вы можете удвоить размер коллекции, и для поиска элемента требуется только одно дополнительное сравнение. Используйте SortedDictionary, если вам нужен быстрый поиск, но вы также хотите поддерживать коллекцию в порядке по ключу.

SortedList <>

SortedList - это еще один класс сортированных ассоциативных контейнеров в общих контейнерах. И снова SortedList, как и SortedDictionary, использует ключ для сортировки пар ключ-значение . Однако, в отличие от SortedDictionary, элементы в SortedList хранятся как отсортированный массив элементов.. Это означает, что вставки и удаления являются линейными - O (n) - потому что удаление или добавление элемента может привести к перемещению всех элементов вверх или вниз в списке. Однако время поиска равно O (log n), потому что SortedList может использовать двоичный поиск для поиска любого элемента в списке по его ключу. Так зачем тебе вообще это нужно? Что ж, ответ заключается в том, что если вы собираетесь загрузить SortedList заранее, вставки будут медленнее, но поскольку индексирование массива происходит быстрее, чем следование ссылкам на объекты, поиск выполняется немного быстрее, чем SortedDictionary. Еще раз я бы использовал это в ситуациях, когда вам нужен быстрый поиск и вы хотите поддерживать коллекцию в порядке по ключу, и где вставки и удаления редки.

Предварительное резюме основных процедур

Отзывы очень приветствуются, так как я уверен, что не все понял правильно.

• Все массивы имеют размер n.
• Несортированный массив = .Add / .Remove равен O (1), но .Item (i) равен O (n).
• Сортированный массив = .Add / .Remove равен O (n), но .Item (i) равен O (log n).

Словарь

объем памяти

KeyArray(n) -> non-sorted array<pointer>
ItemArray(n) -> non-sorted array<pointer>
HashArray(n) -> sorted array<hashvalue>

Добавить

1. Добавить HashArray(n) = Key.GetHash# O (1)
2. Добавить KeyArray(n) = PointerToKey# O (1)
3. Добавить ItemArray(n) = PointerToItem# O (1)

удалять

1. For i = 0 to n, найти iгде HashArray(i) = Key.GetHash # O (log n) (отсортированный массив)
2. Удалить HashArray(i)# O (n) (отсортированный массив)
3. Удалить KeyArray(i)# O (1)
4. Удалить ItemArray(i)# O (1)

Получить предмет

1. For i = 0 to n, найти iгде HashArray(i) = Key.GetHash# O (log n) (отсортированный массив)
2. Возвращение ItemArray(i)

Переберите

1. For i = 0 to n, возвращение ItemArray(i)

SortedDictionary

объем памяти

KeyArray(n) = non-sorted array<pointer>
ItemArray(n) = non-sorted array<pointer>
OrderArray(n) = sorted array<pointer>

Добавить

1. Добавить KeyArray(n) = PointerToKey# O (1)
2. Добавить ItemArray(n) = PointerToItem# O (1)
3. For i = 0 to n, найти iгде KeyArray(i-1) < Key < KeyArray(i)(используя ICompare) # O (n)
4. Добавить OrderArray(i) = n# O (n) (отсортированный массив)

удалять

1. For i = 0 to n, найти iгде KeyArray(i).GetHash = Key.GetHash# O (n)
2. Удалить KeyArray(SortArray(i))# O (n)
3. Удалить ItemArray(SortArray(i))# O (n)
4. Удалить OrderArray(i)# O (n) (отсортированный массив)

Получить предмет

1. For i = 0 to n, найти iгде KeyArray(i).GetHash = Key.GetHash# O (n)
2. Возвращение ItemArray(i)

Переберите

1. For i = 0 to n, возвращение ItemArray(OrderArray(i))

SortedList

объем памяти

KeyArray(n) = sorted array<pointer>
ItemArray(n) = sorted array<pointer>

Добавить

1. For i = 0 to n, найти iгде KeyArray(i-1) < Key < KeyArray(i)(используя ICompare) # O (log n)
2. Добавить KeyArray(i) = PointerToKey# O (n)
3. Добавить ItemArray(i) = PointerToItem# O (n)

удалять

1. For i = 0 to n, найдите iгде KeyArray(i).GetHash = Key.GetHash# O (log n)
2. Удалить KeyArray(i)# O (n)
3. Удалить ItemArray(i)# O (n)

Получить предмет

1. For i = 0 to n, найдите iгде KeyArray(i).GetHash = Key.GetHash# O (log n)
2. Возвращение ItemArray(i)

Переберите

1. For i = 0 to n, возвращение ItemArray(i)

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

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

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

• О (1) = 3
• O (журнал п) = 2
• О (п) = 1
• O (1) или O (n) = 2
• O (log n) или O (n) = 1,5

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

Dictionary:       12.0 
SortedDictionary:  9.0 
SortedList:        6.5

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