Diferença entre Lookup () e Dictionary (Of list ())

165

Estou tentando entender quais estruturas de dados são as mais eficientes e quando / onde usar quais.

Agora, pode ser que eu simplesmente não entenda bem as estruturas, mas como é ILookup(of key, ...)diferente de uma Dictionary(of key, list(of ...))?

Também onde eu gostaria de usar ILookupe onde seria mais eficiente em termos de velocidade do programa / memória / acesso a dados, etc?

John Bustos
fonte
1
pode-se também quer ver o-que-é-a-ponto-de-lookuptkey-TElement
Nawfal

Respostas:

255

Duas diferenças significativas:

  • Lookupé imutável. Yay :) (pelo menos, acredito que a Lookupclasse concreta é imutável e a ILookupinterface não fornece nenhum membro mutante. Poderia haver outras implementações mutáveis, é claro.)
  • Quando você pesquisa uma chave que não está presente em uma pesquisa, você recebe uma sequência vazia de volta em vez de a KeyNotFoundException. (Portanto, não há TryGetValue, AFAICR.)

É provável que sejam equivalentes em eficiência - a pesquisa pode muito bem usar Dictionary<TKey, GroupingImplementation<TValue>>os bastidores, por exemplo. Escolha entre eles com base em seus requisitos. Pessoalmente, acho que a pesquisa geralmente se encaixa melhor que a Dictionary<TKey, List<TValue>>, principalmente devido aos dois primeiros pontos acima.

Note-se que como um detalhe de implementação, a implementação concreta de IGrouping<,>que é usado para os valores de instrumentos IList<TValue>, o que significa que é eficaz para utilizar com Count(), ElementAt()etc.

Jon Skeet
fonte
Se uma pesquisa de chave inexistente resultar em uma sequência vazia em vez de uma exceção, ela não poderá ser usada como uma coleção de uso geral. É meio bom no caso de uma coleção imutável, que é um subproduto das consultas linq.
Nawfal
@nawfal - é exatamente para isso que servem as pesquisas. Do msdn : "Você pode criar uma instância de uma pesquisa <TKey, TElement> chamando ToLookup em um objeto que implementa IEnumerable <T>."
Niall Connaughton
50

Interessante que ninguém tenha declarado a maior diferença real (extraído diretamente do MSDN ):

Uma pesquisa se assemelha a um dicionário. A diferença é que um dicionário mapeia chaves para valores únicos, enquanto uma pesquisa mapeia chaves para coleções de valores.

Mladen Mihajlovic
fonte
51
Verifique a pergunta: trata-se da diferença entre uma Pesquisa <TKey, TValue> e um Dicionário <TKey, Lista <TValue>>, para que essa diferença já esteja explícita.
Martão
5
@Martao Algumas pessoas acham essa pergunta ao pesquisar no Google para entender a diferença entre pesquisas e dicionários. Esta resposta é realmente útil.
jakubiszon 9/06
34

Tanto a Dictionary<Key, List<Value>>como a Lookup<Key, Value>logicamente podem conter dados organizados de maneira semelhante e ambos têm a mesma ordem de eficiência. A principal diferença é que Lookupé imutável: ele não possui Add()métodos e construtor público (e, como Jon mencionou, você pode consultar uma chave inexistente sem uma exceção e ter a chave como parte do agrupamento).

Quanto a qual você usa, isso realmente depende de como você deseja usá-las. Se você estiver mantendo um mapa da chave para vários valores que estão sendo constantemente modificados, então a Dictionary<Key, List<Value>>provavelmente será melhor, pois é mutável.

Se, no entanto, você tiver uma sequência de dados e desejar apenas uma visualização somente leitura dos dados organizados por chave, uma pesquisa será muito fácil de construir e fornecerá um instantâneo somente leitura.

James Michael Hare
fonte
11

A principal diferença entre an ILookup<K,V>e a Dictionary<K, List<V>>é que um dicionário é mutável; você pode adicionar ou remover chaves e também adicionar ou remover itens da lista pesquisada. Um ILookupé imutável e não pode ser modificado depois de criado.

A implementação subjacente de ambos os mecanismos será igual ou semelhante, portanto, a velocidade de pesquisa e a pegada de memória serão aproximadamente as mesmas.

Servy
fonte
1
@JohnBustos Em termos de desempenho, não. É puramente lógico. Você pode passar referências à estrutura para não se preocupar com alguém que a modifique de baixo de você. Você pode fazer suposições sobre o fato de ser imutável que você não pudesse se fosse mutável.
Servy
Obrigado, Servy, esse é um ponto muito bom quando você repassa tantas variáveis ​​ByRef com frequência - Pelo menos essa você tem certeza de que não pode ser modificada. Obrigado!
31512 John Bustos
2
@JohnBustos Lembre-se de que o método padrão de passar um parâmetro de método é por valor, você precisa adicionar explicitamente byref, e isso é algo que deve ser feito muito raramente. Essas estruturas de dados são classes, o que os torna tipos de referência; portanto, passar o valor é o valor da referência; é por isso que passá-lo para outro método pode causar alterações visíveis no chamador.
Servy
Obrigado, Servy, que abre uma nova lata de minhocas para mim em termos do que venho fazendo :), mas entendo o que você está dizendo. Obrigado!!
John Bustos
Sob as cobertas, você sabe se a Pesquisa usa hashbuckets para a chave?
Paparazzo
10

Outra diferença ainda não mencionada é que Lookup () suporta chaves nulas :

A classe Lookup implementa a interface ILookup. A pesquisa é muito semelhante a um dicionário, exceto que vários valores podem ser mapeados para a mesma chave e que chaves nulas são suportadas.

Noble_Bright_Life
fonte
4

Quando a exceção não é uma opção, vá para Pesquisa

Se você está tentando obter uma estrutura tão eficiente quanto uma, Dictionarymas não sabe ao certo que não há chave duplicada na entrada, Lookupé mais seguro.

Como mencionado em outra resposta, ele também suporta chaves nulas e retorna sempre um resultado válido quando consultado com dados arbitrários; portanto, ele parece mais resiliente a entradas desconhecidas (menos propenso que o Dictionary a gerar exceções).

E é especialmente verdade se você comparar com a System.Linq.Enumerable.ToDictionaryfunção:

// won't throw
new[] { 1, 1 }.ToLookup(x => x); 

// System.ArgumentException: An item with the same key has already been added.
new[] { 1, 1 }.ToDictionary(x => x);

A alternativa seria escrever seu próprio código de gerenciamento de chaves duplicado dentro de um foreachloop.

Considerações sobre desempenho, Dicionário: um vencedor claro

Se você não precisar de uma lista e gerenciar um grande número de itens, Dictionary(ou mesmo sua própria estrutura personalizada) seria mais eficiente:

        Stopwatch stopwatch = new Stopwatch();
        var list = new List<string>();
        for (int i = 0; i < 5000000; ++i)
        {
            list.Add(i.ToString());
        }
        stopwatch.Start();
        var lookup = list.ToLookup(x => x);
        stopwatch.Stop();
        Console.WriteLine("Creation: " + stopwatch.Elapsed);

        // ... Same but for ToDictionary
        var lookup = list.ToDictionary(x => x);
        // ...

Como Lookupé necessário manter uma lista de itens para cada chave, é mais lento que o Dicionário (cerca de 3x mais lento para um grande número de itens)

Velocidade de pesquisa: Criação: 00: 00: 01.5760444

Velocidade do dicionário: Criação: 00: 00: 00.4418833

Fab
fonte