java - collections reverseorder()

¿Cuál es la biblioteca Java Collections más eficiente?

Question

¿Cuál es la biblioteca Java Collections más eficiente?

Hace unos años, hice una gran cantidad de Java y tuve la impresión en aquel entonces de que la mejor (más eficiente) implementación de colecciones Java. Pero cuando leí las respuestas a la pregunta "¿ Las librerías Java más útiles? " Noté que el trove apenas se menciona. Entonces, ¿qué biblioteca de colecciones Java es la mejor ahora?

ACTUALIZACIÓN: para aclarar, la mayoría quiero saber qué biblioteca usar cuando tengo que almacenar millones de entradas en una tabla hash, etc. (necesito un tiempo de ejecución pequeño y huella de memoria).

Answer 1

A partir de la inspección, parece que Trove es solo una biblioteca de colecciones para tipos primitivos; no es como si estuviera destinada a agregar una gran cantidad de funcionalidad sobre las colecciones normales en el JDK.

Personalmente (y soy parcial) me encanta Guava (incluido el antiguo proyecto Google Java Collections). Hace que varias tareas (incluidas las colecciones) sean mucho más sencillas, de una forma al menos razonablemente eficiente. Dado que las operaciones de cobro rara vez forman un cuello de botella en mi código (en mi experiencia) esto es "mejor" que una API de colecciones que puede ser más eficiente pero no hace que mi código sea legible.

Dado que la superposición entre Trove y la guayaba es prácticamente nula, tal vez podría aclarar qué es lo que realmente está buscando en una biblioteca de colecciones.

Answer 2

Algunas colecciones de colecciones a considerar:

• Colecciones de Java en java.util
• trove
• Biblioteca de Google Collections
• Colecciones de Apache Commons
• Lib a gran escala de Cliff Click
• Lib de collections Doug Lea: ya no es compatible y en su mayoría se reconstruyó en JDK

En primer lugar, buscaría la biblioteca de colecciones JDK. Cubre las cosas más comunes que debe hacer y obviamente ya está disponible para usted.

Google Collections es probablemente la mejor biblioteca de alta calidad fuera del JDK. Es muy utilizado y bien respaldado.

Apache Commons Collections es más viejo y sufre un poco del problema de "demasiados cocineros", pero también tiene muchas cosas útiles.

Trove tiene colecciones muy especializadas para casos como llaves / valores primitivos. En estos días, encontramos que en JDKs modernos y con las colecciones Java 5+ y casos de uso simultáneo, las colecciones JDK superan incluso a las colecciones especializadas de Trove.

Si tienes casos de uso de concurrencia realmente altos, definitivamente deberías revisar cosas como NonBlockingHashMap en la lib de alta escala, que es una implementación sin bloqueos y puede pisar ConcurrentHashMap si tienes el uso correcto para ello.

Answer 3

Como otros comentaristas han notado, la definición de "eficiente" arroja una amplia red. Sin embargo, nadie ha mencionado aún la biblioteca de Javolution .

Algunos de los aspectos más destacados:

• Las clases de Javolution son rápidas, muy rápidas (por ejemplo, inserción / eliminación de texto en O [Log (n)] en lugar de O [n] para StringBuffer / StringBuilder estándar).
• Todas las clases de Javolution son duras en tiempo real y tienen un comportamiento altamente determinista (en el rango de microsegundos). Además (a diferencia de la biblioteca estándar), Javolution es RTSJ seguro (sin memoria de choque o pérdida de memoria cuando se utiliza con la extensión Java Real-Time).
• Las clases de recopilación en tiempo real de Javolution (mapa, lista, tabla y conjunto) se pueden usar en lugar de la mayoría de las clases de recopilación estándar y proporcionan funcionalidad adicional.
• Las colecciones de Javolution proporcionan garantías de concurrencia para facilitar la implementación de algoritmos paralelos.

