В чем разница между SortedList и SortedDictionary?

Есть ли реальная практическая разница между SortedList и SortedDictionary ? Существуют ли какие-либо обстоятельства, при которых вы конкретно использовали бы один, а не другой?

Да – их характеристики производительности значительно различаются. Вероятно, было бы лучше назвать их SortedTree и SortedTree поскольку это более точно отражает реализацию.

Посмотрите документы MSDN для каждого из них ( SortedDictionary , SortedDictionary ) для получения подробной информации о производительности для разных операций в разных ситуациях. Вот хорошее резюме (из документов SortedDictionary ):

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

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

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

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

( SortedList фактически поддерживает отсортированный массив, а не использует дерево. Он по-прежнему использует двоичный поиск для поиска элементов.)

Вот табличное представление, если оно помогает …

С точки зрения производительности :

 +------------------+---------+----------+--------+----------+----------+---------+ | Collection | Indexed | Keyed | Value | Addition | Removal | Memory | | | lookup | lookup | lookup | | | | +------------------+---------+----------+--------+----------+----------+---------+ | SortedList | O(1) | O(log n) | O(n) | O(n)* | O(n) | Lesser | | SortedDictionary | n/a | O(log n) | O(n) | O(log n) | O(log n) | Greater | +------------------+---------+----------+--------+----------+----------+---------+ * Insertion is O(1) for data that are already in sort order, so that each element is added to the end of the list (assuming no resize is required). 

С точки зрения реализации :

 +------------+---------------+----------+------------+------------+------------------+ | Underlying | Lookup | Ordering | Contiguous | Data | Exposes Key & | | structure | strategy | | storage | access | Value collection | +------------+---------------+----------+------------+------------+------------------+ | 2 arrays | Binary search | Sorted | Yes | Key, Index | Yes | | BST | Binary search | Sorted | No | Key | Yes | +------------+---------------+----------+------------+------------+------------------+ 

Чтобы грубо перефразировать, если вам нужна сырая производительность, SortedDictionary может быть лучшим выбором. Если вам требуется меньшая накладная память и индексированный поиск SortedList подходит лучше. См. Этот вопрос для получения дополнительной информации о том, когда использовать.

Здесь вы можете прочитать здесь , здесь , здесь , здесь и здесь .

Я взломал Reflector, чтобы посмотреть на это, потому что, похоже, есть немного путаницы в SortedList . Это фактически не двоичное дерево поиска, это отсортированный (по ключевому) массив пар ключ-значение . Существует также переменная TKey[] keys которая сортируется в синхронизации с парами ключ-значение и используется для двоичного поиска.

Вот некоторые источники (с таргетингом на .NET 4.5) для резервного копирования моих заявок.

Частные члены

 // Fields private const int _defaultCapacity = 4; private int _size; [NonSerialized] private object _syncRoot; private IComparer comparer; private static TKey[] emptyKeys; private static TValue[] emptyValues; private KeyList keyList; private TKey[] keys; private const int MaxArrayLength = 0x7fefffff; private ValueList valueList; private TValue[] values; private int version; 

SortedList.ctor (IDictionary, IComparer)

 public SortedList(IDictionary dictionary, IComparer comparer) : this((dictionary != null) ? dictionary.Count : 0, comparer) { if (dictionary == null) { ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary); } dictionary.Keys.CopyTo(this.keys, 0); dictionary.Values.CopyTo(this.values, 0); Array.Sort(this.keys, this.values, comparer); this._size = dictionary.Count; } 

SortedList.Add (TKey, TValue): void

 public void Add(TKey key, TValue value) { if (key == null) { ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); } int num = Array.BinarySearch(this.keys, 0, this._size, key, this.comparer); if (num >= 0) { ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate); } this.Insert(~num, key, value); } 

SortedList.RemoveAt (int): void

 public void RemoveAt(int index) { if ((index < 0) || (index >= this._size)) { ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index); } this._size--; if (index < this._size) { Array.Copy(this.keys, index + 1, this.keys, index, this._size - index); Array.Copy(this.values, index + 1, this.values, index, this._size - index); } this.keys[this._size] = default(TKey); this.values[this._size] = default(TValue); this.version++; } 

Просмотрите страницу MSDN для SortedList :

Из раздела «Замечания»:

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

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

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

Это визуальное представление о том, как характеристики сравниваются друг с другом.

Достаточно сказано уже по теме, однако, чтобы это было просто, вот мой прием.

Сортированный словарь следует использовать, когда –

  • Требуются дополнительные операции вставки и удаление.
  • Данные не упорядочены.
  • Доступ к ключам достаточно, и доступ к индексу не требуется.
  • Память не является узким местом.

С другой стороны, Сортированный список следует использовать, когда –

  • Требуется больше запросов и меньше операций вставки и удаления.
  • Данные уже отсортированы (если не все, большинство).
  • Требуется доступ к индексу.
  • Память – это накладные расходы.

Надеюсь это поможет!!

Индексный доступ (упомянутый здесь) является практическим различием. Если вам нужно получить доступ к преемнику или предшественнику, вам потребуется SortedList. SortedDictionary не может этого сделать, поэтому вы достаточно ограничены тем, как вы можете использовать сортировку (first / foreach).

Interesting Posts

исключение в streamе ‘main’ java.lang.NoClassDefFoundError:

Какую файловую систему следует использовать между OSX и Linux

Практика ведения журналов

Время обработки увеличивается дольше и после каждой итерации (TensorFlow)

обновлять файл app.config программно с помощью ConfigurationManager.OpenExeConfiguration (ConfigurationUserLevel.None);

Eclipse / Maven: тесты JUnit не скомпилированы при их запуске

Как управлять несколькими устройствами воспроизведения звука в Windows Vista / 7?

Передача массивов в качестве параметров в bash

Положительная lambda: ‘+ {}’ – Какое волшебство?

MVC, кнопка отправки которого нажата

НПМ за прокси-сервером NTLM

OracleDataSource против Oracle UCP PoolDataSource

Динамические изображения, переданные через HTTPS, отображают сломанное изображение в слове при открытии HTTP-документа

Могу ли я создать собственный код поля в Word 2010 или использовать макрос?

Замена для поврежденного USB-приемопередатчика

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