SortedList <>, SortedDictionary <> e Dicionário <>

98

Eu acho isso SortedList<TKey, TValue> SortedDictionary<TKey, TValue>e Dictionary<TKey, TValue>implemento as mesmas interfaces.

  1. Quando devemos optar por SortedListe SortedDictionaryterminar Dictionary?
  2. Qual é a diferença entre SortedListe SortedDictionaryem termos de aplicação?
Sunder
fonte

Respostas:

101
  1. Ao iterar sobre os elementos em qualquer um dos dois, os elementos serão classificados. Não é assim com Dictionary<T,V>.

  2. MSDN trata da diferença entre SortedList<T,V>e SortedDictionary<T,V>:

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

SortedList (TKey, TValue) usa menos memória do que SortedDictionary (TKey, TValue).

SortedDictionary (TKey, TValue) tem 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 vez a partir de dados classificados, SortedList (TKey, TValue) será mais rápido do que SortedDictionary (TKey, TValue).

Szymon Rozga
fonte
21
Outra diferença prática, que em SortedListvocê pode recuperar por índice (em oposição à recuperação por chave) e em SortedDictionaryvocê não pode.
Andrew Savinykh
65

insira a descrição da imagem aqui

Eu mencionaria diferença entre dicionários.

A imagem acima mostra que Dictionary<K,V>é igual ou mais rápido em todos os casos do que Sortedanalógico, mas se a ordem dos elementos for necessária, por exemplo, para imprimi-los, Sortedum é escolhido.

Src: http://people.cs.aau.dk/~normark/oop-csharp/html/notes/collections-note-time-complexity-dictionaries.html

Lev
fonte
1
Excelente visão geral. Embora não esteja na pergunta original, deve-se notar que, se você escolher entre as Immutableversões desses dicionários, as Sortedversões são geralmente mais rápidas em cerca de 40-50% do que as contrapartes não classificadas (ainda O(log(n)), mas visivelmente mais rápidas por operação) . Os tempos podem ser diferentes dependendo de como a entrada está classificada. Consulte stackoverflow.com/a/30638592/111575
Abel de
21

Para resumir os resultados de um Teste de desempenho - SortedList x SortedDictionary x Dicionário x Hashtable , os resultados do melhor ao pior para diferentes cenários:

Uso de memória:

SortedList<T,T>
Hashtable
SortedDictionary<T,T>
Dictionary<T,T>

Inserções:

Dictionary<T,T>
Hashtable
SortedDictionary<T,T>
SortedList<T,T>

Operações de pesquisa:

Hashtable
Dictionary<T,T>
SortedList<T,T>
SortedDictionary<T,T>

operações de loop foreach

SortedList<T,T>
Dictionary<T,T>
Hashtable
SortedDictionary<T,T>
NullReference
fonte
1
Ao examinar os resultados do teste, pode-se questionar a razão de ser de SortedDictionary.
beawolf
1
Se for Collectionnecessário sorted, você pode esquecer Hashtablee Dictionary: se preencher sua coleção de uma vez -> vá para SortedList, mas se você antecipar, muitas vezes precisará .Adde .Removeitens -> vá para SortedDictionary.
Ama
Talvez haja uma necessidade de esclarecer o que sortedsignifica: quando você faz um, em For Each MyItem in Collectionvez de ser processado na ordem em que .Addos itens foram originalmente sorted Collectioneditados , a irá processá-los em uma ordem de acordo com os critérios dos Keyvalores (definidos em um IComparer). Por exemplo, se suas Chaves são Strings, então sua Coleção será, por padrão, processada de acordo com a ordem alfabética de suas Chaves, mas você sempre pode definir uma regra de classificação personalizada.
Ama
9
  1. Quando você deseja que a coleção seja classificada por chave ao iterar sobre ela. Se você não precisa que seus dados sejam classificados, é melhor você apenas ter um Dicionário, ele terá um desempenho melhor.

  2. SortedList e SortedDictionary fazem praticamente a mesma coisa, mas são implementados de forma diferente, portanto, têm diferentes pontos fortes e fracos explicados aqui .

