Qual é a diferença entre SortedList e SortedDictionary?

261

Existe alguma diferença prática real entre a SortedList<TKey,TValue>e a SortedDictionary<TKey,TValue>? Existem circunstâncias em que você usaria especificamente um e não o outro?

Shaul Behr
fonte
13
Estou confuso. Por que SortedList tem dois parâmetros de tipo em SortedList<TKey,TValue>vez de um SortedList<T>? Por que não implementa IList<T>?
Coronel Panic
3
@ColonelPanic porque funcionalmente SortedList é um mapa, não uma coleção linear. Não deixe o nome te enganar. Assim como um dicionário, você passa uma chave, recebe um valor de volta. Enquanto o dicionário não é ordenado, SortedList é ordenado em sua ordem de classificação natural.
Nawfal

Respostas:

294

Sim - suas características de desempenho diferem significativamente. Provavelmente seria melhor chamá-los SortedListe, SortedTreecomo isso reflete a implementação mais de perto.

Consulte os documentos do MSDN de cada um deles ( SortedList, SortedDictionary) para obter detalhes do desempenho de diferentes operações em diferentes situações. Aqui está um bom resumo (dos SortedDictionarydocumentos):

A SortedDictionary<TKey, TValue>classe genérica é uma árvore de pesquisa binária com recuperação de O (log n), em que n é o número de elementos no dicionário. Nisso, é semelhante à SortedList<TKey, TValue>classe genérica. As duas classes têm modelos de objetos semelhantes e ambas têm recuperação O (log n). Onde as duas classes diferem está no uso da memória e na velocidade de inserção e remoção:

  • SortedList<TKey, TValue>usa menos memória que SortedDictionary<TKey, TValue>.

  • SortedDictionary<TKey, TValue>possui operações de inserção e remoção mais rápidas para dados não classificados, O (log n) em oposição a O (n) para SortedList<TKey, TValue>.

  • Se a lista for preenchida de uma só vez a partir de dados classificados, SortedList<TKey, TValue>será mais rápida que SortedDictionary<TKey, TValue>.

( SortedListna verdade, mantém uma matriz classificada, em vez de usar uma árvore. Ainda usa a pesquisa binária para encontrar elementos.)

Jon Skeet
fonte
Muito obrigado a todos pelos ponteiros. Acho que sou muito preguiçoso em relação ao RTFM ... muito mais fácil perguntar às pessoas legais sobre SO ...;) Eu votei em vocês dois pelas respostas; Jon recebe o crédito da resposta por ser o primeiro a acionar. :)
Shaul Behr
2
Eu acho que a definição SortedList deve ser corrigida, pois não acredito que seja uma árvore de pesquisa binária ...?
Nchaud
1
Eu olhei usando o refletor e descobri que ele não usava uma árvore de pesquisa binária.
Daniel IMMS
Eu acho que o Sorteddictionary é uma árvore AVL ou Red-Blacktree (todo o custo de operação O (logn). E o SortedList é uma pesquisa binária (custa (n) tempo no pior caso) l
Ghoster
105

Aqui está uma exibição tabular, se ajudar ...

De uma perspectiva de desempenho :

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

De uma perspectiva de implementação :

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

Para cerca de paráfrase, se você precisar de desempenho bruto SortedDictionarypoderia ser uma escolha melhor. Se você precisar de menos sobrecarga de memória e recuperação indexada, será SortedListmelhor. Veja esta pergunta para saber mais sobre quando usar qual.

Você pode ler mais aqui , aqui , aqui , aqui e aqui .

nawfal
fonte
Note que se você quer um bom desempenho e uso relativamente baixo de memória e recuperação indexada, considere BDictionary<Key,Value>em LoycCore em vez de SortedDictionary.
26416 Qwertie
1
Sim, veja a parte inferior deste artigo . Acontece que BDictionarygeralmente é mais lento do que SortedDictionaryexceto para tamanhos muito grandes, mas é mais rápido do que SortedListse houver mais de 700 itens. O uso da memória deve ser apenas ligeiramente maior que SortedList(muito menor que SortedDictionary), devido ao uso de matrizes nas folhas da árvore.
Qwertie
22

Eu abri o Reflector para dar uma olhada nisso, pois parece haver um pouco de confusão SortedList. Na verdade, não é uma árvore de pesquisa binária, é uma matriz classificada (por chave) de pares de valores-chave . Há também uma TKey[] keysvariável que é classificada em sincronia com os pares de valores-chave e usada para pesquisa binária.

Aqui está uma fonte (visando o .NET 4.5) para fazer backup de minhas reivindicações.

Membros privados

// 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++;
}
Daniel Imms
fonte
13

Confira a página do MSDN para SortedList :

Na seção Observações:

A SortedList<(Of <(TKey, TValue>)>)classe genérica é uma árvore de pesquisa binária com O(log n)recuperação, onde né o número de elementos no dicionário. Nisso, é semelhante à SortedDictionary<(Of <(TKey, TValue>)>)classe genérica. As duas classes têm modelos de objetos semelhantes e ambas têm O(log n)recuperação. Onde as duas classes diferem está no uso da memória e na velocidade de inserção e remoção:

  • SortedList<(Of <(TKey, TValue>)>)usa menos memória que SortedDictionary<(Of <(TKey, TValue>)>).
  • SortedDictionary<(Of <(TKey, TValue>)>)possui operações de inserção e remoção mais rápidas para dados não classificados, O(log n)em oposição a O(n)para SortedList<(Of <(TKey, TValue>)>).

  • Se a lista for preenchida de uma só vez a partir de dados classificados, SortedList<(Of <(TKey, TValue>)>)será mais rápida que SortedDictionary<(Of <(TKey, TValue>)>).

Stephan
fonte
9
O texto citado está errado (e foi atualizado no MSDN): SortedList não é uma "árvore de pesquisa binária", é uma "matriz de pares de chave / valor".
Eldritch Conundrum
12

Esta é uma representação visual de como os desempenhos se comparam.

Lev
fonte
De onde você tirou essa informação? A partir desse esquema, podemos ver que o Dictinary é melhor de qualquer forma, portanto não há razão para que outros existam.
alex Kostin
9

Já foi dito o suficiente sobre o assunto, no entanto, para simplificar, aqui está minha opinião.

O dicionário ordenado deve ser usado quando-

  • São necessárias mais inserções e operações de exclusão.
  • Dados não ordenados.
  • O acesso à chave é suficiente e o acesso ao índice não é necessário.
  • A memória não é um gargalo.

Por outro lado, a lista classificada deve ser usada quando-

  • São necessárias mais pesquisas e menos operações de inserção e exclusão.
  • Os dados já estão classificados (se não todos, a maioria).
  • O acesso ao índice é necessário.
  • A memória é uma sobrecarga.

Espero que isto ajude!!

Prakash Tripathi
fonte
1

O acesso ao índice (mencionado aqui) é a diferença prática. Se você precisar acessar o sucessor ou predecessor, precisará SortedList. O SortedDictionary não pode fazer isso, portanto você é bastante limitado em como pode usar a classificação (primeiro / foreach).

Cara
fonte