Alternativas HashMap para el almacenamiento de datos con memoria eficiente

Question

Actualmente tengo un programa de tipo hoja de cálculo que conserva sus datos en una Lista de Arratos de HashMaps. Sin duda se sorprenderá cuando le digo que esto no ha resultado ideal. La sobrecarga parece usar 5 veces más memoria que los datos en sí.

This question pregunta acerca de las bibliotecas de colecciones eficientes, y la respuesta fue usar Google Collections. Mi seguimiento es "¿qué parte?". He estado leyendo la documentación, pero no creo que dé una buena idea de qué clases son adecuadas para esto. (También estoy abierto a otras bibliotecas o sugerencias).

Así que estoy buscando algo que me permita almacenar datos densos de tipo hoja de cálculo con una sobrecarga de memoria mínima.

• Mis columnas están actualmente referenciados por objetos Field, filas por sus índices, y los valores son objetos, casi siempre Cuerdas
• Algunas columnas tendrán una gran cantidad de valores repetidos
• operaciones primarias son actualizar o eliminar registros basados ​​en valores de ciertos campos, y también agregar/eliminar/combinar columnas

Conozco opciones como H2 y Derby, pero en este caso no estoy buscando utilizar una base de datos incrustada.

EDIT: Si está sugiriendo bibliotecas, también agradecería que me indicara una o dos clases particulares que se aplicarían aquí. Mientras que la documentación de Sun generalmente incluye información sobre qué operaciones son O (1), que son O (N), etc., no veo mucho de eso en bibliotecas de terceros, ni realmente ninguna descripción de qué clases son las más adecuadas para qué .

Answer 1

Supongo que tiene un mapa de Map<ColumnName,Column>, donde la columna es realmente algo así como ArrayList<Object>.

algunas posibilidades -

• ¿Estás completamente seguro de que la memoria es un problema? Si solo te preocupa el tamaño, valdría la pena confirmar que esto realmente será un problema en un programa en ejecución. Se necesitan muchísimas filas y mapas para completar una JVM.

• Puede probar su conjunto de datos con diferentes tipos de mapas en las colecciones. Dependiendo de sus datos, también puede inicializar mapas con combinaciones predeterminadas de tamaño/factor de carga que pueden ayudar. Me he equivocado con esto en el pasado, es posible que obtengas una reducción del 30% en la memoria si tienes suerte.

• ¿Qué hay de almacenar sus datos en una única estructura de datos parecida a una matriz (una implementación de biblioteca existente o algo así como un envoltorio alrededor de una Lista de Listas), con un solo mapa que asigna claves de columna a columnas de matriz?

Answer 2

Algunas columnas tendrán una gran cantidad de valores repetidos

sugiere inmediatamente a mí el posible uso de la FlyWeight pattern, independientemente de la solución que elija para sus colecciones.

Answer 3

colecciones Trove deben tener un cuidado especial sobre el espacio ocupado (creo que también se han adaptado las estructuras de datos si se adhieren a los tipos primitivos) .. echar un vistazo here.

De lo contrario, puede probar con Apache collections .. ¡simplemente hagan sus puntos de referencia!

En anycase, si tiene muchas referencias en torno a los elementos mismos tratan de diseñar un patrón adecuado (como flyweight)

Answer 4

mantiene sus datos en un ArrayList de HashMaps
Bueno, esta parte parece terriblemente ineficiente para mí. HashMap vacío ya asignará 16 * size of a pointer bytes (16 representa la capacidad inicial predeterminada), más algunas variables para el objeto hash (14 + psize). Si tienes muchas filas escasamente llenas, esto podría ser un gran problema.

Una opción sería usar un único hash grande con una clave compuesta (combinación de fila y columna). Aunque eso no hace que las operaciones en filas completas sean muy efectivas.

Además, dado que no menciona la operación de agregar celda, puede crear hashes con solo el almacenamiento interno necesario (parámetro initialCapacity).

No sé mucho sobre las colecciones de google, así que no puedo ayudar. Además, si encuentra alguna optimización útil, ¡por favor publique aquí! Sería interesante saber

Answer 5

Desde su descripción, parece que en lugar de un ArrayList de HashMaps que más bien desea un HashMap (Vinculado) de ArrayList (cada ArrayList sería una columna).

