Como você classifica um dicionário por valor?

796

Muitas vezes tenho que classificar um dicionário, composto por chaves e valores, por valor. Por exemplo, tenho um hash de palavras e respectivas frequências, que quero ordenar por frequência.

Há um SortedListque é bom para um único valor (digamos frequência), que eu quero mapeá-lo de volta à palavra.

SortedDictionary ordena por chave, não por valor. Alguns recorrem a uma classe personalizada , mas existe uma maneira mais limpa?

Kalid
fonte
1
Além de classificar o dicionário (como na resposta aceita), você também pode criar um IComparerque faça o truque (é verdade que ele aceita uma chave para comparar, mas com uma chave, você pode obter um valor). ;-)
BrainSlugs83

Respostas:

520

Usar:

using System.Linq.Enumerable;
...
List<KeyValuePair<string, string>> myList = aDictionary.ToList();

myList.Sort(
    delegate(KeyValuePair<string, string> pair1,
    KeyValuePair<string, string> pair2)
    {
        return pair1.Value.CompareTo(pair2.Value);
    }
);

Como você está direcionando o .NET 2.0 ou superior, você pode simplificar isso na sintaxe lambda - é equivalente, mas menor. Se você estiver direcionando o .NET 2.0, poderá usar essa sintaxe apenas se estiver usando o compilador do Visual Studio 2008 (ou superior).

var myList = aDictionary.ToList();

myList.Sort((pair1,pair2) => pair1.Value.CompareTo(pair2.Value));
Leon Bambrick
fonte
26
Usei essa solução (obrigado!), Mas fiquei confuso por um minuto até ler a postagem de Michael Stum (e seu trecho de código de John Timney) e perceber que myList é um objeto secundário, uma lista de KeyValuePairs, criada no dicionário, e depois classificado.
22640 Robin Bennett
113
é um forro - Você não precisa de aparelho. ele pode ser reescrita comomyList.Sort((x,y)=>x.Value.CompareTo(y.Value));
Arnis Lapsa
25
Para classificar em ordem descendente, alterne x e y na comparação: myList.Sort ((x, y) => y.Value.CompareTo (x.Value));
Arturo16
8
Eu acho que vale a pena notar que isso requer o Linq para o método de extensão ToList.
Ben
17
Vocês estão preocupados em complicar isso - um dicionário já implementa IEnumerable, para que você possa obter uma lista ordenada como esta:var mySortedList = myDictionary.OrderBy(d => d.Value).ToList();
BrainSlugs83
523

Use LINQ:

Dictionary<string, int> myDict = new Dictionary<string, int>();
myDict.Add("one", 1);
myDict.Add("four", 4);
myDict.Add("two", 2);
myDict.Add("three", 3);

var sortedDict = from entry in myDict orderby entry.Value ascending select entry;

Isso também permitiria uma grande flexibilidade, pois você pode selecionar os 10, 20, 10% etc. etc. Ou, se estiver usando o índice de frequência de palavras type-ahead, também poderá incluir a StartsWithcláusula.

