java - simplificar - producto de sumas karnaugh
¿Qué implementación de Mapa<K, V> debo usar si mi mapa necesita ser más pequeño que rápido? (9)
Habitualmente utilizo HashMap en mis programas, ya que sé que generalmente es el más eficiente (si se usa correctamente) y puede hacer frente a mapas grandes fácilmente. Sé de EnumMap que es muy útil para las claves de enumeración, pero a menudo estoy generando un pequeño mapa que nunca será muy grande, es probable que se descarte muy pronto y no tenga problemas de concurrencia.
¿Es HashMap<K,V> demasiado complicado para estos usos pequeños, locales y temporales? ¿Hay otra implementación simple que pueda usar en estos casos?
Creo que estoy buscando una implementación de Map que sea análoga a ArrayList for List . ¿Existe?
Añadido más tarde después de las respuestas:
Aquí hay un escenario donde una implementación lenta pero muy simple podría ser mejor, cuando tengo muchos, muchos de estos Map . Supongamos, por ejemplo, que tengo un millón de estos pequeños mapas, cada uno con un puñado (a menudo menos de tres) de entradas. Tengo una tasa de referencia baja, tal vez no haga referencia a ellos antes de que sean descartados la mayor parte del tiempo. ¿Sigue siendo el caso de que HashMap es la mejor opción para ellos?
La utilización de recursos es más que solo velocidad: me gustaría algo que no fragmente mucho el montón y haga que los GC tomen mucho tiempo, por ejemplo.
Puede ser que HashMap sea la respuesta correcta, pero este no es un caso de optimización prematura (o al menos no lo es).
Añadido mucho más tarde después de un pensamiento:
Decidí codificar a mano mi propio SmallMap . Es fácil hacer uno con AbstractMap . También he agregado un par de constructores para poder construir un SmallMap partir de un Map existente.
En el camino, tuve que decidir cómo representar las SmallSet e implementar SmallSet para el método entrySet .
Aprendí mucho codificando (y probando esto por unidades) y quiero compartir esto, en caso de que alguien más quiera uno. Está en github here .
Android tiene un ArrayMap con la intención de minimizar la memoria. Además de estar en el núcleo, está en la biblioteca de soporte de v4, que, en teoría, debería poder compilar también para los JRE de Oracle o OpenJDK. Aquí hay un enlace a la fuente de ArrayMap en un enlace de la biblioteca de soporte v4 en github .
Creo que esta es una optimización prematura. ¿Tienes problemas de memoria? ¿Problemas de rendimiento por crear demasiados mapas? Si no, creo que HashMap está bien.
Además, mirando la API, no veo nada más simple que un HashMap .
Si tiene problemas, puede rodar su propia implementación de Map, que tiene elementos internos muy simples. Pero dudo que lo hagas mejor que las implementaciones de Map por defecto, además tienes la sobrecarga de asegurarte de que tu nueva clase funcione. En este caso puede haber un problema con su diseño.
Estoy de acuerdo con @hvgotcodes en que es una optimización prematura, pero aún es bueno saber todas las herramientas en la caja de herramientas.
Si haces muchas iteraciones sobre lo que hay en un mapa, un LinkedHashMap suele ser mucho más rápido que un HashMap, si tienes muchos hilos trabajando con el mapa al mismo tiempo, un ConcurrentHashMap es a menudo una mejor opción. No me preocuparía que cualquier implementación de mapas fuera ineficiente para pequeños conjuntos de datos. Normalmente es al revés, un mapa construido incorrectamente fácilmente se vuelve ineficiente con grandes cantidades de datos si tiene valores de hash incorrectos o si algo hace que tenga muy pocos depósitos para su carga.
Luego, por supuesto, hay casos en que un HashMap no tiene ningún sentido, como si tuviera tres valores que siempre indexará con las teclas 0, 1 y 2, pero supongo que entiende que :-)
Existe una alternativa llamada AirConcurrentMap que es más eficiente en memoria por encima de las entradas de 1K que cualquier otro mapa que haya encontrado, y es más rápida que ConcurrentSkipListMap para operaciones basadas en claves y más rápida que cualquier mapa para iteraciones, y tiene un conjunto de subprocesos internos para exploraciones paralelas. Es una ordenada, es decir, NavigableMap y una ConcurrentMap. Es gratuito para uso no comercial sin fuente y con licencia comercial con o sin fuente. Ver boilerbay.com para los gráficos. Revelación completa: soy el autor.
AirConcurrentMap cumple con los estándares por lo que es compatible con enchufes en todas partes, incluso para un mapa regular.
Los iteradores ya son muy rápidos, especialmente en las entradas de 1K. Las exploraciones de mayor velocidad utilizan un modelo de "visitante" con una sola visita (k, v) de devolución de llamada que alcanza la velocidad de las secuencias paralelas de Java 8. El escaneo paralelo de AirConcurrentMap excede las secuencias paralelas de Java 8 en aproximadamente 4x. El visitante con hilos agrega los métodos split () y merge () al visitante de un solo hilo que recuerdan a map / reduce:
static class ThreadedSummingVisitor<K> extends ThreadedMapVisitor<K, Long> {
private long sum;
// This is idiomatic
long getSum(VisitableMap<K, Long> map) {
sum = 0;
map.getVisitable().visit(this);
return sum;
}
@Override
public void visit(Object k, Long v) {
sum += ((Long)v).longValue();
}
@Override
public ThreadedMapVisitor<K, Long> split() {
return new ThreadedSummingVisitor<K>();
}
@Override
public void merge(ThreadedMapVisitor<K, Long> visitor) {
sum += ((ThreadedSummingVisitor<K>)visitor).sum;
}
}
...
// The threaded summer can be re-used in one line now.
long sum = new ThreadedSummingVisitor().getSum((VisitableMap)map);
HashMap es una buena opción porque ofrece el promedio de O(1) pone y obtiene. No garantiza el orden, aunque como implementaciones de SortedMap (es decir, TreeMap O(log n) pone y obtiene), pero si no tiene ningún requisito para ordenar, HashMap es mejor.
HashMap usa más o menos memoria (cuando se crea) dependiendo de cómo lo inicialice: más cubos significan más uso de memoria, pero acceso más rápido para grandes cantidades de artículos ; si solo necesita un pequeño número de elementos, puede inicializarlo con un valor pequeño, lo que producirá menos depósitos que serán aún más rápidos (ya que cada uno recibirá algunos elementos). No hay pérdida de memoria si la configura correctamente (la compensación es básicamente el uso de memoria frente a la velocidad).
En cuanto a la fragmentación del montón y la pérdida del ciclo de GC y otras cosas, no hay mucho que una implementación de Mapa pueda hacer al respecto; todo vuelve a la forma en que lo pones. Comprenda que esto no tiene que ver con la implementación de Java, sino el hecho de que las EnumMap hash (no las HashTable s) genéricas (como en, por ejemplo, no puede asumir nada acerca de los valores clave como EnumMap hace HashTable ) son las mejores implementaciones posibles de una estructura de mapa.
No hay una pequeña implementación estándar de Map en Java. HashMap es una de las mejores y más flexibles implementaciones de Map , y es difícil de superar. Sin embargo, en el área de requisitos muy pequeños, donde el uso de la pila y la velocidad de construcción es primordial, es posible hacerlo mejor.
He implementado here en GitHub para demostrar cómo se puede hacer esto. Me encantaría algunos comentarios sobre si he tenido éxito. No es de ninguna manera lo que tengo.
Aunque las respuestas ofrecidas aquí a veces eran útiles, tendían, en general, a malinterpretar el punto. En cualquier caso, responder a mi propia pregunta fue, al final, mucho más útil para mí que recibir una.
La pregunta aquí ha cumplido su propósito, y es por eso que la "contesté yo misma".
También me interesó y solo para un experimento creé un mapa que almacena claves y valores solo en campos y permite hasta 5 entradas. Consume 4 menos memoria y funciona 16 veces más rápido que HashMap https://github.com/stokito/jsmallmap
Un HashMap es posiblemente la colección más ligera y simple.
A veces la solución más eficiente es usar un POJO. por ejemplo, si sus claves son nombres de campo y / o sus valores son primitivos.