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

Есть ли реальная практическая разница между SortedList<TKey,TValue> и SortedDictionary<TKey,TValue>? Есть ли какие-то обстоятельства, когда вы бы специально использовали один, а не другой?

Источник

7 ответов

Решение

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

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

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>,

(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<TKey> comparer;
private static TKey[] emptyKeys;
private static TValue[] emptyValues;
private KeyList<TKey, TValue> keyList;
private TKey[] keys;
private const int MaxArrayLength = 0x7fefffff;
private ValueList<TKey, TValue> valueList;
private TValue[] values;
private int version;

SortedList.ctor (IDictionary, IComparer)

public SortedList(IDictionary<TKey, TValue> dictionary, IComparer<TKey> 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<TKey, TValue>(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<TKey>(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>)>) родовой класс. Два класса имеют похожие объектные модели, и оба имеют O(log n) поиск. Эти два класса различаются в использовании памяти и скорости вставки и удаления:

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

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