Meta-Knight
fonte
8

Posso ver que as respostas propostas se concentram no desempenho. O artigo fornecido a seguir não fornece nada de novo em relação ao desempenho, mas explica os mecanismos subjacentes. Observe também que ele não se concentra nos três CollectionTipos mencionados na pergunta, mas aborda todos os Tipos do System.Collections.Genericnamespace.

http://geekswithblogs.net/BlackRabbitCoder/archive/2011/06/16/c.net-fundamentals-choosing-the-right-collection-class.aspx

Extrai:

Dicionário <>

O Dicionário é provavelmente a classe de contêiner associativa mais usada. O Dicionário é a classe mais rápida para pesquisas / inserções / exclusões associativas porque usa uma tabela de hash por baixo dos panos . Como as chaves são hash, o tipo de chave deve implementar corretamente GetHashCode () e Equals () ou você deve fornecer um IEqualityComparer externo ao dicionário na construção. O tempo de inserção / exclusão / pesquisa de itens no dicionário é o tempo constante amortizado - O (1) - o que significa que não importa o tamanho do dicionário, o tempo que leva para encontrar algo permanece relativamente constante. Isso é altamente desejável para pesquisas de alta velocidade. A única desvantagem é que o dicionário, por natureza de usar uma tabela hash, não está ordenado, entãovocê não pode percorrer facilmente os itens em um Dicionário em ordem .

SortedDictionary <>

O SortedDictionary é semelhante ao Dicionário no uso, mas muito diferente na implementação. O SortedDictionary usa uma árvore binária nos bastidores para manter os itens em ordem pela chave . Como consequência da classificação, o tipo usado para a chave deve implementar IComparable corretamente para que as chaves possam ser classificadas corretamente. O dicionário classificado troca um pouco do tempo de pesquisa pela capacidade de manter os itens em ordem, portanto, os tempos de inserção / exclusão / pesquisa em um dicionário classificado são logarítmicos - O (log n). De modo geral, com o tempo logarítmico, você pode dobrar o tamanho da coleção e basta fazer uma comparação extra para encontrar o item. Use o SortedDictionary quando quiser pesquisas rápidas, mas também quiser manter a coleção em ordem pela chave.

SortedList <>

O SortedList é a outra classe de contêiner associativa classificada nos contêineres genéricos. Mais uma vez, SortedList, como SortedDictionary, usa uma chave para classificar pares de valores-chave . Ao contrário de SortedDictionary, no entanto, os itens em uma SortedList são armazenados como uma matriz classificada de itens. Isso significa que as inserções e exclusões são lineares - O (n) - porque excluir ou adicionar um item pode envolver o deslocamento de todos os itens para cima ou para baixo na lista. O tempo de pesquisa, entretanto, é O (log n) porque SortedList pode usar uma pesquisa binária para encontrar qualquer item na lista por sua chave. Então, por que você quer fazer isso? Bem, a resposta é que se você for carregar a SortedList antecipadamente, as inserções serão mais lentas, mas como a indexação de array é mais rápida do que seguir links de objetos, as pesquisas são ligeiramente mais rápidas do que SortedDictionary. Mais uma vez, eu usaria isso em situações em que você deseja pesquisas rápidas e deseja manter a coleção em ordem por chave, e onde inserções e exclusões são raras.


Resumo provisório dos procedimentos subjacentes

O feedback é muito bem-vindo, pois tenho certeza de que não acertei tudo.

  • Todas as matrizes são de tamanho n.
  • Matriz não classificada = .Add / .Remove é O (1), mas .Item (i) é O (n).
  • Matriz classificada = .Add / .Remove é O (n), mas .Item (i) é O (log n).

Dicionário

Memória

KeyArray(n) -> non-sorted array<pointer>
ItemArray(n) -> non-sorted array<pointer>
HashArray(n) -> sorted array<hashvalue>

