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

Question

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

Answer 1

Да - их эксплуатационные характеристики существенно отличаются.Вероятно, было бы лучше позвонить им 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 фактически поддерживает отсортированный массив, а не использует дерево.Он по-прежнему использует двоичный поиск для поиска элементов.)

Answer 2

Вот табличное представление, если это поможет...

Из Производительность перспектива:

+------------------+---------+----------+--------+----------+----------+---------+
| 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 подходит лучше. Смотрите этот вопрос для получения дополнительной информации о том, когда и что использовать.

Вы можете прочитать больше здесь, здесь, здесь, здесь и здесь.

Answer 3

Я приоткрыл 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;

Сортированный список.ctor(идентификатор, 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;
}

Сортированный список.Добавить(TKey, TValue) :пустота

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);
}

Сортированный список.RemoveAt(int) :пустота

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++;
}

Answer 4

Посмотрите на Страница 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>)>).

Answer 5

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

Answer 6

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

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

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

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

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

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

Answer 7

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