objeto - tipos primitivos java

Mapa alternativo para valores primitivos.

Question

Realicé algunos perfiles en mi aplicación y uno de los resultados resultó que aproximadamente el 18% de la memoria en el montón es utilizado por objetos de tipo Double . Resulta que estos objetos son los valores en Map s, donde no puedo usar el tipo primitivo.

Mi razonamiento es que el tipo primitivo de double consume menos memoria que su Double objeto. ¿Hay una manera de tener un mapa como estructura de datos, que acepte cualquier tipo como clave y un double primitivo como valores?

Las principales operaciones serían:

• inserción (probablemente solo una vez)
• Búsqueda (contiene por clave)
• Recuperación (por clave)
• Iteración

Los mapas típicos que tengo son:

• HashMap<T, HashMap<NodeData<T>, Double>> graph
• HashMap<Point2D, Boolean> onSea (aunque no es un valor doble)
• ConcurrentHashMap<Point2D, HashMap<Point2D, Double>>

Todos utilizados con Java 8.

Apéndice

Principalmente no me interesan los marcos que tienen una solución para este tipo de mapas, sino lo que se debe tener en cuenta al abordar estos problemas. Si lo desea, ¿cuáles son los conceptos / ideas / enfoques detrás de dicho marco? O la solución también puede estar en otro nivel, donde los mapas se reemplazan con objetos que siguen un patrón determinado, como lo señaló @Ilmari Karonen en su respuesta.

Answer 1

Hay varias implementaciones:

• http://labs.carrotsearch.com/hppc.html
• http://trove.starlight-systems.com/

Aquí hay preguntas relacionadas con el mejor desempeño:

• La biblioteca de colecciones primitivas de Java más eficiente.
• ¿Cuál es una alternativa rápida a HashMap para mapear a tipos primitivos?

La implementación real también puede influir en el rendimiento

• Diferencia entre HashMap, LinkedHashMap y TreeMap

Answer 2

Lo que está buscando es un Object2DoubleOpenHashMap de fastutil (Collections Framework con una pequeña huella de memoria y rápido acceso e inserción) que proporciona métodos de tipo double getDouble(Object k) y double put(K k, double v) .

Por ejemplo:

// Create a Object2DoubleOpenHashMap instance
Object2DoubleMap<String> map = new Object2DoubleOpenHashMap<>();
// Put a new entry
map.put("foo", 12.50d);
// Access to the entry
double value = map.getDouble("foo");

La clase Object2DoubleOpenHashMap es una implementación real de un Map que no es seguro para subprocesos, sin embargo, todavía puede usar el método de utilidad Object2DoubleMaps.synchronize(Object2DoubleMap<K> m) para hacerlo seguro para los hilos gracias a un decorador.

El código de creación sería entonces:

// Create a thread safe Object2DoubleMap
Object2DoubleMap<String> map =  Object2DoubleMaps.synchronize(
    new Object2DoubleOpenHashMap<>()
);

Answer 3

Otros ya han sugerido varias implementaciones de terceros de mapas de valor primitivo. Para completar, me gustaría mencionar algunas formas de deshacerse de los mapas por completo que es posible que desee considerar. Estas soluciones no siempre serán posibles, pero cuando lo sean, por lo general serán más rápidas y más eficientes en memoria que cualquier mapa.

Alternativa 1: utilizar matrices antiguas.

Una simple matriz double[] puede no ser tan atractiva como un mapa elegante, pero muy poco puede vencerlo en compacidad y velocidad de acceso.

Por supuesto, las matrices vienen con un montón de limitaciones: su tamaño es fijo (aunque siempre se puede crear una nueva matriz y copiar el contenido del antiguo) y sus claves solo pueden ser enteros positivos pequeños que, por razones de eficiencia, deberían ser razonables. denso (es decir, el número total de claves utilizadas debe ser una fracción razonablemente grande del valor de clave más alto). Pero si ese es el caso de sus claves, o si puede hacer que sea el caso, las matrices de valores primitivos pueden ser muy eficientes.

