¿Debería inicializarse un diccionario genérico .NET con una capacidad igual a la cantidad de elementos que contendrá?

Question

Si tengo, digamos, 100 elementos que se almacenarán en un diccionario, ¿debería inicializarlo así?

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

Entiendo que el diccionario .NET se redimensiona internamente cuando alcanza una carga determinada, y que el umbral de carga se define como una relación de la capacidad.

Eso sugeriría que si se agregan 100 elementos al diccionario anterior, se redimensionará cuando se agregue uno de los elementos. Cambiar el tamaño de un diccionario es algo que me gustaría evitar, ya que tiene un impacto en el rendimiento y es un desperdicio de memoria.

La probabilidad de colisiones hash es proporcional a la carga en un diccionario. Por lo tanto, incluso si el diccionario no cambia de tamaño (y utiliza todas sus ranuras), el rendimiento debe disminuir debido a estas colisiones.

¿Cómo debería uno decidir qué capacidad para inicializar el diccionario, suponiendo que sepa cuántos elementos habrá dentro del diccionario?

Answer 1

A lo que debe inicializar la capacidad del diccionario depende de dos factores: (1) La distribución de la función gethashcode, y (2) Cuántos elementos debes insertar.

Su función hash debe ser distribuida al azar, o debe estar especialmente formulada para su conjunto de entradas. Asumamos el primero, pero si está interesado en el segundo, busque funciones hash perfectas.

Si tiene 100 elementos para insertar en el diccionario, una función hash distribuida al azar, y establece la capacidad en 100, entonces cuando inserta el ítem ith en la tabla hash tiene una probabilidad (i-1) / 100 que el ítem chocará con otro ítem al insertarse. Si desea reducir esta probabilidad de colisión, aumente la capacidad. Duplicar la capacidad esperada reduce a la mitad la posibilidad de colisión.

Además, si sabe con qué frecuencia va a acceder a cada elemento del diccionario, es posible que desee insertar los elementos en orden decreciente de frecuencia, ya que los elementos que inserte primero tendrán un acceso más rápido en promedio.

Answer 2

Hice una prueba rápida, probablemente no científica, pero si establecí el tamaño, tomó 1.2207780 segundos para agregar un millón de artículos y tomó 1.5024960 segundos para agregar si no le di una talla al Diccionario ... esto parece insignificante para mí.

Aquí está mi código de prueba, tal vez alguien pueda hacer una prueba más rigurosa, pero dudo que importe.

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

Creo que estás complicando demasiado las cosas. Si sabe cuántos elementos habrá en su diccionario, entonces por supuesto especifique eso en la construcción. Esto ayudará al diccionario a asignar el espacio necesario en sus estructuras de datos internas para evitar la reasignación y la reorganización de los datos.

Answer 4

La especificación de la capacidad inicial del constructor Dictionary aumenta el rendimiento porque habrá menos número de tamaños en las estructuras internas que almacenan los valores del diccionario durante las operaciones de ADD.

Teniendo en cuenta que especifica una capacidad inicial de k para el constructor Dictionary , entonces:

1. El Diccionario reservará la cantidad de memoria necesaria para almacenar k elementos;
2. El rendimiento de QUERY contra el diccionario no se ve afectado y no será más rápido ni más lento;
3. Las operaciones de AGREGAR no requerirán más asignaciones de memoria (quizás caras) y, por lo tanto, serán más rápidas.

De MSDN :

  

La capacidad de un diccionario (TKey,   TValue) es el número de elementos que   Se puede agregar al Diccionario (TKey,   TValue) antes de cambiar el tamaño es necesario.   A medida que los elementos se agregan a un   Diccionario (TKey, TValue), la capacidad   se incrementa automáticamente según sea necesario   mediante la reasignación de la matriz interna.

     

Si el tamaño de la colección puede ser   estimado, especificando el inicial   capacidad elimina la necesidad de   realizar una serie de cambio de tamaño   operaciones mientras se añaden elementos a   el Diccionario (TKey, TValue).

Answer 5

Sí, a diferencia de un HashTable que usa el refrito como el método para resolver colisiones, Diccionario usará el encadenamiento. Así que sí, es bueno usar la cuenta. Para un HashTable es probable que desee usar count * (1 / fillfactor)

Answer 6

El tamaño inicial es solo una sugerencia. Por ejemplo, a la mayoría de las tablas hash les gusta tener tamaños que son números primos o una potencia de 2.