Agregaría un doble mapa desde el nombre de campo al número de columna, y algunos captadores/definidores inteligentes que nunca lanzan IndexOutOfBoundsException.

También puede usar un ArrayList<ArrayList<Object>> (básicamente una matriz dentada creciente dinámicamente) y mantener el mapeo fuera de los nombres de campo (columna).

Algunas columnas tendrán una gran cantidad de valores repetidos

dudo esto es importante, especialmente si son Cuerdas, (que son internalizadas) y su colección almacenarían referencias a ellos.

Answer 6

Guava incluye una interfaz Table y una implementación basada en hash. Parece un ajuste natural a su problema. Tenga en cuenta que esto aún está marcado como beta.

Answer 7

Suponiendo que todas sus filas tienen la mayoría de las mismas columnas, puede usar una matriz para cada fila y un Map < ColumnKey, Integer> para buscar qué columnas se refieren a qué celda. De esta forma, solo tiene 4-8 bytes de sobrecarga por celda.

Si a menudo se repiten las cadenas, puede usar un grupo de cadenas para reducir la duplicación de cadenas. Los grupos de objetos para otros tipos inmutables pueden ser útiles para reducir la memoria consumida.

EDITAR: Puede estructurar sus datos como basados ​​en filas o en columnas.Si se basa en sus filas (una matriz de celdas por fila) agregar/eliminar la fila es solo cuestión de eliminar esta fila. Si está basado en columnas, puede tener una matriz por columna. Esto puede hacer que el manejo de tipos primitivos sea mucho más eficiente. es decir, puede tener una columna que sea int [] y otra que sea doble [], es mucho más común que una columna entera tenga el mismo tipo de datos, en lugar de tener el mismo tipo de datos para una fila completa.

Sin embargo, en cualquiera de los modos en que se estructuran los datos, se utilizará para la modificación de filas o columnas y la realización de un agregar/eliminar del otro tipo dará como resultado la reconstrucción de todo el conjunto de datos.

(Algo que hago es tener datos basados ​​en filas y agregar columnas al final, suponiendo que una fila no es lo suficientemente larga, la columna tiene un valor predeterminado, esto evita una reconstrucción al agregar una columna. columna, tengo un medio de ignorarlo)

Answer 8

He estado experimentando con el uso del SparseObjectMatrix2D del proyecto Colt. Mis datos son bastante densos, pero sus clases de Matrix realmente no ofrecen ninguna forma de ampliarlos, así que fui con un conjunto de matrices dispersas al tamaño máximo.

Parece que utiliza aproximadamente un 10% menos de memoria y carga aproximadamente un 15% más rápido para los mismos datos, además de ofrecer algunos métodos de manipulación inteligentes. Todavía interesado en otras opciones sin embargo.

Answer 9

¿Por qué no intentas usar la implementación de la memoria caché como EHCache. Esto resultó ser muy efectivo para mí, cuando llegué a la misma situación.
Puede simplemente almacenar su colección dentro de la implementación de EHcache. Hay configuraciones como:

Maximum bytes to be used from Local heap. 

Una vez que los bytes utilizados por los desbordamientos de aplicaciones que configuran en la memoria caché, a continuación, la aplicación de caché se encarga de escribir los datos en el disco. También puede configurar la cantidad de tiempo después de la cual los objetos se escriben en el disco usando el algoritmo Usado Menos Reciente. Puede estar seguro de evitar cualquier error de falta de memoria, utilizando este tipo de implementaciones de caché. Solo aumenta las operaciones de E/S de su aplicación en un pequeño grado.
Esto es solo una vista de pájaro de la configuración. Hay muchas configuraciones para optimizar sus requisitos.

Answer 10

Chronicle Map podría tener una sobrecarga de menos de 20 bytes por entrada (ver a test demostrando esto). Para la comparación, la sobrecarga de java.util.HashMap varía de 37-42 bytes con -XX:+UseCompressedOops a 58-69 bytes sin ups comprimidos (reference).

Además, Chronicle Map almacena las claves y los valores fuera del montón, por lo que no almacena los encabezados de objetos, que no se contabilizan como la sobrecarga de HashMap anterior. Chronicle Map integrates con Chronicle-Values, una biblioteca para la generación de implementaciones flyweight de interfaces, el patrón suggested by Brian Agnew en otra respuesta.