caryden
fonte
15
Como posso alterar o Sortedict de volta para um Dictionary <string, int>? Postado nova pergunta SO aqui: stackoverflow.com/questions/3066182/...
Kache
1
Infelizmente, isso não funciona no VS2005 por causa do .net framework 2.0 lá (sem LINQ). É bom ter também a resposta de Bambrick.
Smalcat
22
Não tenho certeza se sempre funciona porque a iteração no dicionário não garante que os KeyValuePairs sejam "puxados" na mesma ordem em que foram inseridos. Portanto, não importa se você usa orderby no LINQ porque o Dictionary pode alterar a ordem dos elementos inseridos. Geralmente, funciona como esperado, mas NÃO HÁ GARANTIA, especialmente para dicionários grandes.
Bozydar Sobczak
16
O tipo de retorno deve ser IEnumerable<KeyValuePair<TKey, TValue>>ou um OrderedDictionary<TKey, TValue>. Ou deve-se usar um SortedDictionarydesde o início. Para uma planície, Dictionaryo MSDN afirma claramente "A ordem na qual os itens são retornados é indefinida". Parece que a última edição de @ rythos42 é a culpada. :)
Boris B.
16
Por favor desconsidere todas as sugestões de .ToDictionary- dicionários padrão não garantem uma ordem de classificação
AlexFoxGill
254
var ordered = dict.OrderBy(x => x.Value);
sean
fonte
6
Não sei por que essa solução não é mais popular - talvez porque exija o .NET 3.5?
Contango
33
Essa é uma boa solução, mas deve ter isso logo antes do ponto e vírgula final: .ToDictionary (pair => pair.Key, pair => pair.Value);
theJerm
3
@theJerm, colocando os itens classificados de volta em um dicionário, a ordem é garantida? Pode funcionar hoje, mas não é garantido.
Nawfal # 31/13
1
Usando a estrutura 4.5, apenas verifiquei que ela não requer uma conversão de volta ao dicionário.
Jagd
12
Não deve haver uma conversão de volta para um dicionário, porque os dicionários não são ordenados. Não há garantia de que os KeyValuePairs permanecerão na ordem que você deseja.
precisa
165

Olhando em volta e usando alguns recursos do C # 3.0, podemos fazer isso:

foreach (KeyValuePair<string,int> item in keywordCounts.OrderBy(key=> key.Value))
{ 
    // do something with item.Key and item.Value
}

Esta é a maneira mais limpa que eu já vi e é semelhante à maneira Ruby de lidar com hashes.

Kalid
fonte
Eu estava tentando classificar um dicionário enquanto adicionava o KeyValuePairs a um ComboBox ... isso funcionou muito bem! Obrigado!
21139 Jason Down
6
Não se esqueça de adicionar o espaço para nome System.Linq ao usar esta sintaxe.
M. Dudley
4
(for KeyValuePair<string, int> item in keywordCounts.OrderBy(key => key.Value) select item).ToDictionary(t => t.Key, t => t.Value)- apenas uma pequena adição à sua resposta :) Obrigado, btw :)
Andrius Naruševičius
7
@ AndriusNaruševičius: Se você adicionar novamente os itens resultantes em um dicionário, você destruirá a ordem, pois não é garantido que os dicionários sejam solicitados de qualquer maneira específica .
OR Mapper
Isso foi útil. Como pode ser invertido para o contrário?
Dan Hastings
158

Você pode classificar um dicionário por valor e salvá-lo novamente (para que, quando for pesquisá-lo, os valores sejam ordenados):

dict = dict.OrderBy(x => x.Value).ToDictionary(x => x.Key, x => x.Value);

Claro, pode não estar correto, mas funciona.

Matt Frear
fonte
8
Você também pode usar OrderByDescending se desejar classificar em uma lista descendente.
Mendokusai
Funcionou para mim, embora eu tenha que alterá-lo um pouco para: Dictionary <key, value> dict = dict.OrderBy (x => x.Value) .ToDictionary (x => x.Key, x => x.Value);
21711 Josh
17
Este "trabalho" não é garantido. É um detalhe de implementação. Não precisa funcionar outras vezes. Resposta errada, com voto negativo.
Nawfal
4
Não é garantido que a saída do dicionário tenha uma ordem de classificação específica.
Roger Willcocks
5
Eu ficaria bastante preocupado em ver isso no código de produção. Não é garantido e pode ser alterado a qualquer momento. Não que eu evite soluções pragmáticas, isso apenas mostra uma falta de entendimento da estrutura de dados imo.
precisa saber é o seguinte
61

Em um nível alto, você não tem outra escolha a não ser percorrer todo o dicionário e analisar cada valor.

Talvez isso ajude: http://bytes.com/forum/thread563638.html Copiar / colar de John Timney:

Dictionary<string, string> s = new Dictionary<string, string>();
s.Add("1", "a Item");
s.Add("2", "c Item");
s.Add("3", "b Item");

