¿Un objeto de diccionario ocupa más memoria que las matrices paralelas?

Answer 1

Necesitamos definir más claramente “diccionario” para responder a esto. En la versión más general, “diccionario” puede significar simplemente “una estructura de datos con algunas operaciones de soporte que admiten el acceso de valores basado en claves”. En ese caso, sus matrices paralelas, más los métodos que admiten el acceso a las entradas en la matriz de valores en función de la entrada en la matriz de claves, ES un diccionario. Entonces (ignorando el tamaño de los métodos que acabo de mencionar), no, un diccionario puede tener exactamente la misma memoria que la versión de arrays paralelos.

La mayoría de las veces, sin embargo, los diccionarios vienen con requisitos adicionales. En lugar de “acceso basado en claves de valores”, prometen un acceso eficiente y basado en claves de valores. Por lo general, eso significa que el diccionario utiliza internamente una estructura ordenada que permite el acceso O (log n) de los elementos, o una tabla hash que permite el acceso O (1) a los elementos.

Si solo se asegura de que sus arreglos paralelos se mantienen ordenados por clave, entonces nuevamente, sus arreglos paralelos siguen siendo un diccionario; ergo el diccionario y las matrices paralelas toman la misma cantidad de memoria. Y los accesos clave en esta estructura de datos serán un poco más rápidos que usar un árbol debido a que se requieren menos referencias, y debido a que los arreglos probablemente estén densamente agrupados en la memoria mientras el árbol está fragmentado, por lo que las búsquedas de claves en el arreglo causarán menos fallas de página, lo cual es un acuerdo mucho más grande que el número de desreferencias requeridas. Sin embargo, pagará la penalización de tener que ampliar la matriz periódicamente, lo que causará una pausa periódica (y, a menos que su código esté prestando mucha atención, aparentemente impredecible) durante la inserción. Con un árbol, no consigues esa pausa. El conjunto paralelo será más rápido en general para las operaciones mixtas de lectura / escritura, y potencialmente mucho más rápido para los casos de uso con mucha lectura, pero el árbol mostrará un rendimiento más predecible para las inserciones.

Si está utilizando una tabla hash, que en muchos SDK es la predeterminada: C #, Python, Ruby; Java proporciona múltiples implementaciones, pero el hecho de tomar HashMap por defecto es la decisión correcta, entonces el diccionario será algo más grande que las matrices paralelas. Esto se debe a que las implementaciones eficientes de tablas hash generalmente mantienen una matriz de mayor capacidad que la cantidad actual de elementos en la tabla (las tablas hash son más eficientes cuando están menos del 75% llenas; podría tener ese número incorrecto, simplemente sacándolo de la memoria ). Por lo tanto, como mínimo, la implementación de la tabla hash es probablemente un 33% más grande que la versión de arreglos paralelos. Sin embargo, muchas implementaciones de tablas hash admiten el agrupamiento cuando las funciones de hash chocan entre teclas distintas, y eso conlleva una sobrecarga adicional (generalmente implementada como una matriz o lista; por lo tanto, para cada contenedor de hash que contiene una entrada, agregue la sobrecarga que la lista requiere).

En pocas palabras: la mayoría de las veces, un diccionario es una tabla hash, así que sí se necesita más memoria que las matrices paralelas. Pero no siempre.