Qual é a diferença entre SortedList e SortedDictionary?
-
06-09-2019 - |
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?
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 aoSortedList<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 queSortedDictionary<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) paraSortedList<TKey, TValue>
.Se a lista é preenchida de uma só vez a partir de dados classificados,
SortedList<TKey, TValue>
é mais rápido do queSortedDictionary<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.
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++;
}
Confira o href="http://msdn.microsoft.com/en-us/library/ms132319.aspx" rel="noreferrer"> MSDN página :
De seção Comentários:
A classe genérica
SortedList<(Of <(TKey, TValue>)>)
é uma árvore de busca binária com recuperaçãoO(log n)
, onden
é o número de elementos no dicionário. Neste, é semelhante à classe genéricaSortedDictionary<(Of <(TKey, TValue>)>)
. As duas classes têm modelos de objectos semelhantes, e ambos têm recuperaçãoO(log n)
. Onde as duas classes diferem está em uso de memória e velocidade de inserção e remoção:
- usos
SortedList<(Of <(TKey, TValue>)>)
menos memória do queSortedDictionary<(Of <(TKey, TValue>)>)
.
SortedDictionary<(Of <(TKey, TValue>)>)
tem operações mais rápidas de inserção e remoção para dados não ordenados,O(log n)
em oposição aO(n)
paraSortedList<(Of <(TKey, TValue>)>)
.Se a lista é preenchida de uma só vez a partir de dados classificados,
SortedList<(Of <(TKey, TValue>)>)
é mais rápido queSortedDictionary<(Of <(TKey, TValue>)>)
.
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).