¿Hay un límite de entradas en un diccionario <>?

Question

Tengo alrededor de 3000 archivos diferentes que necesito organizar y recuperar en diferentes momentos durante el juego.

Creé mi propia estructura de variables. Estaba pensando en crear un "Diccionario" al comienzo de mi aplicación, y simplemente cargar todos mis archivos antes de que comience el juego.

Me pregunto acerca del rendimiento: ¿un diccionario con tantas entradas hará que mi aplicación sea lenta? ¿Un diccionario grande haría que "TryGetValue" y "ContainsKey" corrieran más despacio?

gracias por el consejo!

Answer 1

TryGetValue y ContainsKey deberían ser bastante rápidos en ese tamaño, siempre que la clave tenga hashes bien distribuidos.

Un diccionario tiene un número indexable de "cubos". Cuando agrega o busca un valor con una clave, tomará el valor devuelto por GetHashCode(), lo bajará de nuevo para que sea menor que el número de segmentos (generalmente algo simple como módulo, pero la implementación no está definida), y mira en el cubo relevante.

El cucharón actualmente tendrá cero o más elementos. El diccionario comparará cada elemento con la clave usando .Equals().

El primer bit de encontrar el cubo correcto va a ser en tiempo constante O (1). La segunda parte de la comparación de la clave con las claves del cubo va a estar en el tiempo lineal O (n), donde n se relaciona solo con el número de elementos en ese depósito, no en toda la colección.

En general, debe haber muy pocos elementos en cada segmento (la cantidad de cubos crecerá para tratar de mantener este el caso) por lo que la operación es esencialmente un tiempo constante.

Sin embargo, si sus códigos hash están mal implementados, habrá muchas claves en el mismo cubo. La complejidad del tiempo se acercará más y más a O (n), como se puede ver al experimentar con un objeto con un GetHashCode deliberadamente malo que simplemente devuelve 0 cada vez. En el peor de los casos, es peor que una Lista, ya que una Lista también es O (n), pero el Diccionario tiene más sobrecarga.

¿Esto significa que debe preocuparse? No, incluso métodos de hashing relativamente ingenuos deberían dar resultados relativamente buenos. Si está utilizando una clave de cadena, probablemente ya sea más que suficiente. Si está utilizando un tipo incorporado simple, aún más.

Si encuentra que el acceso al diccionario es lento, debe prestar atención a esto y corregir el método GetHashCode() o crear un IEqualityComparer (que le permite definir reglas externas para GetHashCode() e Igual () para usar con diccionarios, hashsets, etc.

Lo más probable es que 3000 no sea nada, todo irá bien.

Answer 2

3000 entradas es insignificante para un Dictionary<>. Eso no será una fuente de desaceleración.

Leyendo 3000 archivos diferentes en la memoria al inicio, por otro lado, será lento. Será mucho mejor leer los archivos en la memoria solo en el momento en que los necesite, pero guardarlos en la memoria para acceder posteriormente.

Answer 3

Los diccionarios en .NET utilizan un esquema de búsqueda de tabla hash, por lo que agregar entradas tiene muy poco efecto, si corresponde, en el rendimiento de búsqueda. El único problema que tendrá es el uso de la memoria. Un diccionario de 3000 elementos consumirá aproximadamente 3000 veces el almacenamiento utilizado por la clave más los tipos de valor. Si se trata de una simple estructura sin grandes blobs binarios, 3000 es francamente pequeño.

Answer 4

No, no lo hará. Se consumirá memoria, pero TryGetValue y ContainKey deberían ser bastante rápidos, ya que un diccionario es una tabla hash y el acceso a los elementos mediante la clave es constante y no dependerá de la cantidad de elementos.

Answer 5

Al proporcionar el algoritmo de código hash para el tipo de clave de diccionario, se distribuyen los códigos hash de manera relativamente uniforme en el espacio Int32, la búsqueda de código hash no se ve afectada por el tamaño del diccionario.

Ver http://en.wikipedia.org/wiki/Hashtable#Performance_analysis para más detalles.

Answer 6

Su cuello de botella no será el rendimiento del diccionario sino la lectura de 3000 archivos.

Answer 7

Al igual que con la mayoría de las cosas con las computadoras (y en particular con el rendimiento), "Depende (tm)"

Todo depende de la IMPLEMENTACIÓN DE diccionario.

Se podría hacer como un árbol binario, en cuyo caso la búsqueda debería ser O (log2 N), lo que significa que el tiempo de búsqueda crece lentamente a medida que crece el tamaño del diccionario.

Podría hacerse como una tabla hash, que, en teoría es O (1), lo que significa que una búsqueda siempre llevará la misma cantidad de tiempo independientemente del tamaño del diccionario, pero esa es la teoría, y Depende de la cantidad de cubos y la calidad del código hash. Si muchos elementos terminan en el mismo cubo, lo que requiere una búsqueda lineal, se ralentizará considerablemente a medida que el diccionario crezca.

Sin embargo, el diccionario tendría que crecer más allá de 3000 en varios órdenes de magnitud antes de ver una diferencia notable.

Answer 8

Hay un límite, pero 3000 no está ni cerca de eso. Dictionary<> usa Object.GetHashCode() para oraginizar sus claves, lo que devuelve int.Por lo tanto, puede almacenar un máximo de 2^32 (4,294,967,296) claves antes de que se produzca una colisión. Sin embargo, debido a la forma en que normalmente se calculan los códigos hash de .Net, es probable que haya muchas colisiones a medida que se acerque a este número mágico.

Agregar más teclas no ralentizará TryGetValue y ContainsKey - son operaciones O(1).