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

Question

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

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

Answer 1

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

Answer 2

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

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

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

Answer 3

Чтобы подвести итоги теста производительности - SortedList и SortedDictionary, словарь и 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>

Answer 4

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

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

Answer 5

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

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

Выдержки:

Dictionnary <>

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

SortedDictionary <>

SortedDictionary похож на словарь в использовании, но очень отличается по реализации. 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 (1).

Dictionnary

Память

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)

Loop Through

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 (1)
3. Удалить ItemArray(SortArray(i)) # O (1)
4. Удалить OrderArray(i) # O (n) (отсортированный массив)

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

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

Loop Through

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)

Loop Through

1. For i = 0 to n, возврат ItemArray(i)

Answer 6

Пытаясь присвоить оценку производительности каждому случаю, представленному @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

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