List<KeyValuePair<string, string>> myList = new List<KeyValuePair<string, string>>(s);
myList.Sort(
    delegate(KeyValuePair<string, string> firstPair,
    KeyValuePair<string, string> nextPair)
    {
        return firstPair.Value.CompareTo(nextPair.Value);
    }
);
Michael Stum
fonte
3
stringnextPair -> string> nextPair stringfirstPair -> string> firstPair
Art
2
Solução não-Linq perfeita. Nunca deixa de me surpreender como as pessoas sentem a necessidade de usar o Linq, mesmo quando não é absolutamente necessário para resolver o problema. Com o C # 3, acredito que você também pode simplificar o Sort para usar apenas um lambda: myList.Sort ((x, y) => x.Value.CompareTo (y.Value));
25

Você nunca seria capaz de classificar um dicionário de qualquer maneira. Eles não são realmente encomendados. As garantias para um dicionário são de que a coleção de chaves e valores é iterável e os valores podem ser recuperados por índice ou chave, mas não há garantia de nenhuma ordem específica. Portanto, você precisaria inserir o par de valor do nome em uma lista.

Roger Willcocks
fonte
2
Um dicionário classificado pode gerar uma lista de pares de valores-chave.
recursivo
1
@ recursivo Qualquer dicionário deve produzir isso. É interessante notar que minha resposta, que está correta, mas incompleta (poderia ter feito o que os melhores exemplos fizeram) é votada abaixo de uma resposta inválida que resultaria em exceções em valores duplicados no dicionário original (as chaves são únicas, os valores não são garantidos )
Roger Willcocks
5
Esta é a resposta certa, porque o Dictionary não é classificável. Ele hashes chaves e você pode executar uma operação de busca extremamente rápida nele.
Paulius Zaliaduonis
@NetMage Sim. Mas a outra parte do problema é que eles queriam ordenar por Valor. E você só poderia fazer isso trocando Key e Value. E o valor não é necessariamente único, mas a chave deve ser.
Roger Willcocks
Sim, mas acho que sua resposta está incorreta devido às declarações absolutas contidas nela.
NetMage 30/09/19
21

Você não classifica entradas no dicionário. A classe de dicionário no .NET é implementada como uma hashtable - essa estrutura de dados não pode ser classificada por definição.

Se você precisar interagir com sua coleção (por chave) - precisará usar o SortedDictionary, que é implementado como uma Árvore de Pesquisa Binária.

No seu caso, no entanto, a estrutura de origem é irrelevante, porque é classificada por um campo diferente. Você ainda precisará classificá-lo por frequência e colocá-lo em uma nova coleção classificada pelo campo relevante (frequência). Portanto, nesta coleção, as frequências são chaves e as palavras são valores. Como muitas palavras podem ter a mesma frequência (e você a usará como chave), você não pode usar nem o Dictionary nem o SortedDictionary (eles exigem chaves exclusivas). Isso deixa você com uma SortedList.

Não entendo por que você insiste em manter um link para o item original em seu dicionário principal / primeiro.

Se os objetos em sua coleção possuírem uma estrutura mais complexa (mais campos) e você precisar acessá-los / classificá-los com eficiência usando vários campos diferentes como chaves - Você provavelmente precisará de uma estrutura de dados personalizada que consistir no armazenamento principal que suporta inserção e remoção de O (1) (LinkedList) e várias estruturas de indexação - Dictionaries / SortedDictionaries / SortedLists. Esses índices usariam um dos campos da sua classe complexa como uma chave e um ponteiro / referência para o LinkedListNode no LinkedList como um valor.

Você precisaria coordenar inserções e remoções para manter seus índices sincronizados com a coleção principal (LinkedList) e as remoções seriam muito caras, eu acho. É semelhante à maneira como os índices de banco de dados funcionam - eles são fantásticos para pesquisas, mas se tornam um fardo quando você precisa executar várias inserções e exclusões.