En particular, si puede asignar un ID de entero pequeño único a cada objeto clave, entonces puede usar ese ID como un índice en una matriz. De manera similar, si ya está almacenando sus objetos en una matriz (por ejemplo, como parte de una estructura de datos más compleja) y los busca por índice, simplemente puede usar el mismo índice para buscar valores de metadatos adicionales en otra matriz.

Incluso podría prescindir del requisito de identidad de ID, si implementó algún tipo de mecanismo de manejo de colisiones, pero en ese punto estará en el buen camino para implementar su propia tabla hash. En algunos casos, eso podría tener sentido, pero generalmente en ese momento es probablemente más fácil usar una implementación de terceros existente.

Alternativa 2: Personaliza tus objetos.

En lugar de mantener un mapa de objetos clave en valores primitivos, ¿por qué no convertir esos valores en propiedades de los propios objetos? Después de todo, esto es de lo que se trata la programación orientada a objetos: agrupar datos relacionados en objetos significativos.

Por ejemplo, en lugar de mantener un HashMap<Point2D, Boolean> onSea , ¿por qué no simplemente le da a sus puntos una propiedad booleana onSea ? Por supuesto, tendrá que definir su propia clase de puntos personalizados para esto, pero no hay razón por la que no pueda extender la clase estándar de Point2D si así lo desea, de modo que pueda pasar sus puntos personalizados a cualquier método que espere un Point2D .

De nuevo, es posible que este enfoque no siempre funcione directamente, por ejemplo, si necesita trabajar con clases que no puede modificar (pero consulte a continuación), o si los valores que desea almacenar están asociados con más de un objeto (como en su ConcurrentHashMap<Point2D, HashMap<Point2D, Double>> ).

Sin embargo, para este último caso, aún puede resolver el problema rediseñando adecuadamente su representación de datos. Por ejemplo, en lugar de representar un gráfico ponderado como un Map<Node, Map<Node, Double>> , puede definir una clase Edge como:

class Edge {
    Node a, b;
    double weight;
}

y luego agregue una propiedad Edge[] (o Vector<Edge> ) a cada nodo que contenga cualquier borde conectado a ese nodo.

Alternativa 3: Combina múltiples mapas en uno.

Si tiene varios mapas con las mismas claves y no puede simplemente convertir los valores en nuevas propiedades de los objetos clave como se sugirió anteriormente, considere agruparlos en una sola clase de metadatos y crear un solo mapa desde las claves a los objetos de esa clase. Por ejemplo, en lugar de un Map<Item, Double> accessFrequency y un Map<Item, Long> creationTime , considere la posibilidad de definir una sola clase de metadatos como:

class ItemMetadata {
    double accessFrequency;
    long creationTime;
}

y tener un solo Map<Item, ItemMetadata> para almacenar todos los valores de metadatos. Esto es más eficiente en memoria que tener múltiples mapas, y también puede ahorrar tiempo al evitar búsquedas de mapas redundantes.

En algunos casos, por conveniencia, es posible que también desee incluir en cada objeto de metadatos una referencia a su objeto principal correspondiente, de modo que pueda acceder a ambos a través de una sola referencia al objeto de metadatos. Lo que naturalmente sigue en ...

Alternativa 4: Usa un decorador.

Como una combinación de las dos alternativas anteriores, si no puede agregar directamente propiedades de metadatos adicionales a los objetos clave, considere en su lugar envolverlos con decorators que puedan contener los valores adicionales. Así, por ejemplo, en lugar de crear directamente su propia clase de puntos con propiedades adicionales, simplemente podría hacer algo como:

class PointWrapper {
    Point2D point;
    boolean onSea;
    // ...
}

Si lo desea, puede incluso convertir esta envoltura en un decorador completo implementando el reenvío de métodos, pero incluso una simple envoltura "tonta" puede ser suficiente para muchos propósitos.