Adicionar

  1. Adicionar HashArray(n) = Key.GetHash# O (1)
  2. Adicionar KeyArray(n) = PointerToKey# O (1)
  3. Adicionar ItemArray(n) = PointerToItem# O (1)

Remover

  1. For i = 0 to n, encontre ionde HashArray(i) = Key.GetHash # O (log n) (matriz classificada)
  2. Remova HashArray(i)# O (n) (matriz classificada)
  3. Remova KeyArray(i)# O (1)
  4. Remova ItemArray(i)# O (1)

Obter Item

  1. For i = 0 to n, encontre ionde HashArray(i) = Key.GetHash# O (log n) (matriz classificada)
  2. Retorna ItemArray(i)

Loop Through

  1. For i = 0 to n, Retorna ItemArray(i)

SortedDictionary

Memória

KeyArray(n) = non-sorted array<pointer>
ItemArray(n) = non-sorted array<pointer>
OrderArray(n) = sorted array<pointer>

Adicionar

  1. Adicionar KeyArray(n) = PointerToKey# O (1)
  2. Adicionar ItemArray(n) = PointerToItem# O (1)
  3. For i = 0 to n, encontre ionde KeyArray(i-1) < Key < KeyArray(i)(usando ICompare) # O (n)
  4. Adicione OrderArray(i) = n# O (n) (matriz classificada)

Remover

  1. For i = 0 to n, encontre ionde KeyArray(i).GetHash = Key.GetHash# O (n)
  2. Remova KeyArray(SortArray(i))# O (n)
  3. Remova ItemArray(SortArray(i))# O (n)
  4. Remova OrderArray(i)# O (n) (matriz classificada)

Obter Item

  1. For i = 0 to n, encontre ionde KeyArray(i).GetHash = Key.GetHash# O (n)
  2. Retorna ItemArray(i)

Loop Through

  1. For i = 0 to n, Retorna ItemArray(OrderArray(i))

SortedList

Memória

KeyArray(n) = sorted array<pointer>
ItemArray(n) = sorted array<pointer>

Adicionar

  1. For i = 0 to n, encontre ionde KeyArray(i-1) < Key < KeyArray(i)(usando ICompare) # O (log n)
  2. Adicionar KeyArray(i) = PointerToKey# O (n)
  3. Adicionar ItemArray(i) = PointerToItem# O (n)

Remover

  1. For i = 0 to n, encontre ionde KeyArray(i).GetHash = Key.GetHash# O (log n)
  2. Remova KeyArray(i)# O (n)
  3. Remova ItemArray(i)# O (n)

Obter Item

  1. For i = 0 to n, encontre ionde KeyArray(i).GetHash = Key.GetHash# O (log n)
  2. Retorna ItemArray(i)

Loop Through

  1. For i = 0 to n, Retorna ItemArray(i)
Ama
fonte
0

Tentando atribuir um pontuação de desempenho a cada caso apresentado por @Lev, usei os seguintes valores:

  • O (1) = 3
  • O (log n) = 2
  • O (n) = 1
  • O (1) ou O (n) = 2
  • O (log n) ou O (n) = 1,5

Os resultados são (mais altos = melhores):

Dictionary:       12.0 
SortedDictionary:  9.0 
SortedList:        6.5

É claro que cada caso de uso dará mais peso a certas operações.

Jaime
fonte
1
Como regra geral, o peso de O (log n) seria log (n) / log (2) (+1 cada vez que n dobra), enquanto o peso de O (n) seria n. Portanto, sua ponderação seria correta para tamanhos de até 4. Qualquer coisa além fará com que sua proporção de 2: 1 suba rapidamente. Por exemplo, se n = 100, então você deve ter O (log n) = 15. Seguindo um pensamento semelhante, seu O (1) pesaria 100. Conclusão: O (n) perde a batalha rapidamente. Caso contrário, significa que seu array é pequeno e a eficiência não é uma preocupação.
Ama