Ordenación de Listas en java

List tiene un nuevo método sort(Comparable). Resulta útil, porque permite a las implementaciones especificar cómo ordenar su estructura interna de datos. Vector sincroniza de una vez la lista, no por elemento. ArrayList evita copiar el array si no es necesario. CopyOnWriteArrayList funciona.

Este artículo es una traducción al castellano de la entrada original publicada, en inglés, por Dr. Heinz Kabutz en su número 239 del JavaSpecialists newsletter. Puedes consultar el texto original en Javaspecialists’ Newsletter #239: Sorting Lists

Este artículo se publica en Adictos al Trabajo, con permiso del autor, traducido por David Gómez García, (@dgomezg) consultor tecnológico en Autentia, colaborador de Javaspecialists e instructor certificado para impartir los cursos de Javaspecialists en Español.

Bienvenidos a la edición número 239 del Javatm Specialists’ Newsletter, enviada desde la bella isla de Creta. Estoy sentado en mi balcón bajo la luna llena, escuchando el sonido rural de nuestra oveja “Darling” al deambular moviendo su cencerro, sin duda en busca del último penacho verde de hierba. La oveja tiene un nombre, lo que significa que no nos la podemos comer, ni a ella ni ninguno de sus descendientes hasta la décima generación.

El viernes pasado tuvimos un “Festival de la sandía” en nuestro pueblo de Chorafakia. La idea es genial. Por 5 euros, te dan una botella de tsikoudia (aguardiente) para compartir entre 4, y toda la sandía que seas capaz de comer. Por supuesto, también puedes comprar otras bebidas y carnes a la parrilla. Música de Creta en vivo, bailarines y una jornada festiva y alegre. La idea es fantástica y, sin duda, volveré el año que viene. Incluso podría ser voluntario para ayudar con la parrilla. Al fin y al cabo, podría ser Chorafakiano ya, aunque nací y me crié en Sudáfrica.

Ordenación de Listas en Java

En versiones anteriores de Java, utilizamos normalmente Collections.sort(List) para ordenar una lista de objetos. Algunas listas implementan el interfaz RandomAccess, indicando que podemos acceder a cualquier elemento de la lista ubicado en cualquier posición en un tiempo constante. Un ejemplo de este tipo de listas es ArrayList. Por el contrario, LinkedList no lo es. Una búsqueda tiene una complejidad de tiempo de O(n). El método Collections.sort(List) no considera si la List implementa RandomAccess, sino que la convierte siempre a un Array, para después ordenarlo con Arrays.sort(Object[]) y volcar de nuevo en la lista con el método set() de ListIterator. La siguiente es la forma en que podríamos ordenar las listas que tenían complejidad en tiempo de O(n) para la búsqueda:

Internamente, el método Arrays.sort() también crea arrays temporales del mismo tamaño de los datos de entrada. Tenemos, por tanto, dos puntos en los que se crean arrays temporales: Collections.sort() y Arrays.sort(). Antes de Java 7, teníamos Merge Sort, que creaba un array del tamaño exacto del array de entrada. A partir de Java 7 tenemos Tim Sort, que crea algunos arrays temporales adicionales y que incrementa un poquito el total de objetos ‘basura’ creados.

En Java 8, el interfaz List contiene un nuevo método sort(Comparator). La implementación por defecto parece la misma que la del método Collections.sort(List, Comparator) de Java 7. Sin embargo, dado que se encuentra en el interfaz, ahora podemos tener especializaciones en las implementaciones de List. Esto significa que ArrayList no necesita ya copiar sus contenidos en un array, y puede ordenar directamente. CopyOnWriteArrayList puede ordenar sus contenidos sin lanzar la excepción UnsupportedOperationException en su método set(). La vida es bella.

En cualquier caso, cualquier sagaz ingeniero informático podría fácilmente caer en la cuenta de que la creación de objetos no es el cuello de botella del método sort(). Al revés, la fusión y la propia ordenación son las que se llevan la mayor parte del tiempo. Podemos comprobarlo mirando la tasa de creación de objetos. En mi máquina, puedo crear hasta 4 Gb por segundo. En este caso, estamos creando sólo unos 12 Mb por segundo. Comprobaremos la tasa de creación de objetos, sólo por curiosidad.

Me gustaría en este punto agradecer a nuestro suscriptor Michael Inden, autor de un buen libro, Java 8 – Die Neuerungen (en alemán). Yo ya sabía que List tenía un método sort() pero, gracias a su libro, aprendí las diferentes especializaciones de las implementaciones de List. Curioso.

Para comprobar la tasa de creación de objetos, he simplificado el ByteWatcher

A continuación, cogí una pequeña utilidad Memory que escribí para los ejercicios de mi Extreme Java – Advanced Topics Course (que también impartimos en español). Es similar a la enumeración TimeUnit en su estructura. Lo usamos para convertir la información de bytes asignados en números fáciles de leer:

Por último, la clase de prueba, de nombre ListSorting. Vamos a probar 5 implementaciones diferentes de List: ArrayList, LinkedList, Vector, CopyOnWriteArrayList y la lista devuelta por Arrays.asList(...). Cada una de las listas contiene objetos Double. Empezamos generando un stream de valores nativos double utilizando ThreadLocalRandom, los convertimos implícitamente a Double y los recogemos en la List. Así se crea la lista que ordenaremos.

El método test() toma por parámetro la forma de construir la lista (por ejemplo, ArrayList::new o LinkedList::new). Cada una de los tipos de listas tienen que tener un constructor que acepte una lista como parámetro. También proporcionaremos esa lista desordenada al método test(). De esta manera, nuestro método test() puede probar diferentes formas de ordenar las listas, antiguas y nuevas.

LinkedList utiliza el método por defecto de ordenación de Java 7, que ahora reside en el método sort() por defecto del interface List. La mayoría de las implementaciones de List, como ArrayList, Arrays.ArrayList, Vector y CopyOnWriteArrayList, han sobre-escrito el método con versiones más eficientes. Al ejecutar el código, verás que ArrayList reserva menos bytes que antes, pese a que no se ve una gran diferencia en el tiempo de CPU. También verás que CopyOnWriteArrayList ahora se puede ordenar, mientras que antes nos daba un UnsupportedOperationException.

Ordenando como un campeón en Java 8

En Java 8, tenemos un Arrays.parallelSort(), pero no hay un Collections.parallelSort() equivalente. Pero podemos lograr nuestro nirvana de la ordenación con parallel streams. En mi método parallelSort(), especificamos una lista y una Function que se utilizará para crear el tipo adecuado de List. R es el tipo del resultado, por ejemplo ArrayList<E> o LinkedList<E>. Tiene que ser un subtipo de List<E>. Así, podemos convertir la lista en un parallel stream, ordenarla, y recoger sus valores en una lista. El resultado es un ArrayList, wue luego convertimos con la función listConstructor.

Aqui tenemos un ejemplo donde generamos tres tipos distintos de listas utilizando nuestro método parallelSort():

Hay un pero: La implementación actual en Java 8 de la ordenación en paralelo sólo funciona si hay al menos un hilo disponible en el common fork join pool. No pasará por defecto a utilizar el hilo que invoca la ordenación, como pasaría con otras parallel tasks. Creo que esto es un bug, no una feature ;). La he enviado, pero no creo que sea resuelta pronto. No es grave porque, en cualquier caso, se supone que no deberíamos bloquear todos los hilos del common pool.

Gracias por leer mi artículo. Espero que lo hayas disfrutado tanto como yo al escribirlo 🙂

Saludos

Heinz.