Este enfoque es más útil si luego puede organizar almacenar y trabajar solo con los envoltorios, para que nunca tenga que buscar el envoltorio correspondiente a un objeto sin envolver. Por supuesto, si necesita hacerlo ocasionalmente (por ejemplo, porque solo está recibiendo los objetos sin envolver de otro código), puede hacerlo con un solo Map<Point2D, PointWrapper> , pero luego está de vuelta en La alternativa anterior.

Answer 4

Para tener una mejor estimación de cómo estas diversas bibliotecas se comparan unas con otras, armé un pequeño punto de referencia que verifica el rendimiento de:

• Tiempo total para 300''000 inserciones.
• tiempo promedio para una verificación de contenciones con 1000 muestras que están en el mapa
• Tamaño de la memoria de la estructura de datos Observé la estructura similar a un Map que toma una String como clave y el double como valor. Los marcos revisados ​​son Eclipse Collection , HPPC , Trove y fastutil , así como para la comparación de HashMap y ConcurrentHashMap .

En resumen, estos son los resultados:

Filling in 300000 into the JDK HashMap took 107ms
Filling in 300000 into the JDK ConcurrentHashMap took 152ms
Filling in 300000 into the Eclipse map took 107ms
Filling in 300000 into the Trove map took 855ms
Filling in 300000 into the HPPC map took 93ms
Filling in 300000 into the FastUtil map took 163ms
1000 lookups average in JDK HashMap took: 550ns
1000 lookups average in JDK Concurrent HashMap took: 748ns
1000 lookups average in Eclipse Map took: 894ns
1000 lookups average in Trove Map took: 1033ns
1000 lookups average in HPPC Map took: 523ns
1000 lookups average in FastUtil Map took: 680ns
JDK HashMap:            43''809''895B
JDK Concurrent HashMap: 43''653''740B => save  0.36%
Eclipse Map:            35''755''084B => save 18.39%
Trove Map:              32''147''798B => save 26.62%
HPPC Map:               27''366''533B => save 37.53%
FastUtil Map:           31''560''889B => save 27.96%

Para todos los detalles, así como la aplicación de prueba, eche un vistazo a la entrada de mi blog .

Answer 5

Eclipse Collections tiene mapas de object y primitivos y tiene versiones mutables e inmutables para ambos.

MutableObjectDoubleMap<String> doubleMap = ObjectDoubleMaps.mutable.empty();
doubleMap.put("1", 1.0d);
doubleMap.put("2", 2.0d);

MutableObjectBooleanMap<String> booleanMap = ObjectBooleanMaps.mutable.empty();
booleanMap.put("ok", true);

ImmutableObjectDoubleMap<String> immutableMap = doubleMap.toImmutable();
Assert.assertEquals(doubleMap, immutableMap);

Un MutableMap se puede utilizar como una fábrica para un ImmutableMap en colecciones de Eclipse llamando a toImmutable como lo he hecho en el ejemplo anterior. Tanto los mapas mutables como los inmutables comparten una interfaz padre común, que en el caso de MutableObjectDoubleMap y MutableObjectDoubleMap arriba, se denomina ObjectDoubleMap .

Eclipse Collections también tiene versiones sincronizadas y no modificables para todos los contenedores mutables en la biblioteca. El siguiente código le dará una vista sincronizada envuelta alrededor de los mapas primitivos.

MutableObjectDoubleMap<String> doubleMap = 
        ObjectDoubleMaps.mutable.<String>empty().asSynchronized();
doubleMap.put("1", 1.0d);
doubleMap.put("2", 2.0d);

MutableObjectBooleanMap<String> booleanMap = 
        ObjectBooleanMaps.mutable.<String>empty().asSynchronized();
booleanMap.put("ok", true);

Esta comparación de rendimiento de mapas grandes se publicó hace un par de años.

Descripción general de HashMap grande: JDK, FastUtil, Goldman Sachs, HPPC, Koloboke, Trove - versión enero de 2015

Desde entonces, GS Collections se ha migrado a Eclipse Foundation y ahora es Eclipse Collections.

Nota: Soy un comendador de Eclipse Collections.