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.
[/box]
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:
|
1 2 3 4 5 6 7 8 9 |
public static void sort(List list) { Object[] a = list.toArray(); Arrays.sort(a); ListIterator i = list.listIterator(); for (int j=0; j<a.length; j++) { i.next(); i.set(a[j]); } } |
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
import javax.management.*; import java.lang.management.*; /** * Reduced version of the ByteWatcher, described here: * http://www.javaspecialists.eu/archive/Issue232.html */ public class ByteWatcher { private static final String GET_THREAD_ALLOCATED_BYTES = "getThreadAllocatedBytes"; private static final String[] SIGNATURE = new String[]{long.class.getName()}; private static final MBeanServer mBeanServer; private static final ObjectName name; private final Object[] PARAMS; private final long MEASURING_COST_IN_BYTES; // usually 336 private final long tid; private long allocated = 0; static { try { name = new ObjectName( ManagementFactory.THREAD_MXBEAN_NAME); mBeanServer = ManagementFactory.getPlatformMBeanServer(); } catch (MalformedObjectNameException e) { throw new ExceptionInInitializerError(e); } } public ByteWatcher() { this.tid = Thread.currentThread().getId(); PARAMS = new Object[]{tid}; long calibrate = threadAllocatedBytes(); // calibrate for (int repeats = 0; repeats < 10; repeats++) { for (int i = 0; i < 10_000; i++) { // run a few loops to allow for startup anomalies calibrate = threadAllocatedBytes(); } try { Thread.sleep(50); } catch (InterruptedException e) { Thread.currentThread().interrupt(); break; } } MEASURING_COST_IN_BYTES = threadAllocatedBytes() - calibrate; reset(); } public void reset() { allocated = threadAllocatedBytes(); } private long threadAllocatedBytes() { try { return (long) mBeanServer.invoke( name, GET_THREAD_ALLOCATED_BYTES, PARAMS, SIGNATURE ); } catch (Exception e) { throw new IllegalStateException(e); } } /** * Calculates the number of bytes allocated since the last * reset(). */ public long calculateAllocations() { long mark1 = ((threadAllocatedBytes() - MEASURING_COST_IN_BYTES) - allocated); return mark1; } } |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 |
public enum Memory { BYTES { public double toBytes(double d) { return d; } public double toKiloBytes(double d) { return toBytes(d) / 1024; } public double toMegaBytes(double d) { return toKiloBytes(d) / 1024; } public double toGigaBytes(double d) { return toMegaBytes(d) / 1024; } public double toTeraBytes(double d) { return toGigaBytes(d) / 1024; } }, KILOBYTES { public double toBytes(double d) { return toKiloBytes(d) * 1024; } public double toKiloBytes(double d) { return d; } public double toMegaBytes(double d) { return toKiloBytes(d) / 1024; } public double toGigaBytes(double d) { return toMegaBytes(d) / 1024; } public double toTeraBytes(double d) { return toGigaBytes(d) / 1024; } }, MEGABYTES { public double toBytes(double d) { return toKiloBytes(d) * 1024; } public double toKiloBytes(double d) { return toMegaBytes(d) * 1024; } public double toMegaBytes(double d) { return d; } public double toGigaBytes(double d) { return toMegaBytes(d) / 1024; } public double toTeraBytes(double d) { return toGigaBytes(d) / 1024; } }, GIGABYTES { public double toBytes(double d) { return toKiloBytes(d) * 1024; } public double toKiloBytes(double d) { return toMegaBytes(d) * 1024; } public double toMegaBytes(double d) { return toGigaBytes(d) * 1024; } public double toGigaBytes(double d) { return d; } public double toTeraBytes(double d) { return toGigaBytes(d) / 1024; } }, TERABYTES { public double toBytes(double d) { return toKiloBytes(d) * 1024; } public double toKiloBytes(double d) { return toMegaBytes(d) * 1024; } public double toMegaBytes(double d) { return toGigaBytes(d) * 1024; } public double toGigaBytes(double d) { return toTeraBytes(d) * 1024; } public double toTeraBytes(double d) { return d; } }; public abstract double toBytes(double d); public abstract double toKiloBytes(double d); public abstract double toMegaBytes(double d); public abstract double toGigaBytes(double d); public abstract double toTeraBytes(double d); public static String format(double d, Memory unit, int decimals) { String unitStr; double val; double bytes = unit.toBytes(d); if (bytes < 1024) { val = bytes; unitStr = "B"; } else if (bytes < 1024 * 1024) { val = BYTES.toKiloBytes(bytes); unitStr = "KB"; } else if (bytes < 1024 * 1024 * 1024) { val = BYTES.toMegaBytes(bytes); unitStr = "MB"; } else if (bytes < 1024 * 1024 * 1024 * 1024L) { val = BYTES.toGigaBytes(bytes); unitStr = "GB"; } else { val = BYTES.toTeraBytes(bytes); unitStr = "TB"; } return String.format("%." + decimals + "f%s", val, unitStr); } } |
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
import java.io.*; import java.lang.management.*; import java.util.*; import java.util.concurrent.*; import java.util.function.*; import java.util.stream.*; public class ListSorting { private static final ByteWatcher byteWatcher = new ByteWatcher(); public static void main(String... args) throws IOException { for (int i = 0; i < 10; i++) { testAll(); System.out.println(); } } private static void testAll() { for (int size = 100_000; size <= 10_000_000; size *= 10) { List jumble = ThreadLocalRandom.current() .doubles(size) .boxed() .collect(Collectors.toList()); test(ArrayList::new, jumble); test(LinkedList::new, jumble); test(Vector::new, jumble); test(CopyOnWriteArrayList::new, jumble); test(doubles -> Arrays.asList( jumble.stream().toArray(Double[]::new) ), jumble); } } private static void test( UnaryOperator<List> listConstr, List list) { sortOld(listConstr.apply(list)); sortNew(listConstr.apply(list)); } private static void sortOld(List list) { measureSort("Old", list, () -> sort(list)); } private static void sortNew(List list) { measureSort("New", list, () -> list.sort(null)); } private final static ThreadMXBean tmbean = ManagementFactory.getThreadMXBean(); private static void measureSort(String type, List list, Runnable sortJob) { try { long time = tmbean.getCurrentThreadUserTime(); byteWatcher.reset(); sortJob.run(); long bytes = byteWatcher.calculateAllocations(); time = tmbean.getCurrentThreadUserTime() - time; time = TimeUnit.MILLISECONDS.convert( time, TimeUnit.NANOSECONDS); System.out.printf( "%s sort %s %,3d in %dms and bytes %s%n", type, list.getClass().getName(), list.size(), time, Memory.format(bytes, Memory.BYTES, 2)); } catch (UnsupportedOperationException ex) { System.out.println("Old sort: Cannot sort " + list.getClass().getName() + " " + ex); } } /** * {@linkplain java.util.Collections#sort Copied from Java 7} */ @SuppressWarnings({"unchecked", "rawtypes"}) public static void sort(List list) { Object[] a = list.toArray(); Arrays.sort(a); ListIterator i = list.listIterator(); for (Object e : a) { i.next(); i.set((E) e); } } } |
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
import java.util.*; import java.util.function.*; import java.util.stream.*; public class SortingLikeABoss { public static <E, R extends List> R parallelSort( List list, Function<List, R> listConstructor) { return listConstructor.apply( list.parallelStream() .sorted() .collect(Collectors.toList())); } } |
Aqui tenemos un ejemplo donde generamos tres tipos distintos de listas utilizando nuestro método parallelSort():
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
import org.junit.Test; import java.util.*; import java.util.concurrent.*; import java.util.stream.*; import static org.junit.Assert.assertEquals; public class SortingLikeABossTest { @Test public void testBossSorting() { List jumble = ThreadLocalRandom.current() .doubles(1_000_000) .parallel() .boxed() .collect(Collectors.toList()); List sorted = new ArrayList(jumble); Collections.sort(sorted); ArrayList al = SortingLikeABoss.parallelSort( jumble, ArrayList::new ); assertEquals(sorted, al); LinkedList ll = SortingLikeABoss.parallelSort( jumble, LinkedList::new ); assertEquals(sorted, ll); CopyOnWriteArrayList cowal = SortingLikeABoss.parallelSort( jumble, CopyOnWriteArrayList::new ); assertEquals(sorted, cowal); } } |
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.
