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

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

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

6 ответов

Решение

  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, 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>
Источник

Я вижу, что предлагаемые ответы сосредоточены на производительности. Статья, представленная ниже, не дает ничего нового в отношении производительности, но объясняет основные механизмы. Также обратите внимание, что он не фокусируется на трех 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)

Переберите

  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)

Переберите

  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, я использовал следующие значения:

  • 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

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

Источник
Другие вопросы по тегам