Um dicionário genérico .NET deve ser inicializado com uma capacidade igual ao número de itens que conterá?

Question

Se eu tiver, digamos, 100 itens que serão armazenados em um dicionário, devo inicializá -lo assim?

var myDictionary = new Dictionary<Key, Value>(100);

Meu entendimento é que o dicionário .NET se redimensiona internamente quando atinge um determinado carregamento e que o limite de carregamento é definido como uma proporção da capacidade.

Isso sugeriria que, se 100 itens fossem adicionados ao dicionário acima, ele redimensione quando um dos itens fosse adicionado. Redimensionar um dicionário é algo que eu gostaria de evitar, pois tem um sucesso de desempenho e é um desperdício de memória.

A probabilidade de colisões de hash é proporcional ao carregamento em um dicionário. Portanto, mesmo que o dicionário não seja redimensionado (e use todos os seus slots), o desempenho deve se degradar devido a essas colisões.

Como é melhor decidir que capacidade inicializar o dicionário, supondo que você saiba quantos itens estarão dentro do dicionário?

Answer 1

O que você deve inicializar a capacidade do dicionário depende de dois fatores: (1) a distribuição da função do código do gethash e (2) quantos itens você deve inserir.

Sua função de hash deve ser distribuída aleatoriamente, ou deve ser especialmente formulada para o seu conjunto de informações. Vamos supor o primeiro, mas se você estiver interessado no segundo, as funções de hash perfeitas.

Se você tem 100 itens a serem inseridos no dicionário, uma função de hash distribuída aleatoriamente e você define a capacidade para 100, então quando insere o ITH Item na tabela de hash, você tem uma probabilidade (i-1) / 100 de que o ITH O item colidirá com outro item após a inserção. Se você deseja diminuir essa probabilidade de colisão, aumente a capacidade. Dobrar a capacidade esperada pela metade da chance de colisão.

Além disso, se você souber com que frequência acessará cada item no dicionário, poderá inserir os itens em ordem de diminuição da frequência, pois os itens que você inserir primeiro serão, em média, mais rapidamente o acesso.

Answer 2

Fiz um teste rápido, provavelmente não científico, mas se eu definir o tamanho, levou 1.2207780 segundos para adicionar um milhão de itens e foram necessários 1.5024960 segundos para acrescentar se não dei um tamanho ao dicionário ... Isso parece insignificante para mim .

Aqui está o meu código de teste, talvez alguém possa fazer um teste mais rigoroso, mas duvido que isso importa.

static void Main(string[] args)
        {
            DateTime start1 = DateTime.Now;
            var dict1 = new Dictionary<string, string>(1000000);

            for (int i = 0; i < 1000000; i++)
                dict1.Add(i.ToString(), i.ToString());

            DateTime stop1 = DateTime.Now;

            DateTime start2 = DateTime.Now;
            var dict2 = new Dictionary<string, string>();

            for (int i = 0; i < 1000000; i++)
                dict2.Add(i.ToString(), i.ToString());

            DateTime stop2 = DateTime.Now;

            Console.WriteLine("Time with size initialized: " + (stop1.Subtract(start1)) + "\nTime without size initialized: " + (stop2.Subtract(start2)));
            Console.ReadLine();
        }

Answer 3

Eu acho que você está complicando demais. Se você souber quantos itens estarão no seu dicionário, especifique isso na construção. Isso ajudará o dicionário a alocar o espaço necessário em suas estruturas de dados internas para evitar realocar e reorganizar os dados.

Answer 4

Especificando a capacidade inicial para o Dictionary O construtor aumenta o desempenho, porque haverá menos número de redes para as estruturas internas que armazenam os valores do dicionário durante as operações de adição.

Considerando que você especifica uma capacidade inicial de k para o Dictionary construtor então:

1. o Dictionary reservará a quantidade de memória necessária para armazenar K elementos;
2. O desempenho da consulta contra o dicionário não é afetado e não será mais rápido ou mais lento;
3. As operações adicionais não exigirão mais alocações de memória (talvez caras) e, portanto, serão mais rápidas.

A partir de Msdn:

A capacidade de um dicionário (TKEY, TVALUE) é o número de elementos que podem ser adicionados ao dicionário (TKEY, TVALUE) antes de redimensionar. À medida que os elementos são adicionados a um dicionário (TKEY, TVALUE), a capacidade é aumentada automaticamente conforme exigido pela realocação da matriz interna.

Se o tamanho da coleção puder ser estimado, especificar a capacidade inicial eliminar a necessidade de executar várias operações de redimensionamento enquanto adiciona elementos ao dicionário (TKEY, TVALUE).

Answer 5

Sim, ao contrário de um HashTable que usa a reformulação como método para resolver colisões, Dictionary usará o encadeamento. Então, sim, é bom usar a contagem. Para HashTable Você provavelmente quer usar count * (1/fillfactor)

Answer 6

O tamanho inicial é apenas uma sugestão. Por exemplo, a maioria das tabelas de hash gosta de ter tamanhos que são números primos ou uma potência de 2.