La distribución de Javolution incluye una suite de referencia para que pueda ver cómo se comparan con otras bibliotecas / las colecciones integradas.

Answer 4

Depende de cómo definamos "eficiente".

Cada estructura de datos tiene su propio comportamiento Big-Oh para lectura, escritura, iteración, huella de memoria, etc. Es probable que una lista vinculada en una biblioteca sea la misma que cualquier otra. Y un mapa hash será más rápido para leer O (1) que una lista enlazada O (n).

Pero cuando leí las respuestas a la pregunta "¿Las librerías de Java gratuitas más útiles?" Noté que ese tesoro apenas se menciona.

Esto no suena como "más eficiente". Suena como "el más popular" para mí.

Solo algunos comentarios: nunca he oído hablar de ellos, y no conozco a nadie que los haya usado. Las colecciones integradas en el JDK, Google o Apache Commons son bien conocidas por mí.

Answer 5

Para almacenar millones de String en un mapa, consulte http://code.google.com/p/flatmap

Answer 6

Sé que esta es una publicación antigua y hay un montón de respuestas aquí. Pero, las respuestas anteriores son superficiales y simplificadas en términos de sugerir una biblioteca. No hay una sola biblioteca que tenga un buen rendimiento en los diversos puntos de referencia presentados aquí. La única conclusión que obtengo es que si te preocupas por el rendimiento y la memoria, y específicamente por los tipos primitivos, vale la pena mirar las alternativas que no son jdk.

Aquí hay un análisis de sonido más, en términos de mecánica de referencia y las bibliotecas cubiertas. This es un hilo en la lista de desarrollo mahout.

Las bibliotecas cubiertas son

• HPPC
• Trove
• FastUtil
• Mahout (Colt)
• Colecciones de Java

Actualización de junio de 2015 : Desafortunadamente, los puntos de referencia originales ya no están disponibles y, además, están un poco desactualizados. Here hay unos puntos de referencia bastante recientes (enero de 2015) realizados por otra persona. No es tan completo ni tiene las herramientas exploratorias interactivas como el enlace original.

Answer 7

Si desea almacenar millones de registros en una tabla hash, es probable que se encuentre con problemas de memoria. Esto me sucedió cuando intenté crear un mapa con 2,3 millones de objetos String, por ejemplo. Fui con BerkeleyDB , que es muy maduro y funciona bien. Tienen una API de Java que envuelve la API de Colecciones, por lo que puedes crear mapas arbitrariamente grandes con muy poca huella de memoria. Sin embargo, el acceso será más lento (ya que está almacenado en el disco).

Pregunta de seguimiento : ¿existe una biblioteca decente (y eficiente) y bien mantenida para colecciones inmutables? Clojure tiene un excelente soporte para esto, y sería bueno tener algo similar para Java.

Answer 8

Soy desarrollador de happy-collections de happy-collections en source-forge

1. Colecciones basadas en eventos
2. No modificable
3. SortedList
4. Cache

Answer 9

Trove ofrece algunas ventajas.

• memoria más pequeña, no usa objetos Map.Entry
• puede usar estrategias hash en lugar de claves para mapas, esto ahorra memoria y significa que no necesita definir una nueva clave cada vez que desea almacenar en caché un objeto en un nuevo conjunto de sus atributos
• tiene tipos de colección primitivos
• Creo que tiene alguna forma de iterador interno

Dicho esto, se ha hecho mucho para mejorar las colecciones jdk desde que se escribió el trove.

Sin embargo, son las estrategias de hash las que me atraen ... Google lo ha descubierto y ha leído su descripción general.

Answer 10

ConcurrentHashMap , así como el paquete java.util.concurrent , deben mencionarse si planea usar HashMap en múltiples hilos. Se asume una huella de memoria pequeña, ya que esto es parte de Java estándar.

Answer 11

java.util

Perdón por la respuesta obvia, pero para la mayoría de los usos, las colecciones predeterminadas de Java son más que suficientes.