Todas as opções acima só são justificadas se você deseja fazer algum processamento pesado de consulta. Se você precisar produzi-los apenas uma vez classificados por frequência, poderá produzir uma lista de tuplas (anônimas):

var dict = new SortedDictionary<string, int>();
// ToDo: populate dict

var output = dict.OrderBy(e => e.Value).Select(e => new {frequency = e.Value, word = e.Key}).ToList();

foreach (var entry in output)
{
    Console.WriteLine("frequency:{0}, word: {1}",entry.frequency,entry.word);
}
Zar Shardan
fonte
15
Dictionary<string, string> dic= new Dictionary<string, string>();
var ordered = dic.OrderBy(x => x.Value);
return ordered.ToDictionary(t => t.Key, t => t.Value);
mrfazolka
fonte
12

Ou, por diversão, você pode usar alguns benefícios da extensão LINQ:

var dictionary = new Dictionary<string, int> { { "c", 3 }, { "a", 1 }, { "b", 2 } };
dictionary.OrderBy(x => x.Value)
  .ForEach(x => Console.WriteLine("{0}={1}", x.Key,x.Value));
mythz
fonte
10

Classificando uma SortedDictionarylista para vincular a um ListViewcontrole usando o VB.NET:

Dim MyDictionary As SortedDictionary(Of String, MyDictionaryEntry)

MyDictionaryListView.ItemsSource = MyDictionary.Values.OrderByDescending(Function(entry) entry.MyValue)

Public Class MyDictionaryEntry ' Need Property for GridViewColumn DisplayMemberBinding
    Public Property MyString As String
    Public Property MyValue As Integer
End Class

XAML:

<ListView Name="MyDictionaryListView">
    <ListView.View>
        <GridView>
            <GridViewColumn DisplayMemberBinding="{Binding Path=MyString}" Header="MyStringColumnName"></GridViewColumn>
            <GridViewColumn DisplayMemberBinding="{Binding Path=MyValue}" Header="MyValueColumnName"></GridViewColumn>
         </GridView>
    </ListView.View>
</ListView>
BSalita
fonte
7

A maneira mais fácil de obter um dicionário classificado é usar a SortedDictionaryclasse incorporada :

//Sorts sections according to the key value stored on "sections" unsorted dictionary, which is passed as a constructor argument
System.Collections.Generic.SortedDictionary<int, string> sortedSections = null;
if (sections != null)
{
    sortedSections = new SortedDictionary<int, string>(sections);
}

sortedSections vontade contém a versão classificada de sections

Alex Ruiz
fonte
7
Como você menciona no seu comentário, SortedDictionaryclassifica por teclas. O OP quer classificar por valor. SortedDictionarynão ajuda neste caso.
Marty Neal
Bem ... Se ele (você) puder, basta definir os valores como as chaves. Cronometrei as operações e sorteddictionary()sempre venci em pelo menos 1 microssegundo, e é muito mais fácil de gerenciar (como a sobrecarga de convertê-la novamente em algo facilmente interagida e gerenciada de maneira semelhante a um dicionário é 0 (já é um sorteddictionary)).
mbrownnyc
2
@mbrownnyc - não, fazer isso requer a suposição ou condição prévia de que os VALUES são únicos, o que não é garantido.
Roger Willcocks
6

As outras respostas são boas, se tudo o que você deseja é ter uma lista "temporária" classificada por Valor. No entanto, se você quiser ter um dicionário classificado por Keyque sincroniza automaticamente com outro dicionário que é classificada por Value, você pode usar a Bijection<K1, K2>classe .

Bijection<K1, K2> permite que você inicialize a coleção com dois dicionários existentes; portanto, se você deseja que um deles não seja classificado e que o outro seja classificado, você pode criar sua bijeção com código como

var dict = new Bijection<Key, Value>(new Dictionary<Key,Value>(), 
                               new SortedDictionary<Value,Key>());

Você pode usar dictcomo qualquer dicionário normal (implementado IDictionary<K, V>) e depois chamar dict.Inversepara obter o dicionário "inverso" que é classificado por Value.

