Qual é a diferença entre SortedList e SortedDictionary?

StackOverflow https://stackoverflow.com/questions/935621

Pergunta

Existe alguma diferença prática real entre um SortedList<TKey,TValue> e uma SortedDictionary<TKey,TValue> ? Existem quaisquer circunstâncias onde você iria especificamente usar um e não o outro?

Foi útil?

Solução

Sim - suas características de desempenho diferem significativamente. Provavelmente seria melhor chamá-los SortedList e SortedTree como que reflete a implementação mais de perto.

Olhe para a documentação do MSDN para cada um deles ( SortedList , SortedDictionary ) para obter detalhes sobre o desempenho para diferentes operações em diferentes situtations. Aqui está um resumo agradável (dos docs SortedDictionary):

O SortedDictionary<TKey, TValue> genérico classe é uma árvore de busca binária com O (N log N) de recuperação, onde n é o número de elementos no dicionário. Neste, é semelhante ao SortedList<TKey, TValue> genérico classe. As duas classes têm semelhante modelos de objecto, e ambos têm O (N log N) recuperação. Onde as duas classes diferem está em uso de memória e velocidade de inserção e remoção:

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

  • SortedDictionary<TKey, TValue> tem inserção mais rápida e remoção operações para dados não ordenados, O (N log N) em oposição a O (n) para SortedList<TKey, TValue>.

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

(SortedList realmente mantém um array ordenado, ao invés de usar uma árvore. Ele ainda usa pesquisa binária para encontrar elementos.)

Outras dicas

Aqui está uma visão tabular se isso ajuda ...

A partir de um desempenho perspectiva: 

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

A partir de um aplicação perspectiva: 

+------------+---------------+----------+------------+------------+------------------+
| 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 aproximadamente paráfrase, se você precisar de SortedDictionary desempenho bruto poderia ser uma escolha melhor. Se você precisar de menor sobrecarga de memória e indexados fits SortedList recuperação melhor. Veja esta questão para saber mais sobre quando usar cada.

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

Eu rachei Refletor aberto a ter um olhar para isso como parece haver um pouco de confusão sobre SortedList. É, de facto, não uma árvore de busca binária, é uma classificadas (pela chave) matriz de pares chave-valor . Há também uma variável TKey[] keys que é classificada em sincronia com os pares chave-valor e usado para busca binária.

Aqui está alguma fonte (alvo 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++;
}

Esta é a representação visual de como performances comparar uns aos outros.

O suficiente é dito já sobre o tema, no entanto mantê-lo simples, aqui é a minha opinião.

Ordenado dicionário deve ser usado quando -

  • Mais inserções e operações de exclusão são necessários.
  • Dados em ordenou-un.
  • Acesso Key é suficiente e acesso índice não é exigido.
  • A memória não é um gargalo.

Por outro lado, lista ordenada deve ser usado quando -

  • Mais pesquisas e menos inserções e operações de exclusão são necessários.
  • Os dados já estão classificados (se não todos, a maioria).
  • Acesso Index é necessária.
  • A memória é uma sobrecarga.

Espero que isso ajude !!

Acesso Index (mencionado aqui) é a diferença prática. Se você precisar acessar o sucessor ou predecessor, você precisa SortedList. SortedDictionary não pode fazer isso assim que você é bastante limitada com a forma como você pode usar a ordenação (primeiro / foreach).

Não afiliado a StackOverflow
scroll top