Answer 12

La pregunta es (ahora) sobre el almacenamiento de muchos datos, que se pueden representar utilizando tipos primitivos como int , en un Mapa. Algunas de las respuestas aquí son muy engañosas en mi opinión. Veamos por qué.

Modifiqué el benchmark de trove para medir tanto el tiempo de ejecución como el consumo de memoria. También agregué PCJ a este benchmark, que es otra biblioteca de colecciones para tipos primitivos (lo uso extensivamente). El benchmark "oficial" no compara IntIntMaps con Java Collection''s Map<Integer, Integer> , probablemente almacenar Integers y almacenar ints no es lo mismo desde un punto de vista técnico. Pero a un usuario puede no importarle este detalle técnico, quiere almacenar datos representables con datos de manera eficiente.

Primero, la parte relevante del código:

new Operation() {

     private long usedMem() {
        System.gc();
        return Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
     }

     // trove
     public void ours() {
        long mem = usedMem();
        TIntIntHashMap ours = new TIntIntHashMap(SET_SIZE);
        for ( int i = dataset.size(); i-- > 0; ) {
           ours.put(i, i);
        }
        mem = usedMem() - mem;
        System.err.println("trove " + mem + " bytes");
        ours.clear();
     }

     public void pcj() {
        long mem = usedMem();
        IntKeyIntMap map = new IntKeyIntOpenHashMap(SET_SIZE);
        for ( int i = dataset.size(); i-- > 0; ) {
           map.put(i, i);
        }
        mem = usedMem() - mem;
        System.err.println("pcj " + mem + " bytes");
        map.clear();
     }

     // java collections
     public void theirs() {
        long mem = usedMem();
        Map<Integer, Integer> map = new HashMap<Integer, Integer>(SET_SIZE);
        for ( int i = dataset.size(); i-- > 0; ) {
           map.put(i, i);
        }
        mem = usedMem() - mem;
        System.err.println("java " + mem + " bytes");
        map.clear();
     }

Supongo que los datos vienen como primitivos, lo que parece cuerdo. Pero esto implica una penalización de tiempo de ejecución para java util, debido al auto-boxing, que no es necesario para los frameworks de colecciones primitivos.

Los resultados de tiempo de ejecución (sin llamadas a gc() , por supuesto) en WinXP, jdk1.6.0_10:

100000 put operations 100000 contains operations java collections 1938 ms 203 ms trove 234 ms 125 ms pcj 516 ms 94 ms

Si bien esto puede parecer drástico, esta no es la razón para usar dicho marco.

La razón es el rendimiento de la memoria. Los resultados para un mapa que contiene 100000 entradas int :

java collections oscillates between 6644536 and 7168840 bytes trove 1853296 bytes pcj 1866112 bytes

Las colecciones de Java necesitan más de tres veces la memoria en comparación con los marcos de recopilación primitivos. Es decir, puede mantener tres veces más datos en la memoria, sin recurrir al disco IO, lo que reduce el rendimiento del tiempo de ejecución por magnitudes. Y esto importa. Lea la highscalability para descubrir por qué.

En mi experiencia, el alto consumo de memoria es el mayor problema de rendimiento con Java, lo que por supuesto también tiene un peor rendimiento en el tiempo de ejecución. Los marcos de colección primitivos realmente pueden ayudar aquí.

Entonces: No, java.util no es la respuesta. Y "agregar funcionalidad" a las colecciones de Java no es el punto cuando se pregunta sobre la eficiencia. Además, las colecciones modernas de JDK no "superan incluso a las colecciones especializadas de Trove".

Descargo de responsabilidad: El punto de referencia aquí está lejos de ser completo, ni es perfecto. Está destinado a llevar a casa el punto, que he experimentado en muchos proyectos. Las colecciones primitivas son lo suficientemente útiles como para tolerar la API sospechosa, si trabajas con muchos datos.