Bijection<K1, K2>faz parte do Loyc.Collections.dll , mas se você quiser, poderá simplesmente copiar o código fonte em seu próprio projeto.

Nota : Caso haja várias chaves com o mesmo valor, você não poderá usá-lo Bijection, mas poderá sincronizar manualmente entre um comum Dictionary<Key,Value>e um BMultiMap<Value,Key>.

Qwertie
fonte
Semelhante a http://stackoverflow.com/questions/268321, mas pode substituir cada Dicionário por SortedDictionary. Embora as respostas pareçam não suportar valores duplicados (assume 1 a 1).
11136 crokusek
3

Suponha que tenhamos um dicionário como

   Dictionary<int, int> dict = new Dictionary<int, int>();
   dict.Add(21,1041);
   dict.Add(213, 1021);
   dict.Add(45, 1081);
   dict.Add(54, 1091);
   dict.Add(3425, 1061);
   sict.Add(768, 1011);

1) você pode usar temporary dictionary to store values as:

        Dictionary<int, int> dctTemp = new Dictionary<int, int>();

        foreach (KeyValuePair<int, int> pair in dict.OrderBy(key => key.Value))
        {
            dctTemp .Add(pair.Key, pair.Value);
        }
Akshay Kapoor
fonte
3

Na verdade, em C #, os dicionários têm métodos sort (); como você está mais interessado em classificar por valores, não é possível obter valores até fornecer a chave, resumindo, você precisa iterá-los usando o Order By do LINQ,

var items = new Dictionary<string, int>();
items.Add("cat", 0);
items.Add("dog", 20);
items.Add("bear", 100);
items.Add("lion", 50);

// Call OrderBy method here on each item and provide them the ids.
foreach (var item in items.OrderBy(k => k.Key))
{
    Console.WriteLine(item);// items are in sorted order
}

você pode fazer um truque,

var sortedDictByOrder = items.OrderBy(v => v.Value);

ou

var sortedKeys = from pair in dictName
            orderby pair.Value ascending
            select pair;

também depende de que tipo de valores você está armazenando,
é único (como string, int) ou múltiplo (como List, Array, classe definida pelo usuário);
se único, você pode fazer uma lista e aplicar classificação.
se classe definida pelo usuário, essa classe deve implementar IComparable
ClassName: IComparable<ClassName>e substituir compareTo(ClassName c) , pois são mais rápidas que o LINQ e mais orientadas a objetos.

Ashish Kamble
fonte
0

Namespace necessário: using System.Linq;

Dictionary<string, int> counts = new Dictionary<string, int>();
counts.Add("one", 1);
counts.Add("four", 4);
counts.Add("two", 2);
counts.Add("three", 3);

Ordenar por desc:

foreach (KeyValuePair<string, int> kvp in counts.OrderByDescending(key => key.Value))
{
// some processing logic for each item if you want.
}

Ordem por Asc:

foreach (KeyValuePair<string, int> kvp in counts.OrderBy(key => key.Value))
{
// some processing logic for each item if you want.
}
Jaydeep Shil
fonte
-2

Você pode classificar o dicionário por valor e obter o resultado no dicionário usando o código abaixo:

Dictionary <<string, string>> ShareUserNewCopy = 
       ShareUserCopy.OrderBy(x => x.Value).ToDictionary(pair => pair.Key,
                                                        pair => pair.Value);                                          
pawan Kumar
fonte
8
Ao colocar os itens classificados novamente em um dicionário, eles não são mais garantidos para serem classificados quando você enumera o novo dicionário.
Marty Neal
2
E por que você está adicionando esta resposta quando já está respondida?
Nawfal # 31/13
-2

Como você possui um dicionário, é possível classificá-los diretamente nos valores usando abaixo de um forro:

var x = (from c in dict orderby c.Value.Order ascending select c).ToDictionary(c => c.Key, c=>c.Value);
aggaton
fonte
4
Esta resposta está incorreta, pois não há garantia de
OR Mapper