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

planeacion de la capacidad ejemplos

Question

Si tengo, por ejemplo, 100 elementos que se almacenarán en un diccionario, ¿debo inicializarlo así?

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

Tengo entendido que el diccionario .NET se redimensiona internamente cuando alcanza una carga determinada y que el umbral de carga se define como una proporción de la capacidad.

Eso sugeriría que si se añadieran 100 elementos al diccionario anterior, se redimensionaría cuando se añadiera 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 se redimensiona (y utiliza todas sus ranuras), entonces el rendimiento debe degradarse debido a estas colisiones.

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

Answer 1

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

Answer 2

Hice una prueba rápida, probablemente no científica, pero si configuré el tamaño, tardé 1.2207780 segundos en agregar un millón de elementos y tardé 1.5024960 segundos en agregarlo si no le daba un tamaño al diccionario ... esto me parece insignificante .

Este es mi código de prueba, tal vez alguien puede 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

Sí, a diferencia de una HashTable que usa el reafilado como método para resolver colisiones, Dictionary usará encadenamiento. Entonces sí, es bueno usar el conteo. Para una HashTable es probable que desee utilizar count * (1/fillfactor)

Answer 4

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

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

1. El Dictionary 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 o más lento;
3. Las operaciones ADD no requerirán más asignaciones de memoria (quizás costosas) y, por lo tanto, serán más rápidas.

Desde MSDN :

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

Si se puede estimar el tamaño de la colección, al especificar la capacidad inicial se elimina la necesidad de realizar una serie de operaciones de cambio de tamaño al agregar elementos al diccionario (TKey, TValue).

Answer 5

Lo que debe inicializar la capacidad del diccionario depende de dos factores: (1) la distribución de la función gethashcode, y (2) la cantidad de elementos que debe insertar.

Su función hash debe ser distribuida aleatoriamente, o debe estar especialmente formulada para su conjunto de entrada. Supongamos el primero, pero si está interesado en la segunda búsqueda, tenga funciones hash perfectas.

Si tiene 100 elementos para insertar en el diccionario, una función hash distribuida aleatoriamente, y establece la capacidad en 100, luego cuando inserta el ítem i-ésimo en la tabla hash, tiene una probabilidad (i-1) / 100 de que la i-ésima el artículo colisionará con otro artículo luego de la inserción. Si desea reducir esta probabilidad de colisión, aumente la capacidad. Duplicar la capacidad esperada reduce a la mitad las posibilidades de colisión.

Además, si sabe con qué frecuencia va a acceder a cada elemento en el diccionario, puede insertar los elementos en orden de frecuencia decreciente ya que los artículos que inserta primero serán, en promedio, más rápidos de acceder.

Answer 6

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