jueves
ene102013
Librerías de Collections alternativas al API estándar
Abraham
En muchas ocasiones cuando necesitamos una estructura de datos para construir nuestro programa encontraremos alguna adecuada dentro del API de Collections estándar de Java. Sin embargo, hay ocasiones en las cuales dentro de la librería estándar no encontramos la estructura ideal. Este artículo hace una revisión de una serie de librerías de colecciones alternativas. Las librerías discutidas en el artículo son:
- Collections API, la librería estándar de Java
- Google Guava, que contiene cosas interesantes como estructuras de datos completamente thread-safe, Multi-mapas (que pueden emplearse para construir grafos), etc.
- Apache Commons Collections, que contiene una estructura tipo "bolsa" (Bag) que admite duplicados, además de varias estructuras tipo FIFO/LIFO.
- Trove, es ideal si lo que vas a almacenar en tus estructuras son sólo números porque incrementará su rendimiento.
- Huge Collections, como su nombre indica, contiene estructuras pensadas para trabajar con grandes volúmenes de datos. Para ello, se las apañan para almacenar estos datos fuera del heap Java, de tal modo que no haya paradas en la aplicación por culpa de que el recogedor de basura tiene que trabajar sobre un heap inmenso.
- Highly Scalable Java: interesante para entornos donde se emplea mucho locking
- fastutil: pensada para colecciones enormes de hasta 2^31 elementos.
¿Cuantos de vosotros habéis empleado alguna librería de Collections distinta de la estándar de Java? ¿Cuál fue? ¿Qué tal vuestra experiencia con ella?
Reader Comments (18)
Cuando yo empecé con Java éste no tenía collections (eso fue una novedad de Java 2), y usaba JGL de ObjectSpace. JGL estaba mucho mejor diseñada que las collections de Java, entre otras cosas una llamada a un método que devolvía un resultado no modificaba el estado del objeto, lo que sí que ocurre con Iterator por ejemplo.
ObjectSpace también creo un servidor de aplicaciones (Voyager) que permitía tener objeto remotos de una manera transparente, no como el RMI o CORBA de la época que te obligaban a escribir código especial para los objetos remotos.
En fin, a veces las cosas sencillas y elegantes pasan desapercibidas mientras que las mediocres triunfan.
He usado Trove, hace algunos años, y funcionaba muy bien. Sin embargo, a menos que se necesiten colecciones muy grandes de primitivas, no veo justificación para usarla.
@javierpaniza
No comprendo esa afirmación de que los Iterator modifican el estado del objeto. Los Iterator en Java no lo modifican. La razón de que no sean thread-safe es otra, si es en eso en lo que estabas pensando.
Gracias por el post...aprovecho para comentar que seria muy util crear dentro de la web una lista de librerias externas para Java...esto pidiendo que cada cual nombre las que conoce (para no recargar el trabajo sobre uno solo)...hay cientos de librerias ocultas en la red que extienden el lenguaje y facilitan muchas tareas...Gracias!!!
Anon ¿alguna propuesta sobre exactamente cómo crear ese listado de librerías? ¿usando un wiki o similar?
Hola Choces,
Un iterador es un objeto. Con un iterador puedes escribir:
Iterator it = ... ;
System.out.println(it.next()); // Imprime un valor
System.out.println(it.next()); // Imprime otro valor diferente: MAL HECHO
Por supuesto esto se basa en una premisa que a lo mejor no es cierta: "Si Eiffel es el lenguaje perfecto Java está mal diseñado." JGL seguía los principio que Meyer postulaba, eso me parecio al menos curioso y por eso mismo mi primera impresión de Collection cuando salió Java 2 no fue buena. Pero en fin, al menos es suficiente y bueno, nadie ha muerto porque it.next() devuelva cada vez un valor diferente.
La idea de listado de librerías y descripción de utilidades, enlace de descarga, año de fundación, estado... etc, es una idea GENIAL CHAVALES. ¿Podemos organizar un grupo de investigación orientado a ello?
@javierpaniza
Hay una diferencia entre "cambiar el estado de un objeto" y "devolver un valor diferente".
Con toda lógica, si se busca recorrer una colección para obtener los valores almacenados, el método que devuelve cada uno de los valores dará un resultado diferente en cada invocación. Sin embargo, ello no altera en nada el estado de ningún objeto: no hay cambios de valor debidos a la ejecución del método, ni en el iterador ni en la colección. Lo único que cambia es el valor de la variable a la que se asigna el resultado del método.
@choces Siendo purista, que creo que por ahí va Javier, en realidad si se cambia el estado ya que el objeto tiene, como parte del estado, un apuntador a cual es el objeto siguiente, y al llamar a next() y devolverlo, se cambia ese apuntador. Así que sí que modifica el estado. Y esa "chorrada" purista hace que un Iterator no se pueda compartir de forma simple entre varios Threads, por ejemplo, ya que el objeto muta al recorrerlo.
Por poner un equivalente, un array no modifica su estado cuando lo recorres, ya que el apuntador es externo y no forma parte del objeto en sí.
Obviamente, se hace para facilitar el recorrido sin tener que aportar y mantener el apuntador externo, como en el caso del array, y presupone, con bastante razón, que se usará desde un único Thread.... si eso es bueno o malo, es otro tema :D.
@Guatdefu
La razón por la que los iteradores no son thread-safe no es porque el objeto mute al recorrerlo, debido al propio iterador, puesto que no lo hace.
Las colecciones en Java usan todas un array interno para almacenar los datos, y ese array es una propiedad mutable dentro de cada colección. De otro modo no se podrían añadir, modificar o eliminar sus elementos.
La cuestión es que, siendo la propiedad mutable, el recorrido por sus elementos que hace un iterador puede ser inconsistente en multitarea: el iterador no puede asegurar que el hasNext o next existan siquiera cuando accede a ellos. De ahí la conocida ConcurrentModificationException que se puede producir cuando se ejecuta un iterador sin sincronización.
Los métodos hasNext y next de Iterator simplemente comprueban si el siguiente elemento existe, y devuelve su valor, respectivamente, respecto del array interno. Ni la declaración del array cambia, ni sus elementos, debido a la actividad del Iterator. No puedo aceptar que eso sea "un cambio de estado" provocado por el Iterator, por muy purista que uno se ponga.
Un iterador es una clase Inner, ¿no? Es decir, una clase interna a otra clase Java (en este caso una lista con elementos). ¿Alguien puede confirmar esto? Por lo que entonces, tenemos un debate interesante por delante.
Sí. Por ejemplo, así es como se implementa en ArrayList:
public Iterator<E> iterator() {
return new Itr();
}
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
choces, a lo que se refiere javier con cambio de estado es, ya que has puesto el código, a que el valor de la propiedad "cursor" y "lastRep" se modifican en cada llamada a next o remove. Un cambio en la propiedades de un objeto, el iterator en este caso, es un cambio de estado. Y precisamente este cambio de estado es el culpable de que esta clase no sea thread-safe.
Si esto es bueno o malo ya es otra discusión, en mi opinión acceder a una colección o cualquier otra estructura de datos en general, desde varios threads es peliagudo y tienes que hacerlo con mucho ojo. Precisamente debido a esto ahora están tan auge los lenguajes funcionales, sin estado es mucho más facil construir software multi-thread sin meter mucho la pata.
Dicho esto, el diseño del API java de collections es viejuno y tiene cosas que vistas ahora son bastante feas, con por ejemplo el método Collection.sort, estatico y recibe un List!, feo, feo.
Otra "alternativa" a las colecciones de java también las podemos encontrar en lenguajes como groovy o clojure, que recubren las colecciones de java con al menos algo de "sintactic sugar". En groovy por ejemplo tienes unos cuantos métodos que valiendose de las closures que groovy si tiene simplifican enormemente el trabajo con colecciones.
El iterador no es thread-safe porque puede cambiar la propiedad ArrayList.this.elementData mientras se ejecuta el iterador. Esa es una propiedad mutable de ArrayList, a la que se accede mediante los métodos de la propia ArrayList.
Se ve con claridad cuándo y por qué se lanzan las excepciones desde el iterador.
Es inevitable que las propiedades internas del iterador cambien, cuando se ejecuta sobre una propiedad mutable externa.
¿Alguien puede construir un iterador thread-safe cuando la propiedad a iterar es un array mutable?.
Iteración thread-safe:
List<String> lista = new ArrayList<>(4);
lista.add("a");
lista.add("b");
List<String> inmutable = Collections.unmodifiableList(lista);
for (Iterator<String> it = inmutable.iterator(); it.hasNext();) {
String item = it.next();
System.out.println("elemento: " + item);
}
Bueno...no quise responder en este post por no desviar el tema que se estaba tratando....sobre la idea de la base de datos de librerias, me imagino una pagina que tenga al lado izquierdo una lista (ordenada alfabeticamente) con los temas que abarcan un conjunto de librerias...por ejemplo
L
+ Localizacion # al dar click, deberan salir informacion de librerias para google maps
M
+ Matematicas # librerias para hacer calculos matematicos
P
+ pdf # librerias para el manejo de pdfs
si alguien tiene otra idea seria genial...la mia es muy simple...
Cuando se este recolectando informacion sobre librerias...por aqui estare de primero aportando!!!
Gracias por la atencion!!!
@choces, gracias por los aportes
@Anon, es buena idea.... lo tengo en mente
Me he "enredado" (¡Qué raro!) con el asunto de los iteradores, y he pasado por alto (aunque lo tenía presente de reojo) el asunto de la relación de librerías.
Me parece, más que una estupenda idea, una necesidad imperativa.
Podéis contar con mi completa colaboración en este tema.
ok, a ver si sacamos tiempo. Operación rescate de código