sort - ordenar datos en una lista java

Ordenar una lista en paralelo sin crear una matriz temporal en Java 8

Question

Java 8 proporciona java.util.Arrays.parallelSort , que ordena las matrices en paralelo utilizando el marco fork-join. Pero no hay un correspondiente Collections.parallelSort para ordenar las listas.

Puedo usar toArray , ordenar esa matriz y almacenar el resultado en mi lista, pero eso aumentará temporalmente el uso de la memoria, que si estoy usando la ordenación paralela ya es alta porque la ordenación paralela solo paga las listas enormes. En lugar de duplicar la memoria (la lista más la memoria de trabajo de parallelSort), estoy usando tres veces (la lista, la matriz temporal y la memoria de trabajo de parallelSort). (La documentación de Arrays.parallelSort dice "El algoritmo requiere un espacio de trabajo que no sea mayor que el tamaño de la matriz original".)

Dejando de lado el uso de la memoria, Collections.parallelSort también sería más conveniente para lo que parece una operación bastante común. (Tiendo a no usar arrays directamente, por lo que ciertamente lo uso con más frecuencia que Arrays.parallelSort).

La biblioteca puede probar RandomAccess para evitar intentar, por ejemplo, ordenar rápidamente una lista vinculada, por lo que no puede ser una razón para una omisión deliberada.

¿Cómo puedo ordenar una lista en paralelo sin crear una matriz temporal?

Answer 1

Creo que está condenado a usar una implementación de List personalizada aumentada con su propio parallelSort o, si no, cambiar todo su otro código para almacenar la gran cantidad de datos en tipos de Array .

Este es el problema inherente a las capas de tipos de datos abstractos. Están destinados a aislar al programador de los detalles de la implementación. Pero cuando los detalles de la implementación son importantes, como en el caso del modelo de almacenamiento subyacente para la clasificación, el aislamiento por lo demás espléndido deja al programador indefenso.

Los documentos de clasificación de List estándar proporcionan un ejemplo. Después de la explicación que se utiliza mergesort , dicen

La implementación predeterminada obtiene una matriz que contiene todos los elementos de esta lista, ordena la matriz e itera sobre esta lista restableciendo cada elemento desde la posición correspondiente en la matriz. (Esto evita el rendimiento de n2 log (n) que resultaría de intentar ordenar una lista vinculada en su lugar).

En otras palabras, "dado que no conocemos el modelo de almacenamiento subyacente para una List y no pudimos tocarlo si lo hiciéramos, hacemos una copia organizada de una manera conocida". La expresión entre paréntesis se basa en el hecho de que la List "ithth element accessor" en una lista vinculada es Omega (n), por lo que la combinación de matrices normal implementada con ella sería un desastre. De hecho, es fácil implementar mergesort de manera eficiente en listas enlazadas. El implementador de la List simplemente no puede hacerlo.

Una ordenación paralela en la List tiene el mismo problema. La ordenación secuencial estándar lo arregla con sort personalizadas en las implementaciones concretas de la List . La gente de Java simplemente no ha elegido ir allí todavía. Tal vez en Java 9.

Answer 2

No parece haber una forma sencilla de ordenar una List en paralelo en Java 8. No creo que esto sea fundamentalmente difícil; se parece más a un descuido para mí.

La dificultad con un hipotético Collections.parallelSort(list, cmp) es que la implementación de Collections no sabe nada sobre la implementación de la lista o su organización interna. Esto se puede ver al examinar la implementación de Java 7 de Collections.sort(list, cmp) . Como observó, tiene que copiar los elementos de la lista a una matriz, ordenarlos y luego volver a copiarlos en la lista.

Esta es la gran ventaja del método de extensión List.sort(cmp) sobre Collections.sort(list, cmp) . Puede parecer que esto es simplemente una pequeña ventaja sintáctica al poder escribir myList.sort(cmp) lugar de Collections.sort(myList, cmp) . La diferencia es que myList.sort(cmp) , al ser un método de extensión de interfaz, puede ser anulado por la implementación específica de la List . Por ejemplo, ArrayList.sort(cmp) ordena la lista en el lugar utilizando Arrays.sort() mientras que la implementación predeterminada implementa la antigua técnica copyout-sort-copyback.

Debería ser posible agregar un método de extensión parallelSort a la interfaz de la List que tenga una semántica similar a List.sort pero que se List.sort la clasificación en paralelo. Esto permitiría que ArrayList realice una ordenación directa in situ utilizando Arrays.parallelSort . (No me queda del todo claro qué debería hacer la implementación por defecto. Podría valer la pena hacer copyout-parallelSort-copyback). Dado que esto sería un cambio de API, no puede suceder hasta la próxima versión importante de Java SE .

En cuanto a una solución Java 8, hay un par de soluciones, ninguna muy bonita (como es típico de las soluciones). Podría crear su propia implementación de List basada en matriz y anular sort() para ordenar en paralelo. O puede subclasificar ArrayList , anular sort() , capturar la matriz elementData través de la reflexión y llamar a parallelSort() en ella. Por supuesto, simplemente puede escribir su propia implementación de List y proporcionar un método parallelSort() , pero la ventaja de anular List.sort() es que esto funciona en la interfaz de la List simple y no tiene que modificar todo el código en su base de código para utilizar una subclase de List diferente.

Answer 3

Solo estoy especulando aquí, pero veo varias buenas razones para que los algoritmos genéricos prefieran trabajar en arreglos en lugar de instancias de List :

• El acceso a los elementos se realiza a través de llamadas de método. A pesar de todas las optimizaciones que JIT puede aplicar, incluso para una lista que implementa RandomAccess , esto probablemente signifique una gran sobrecarga en comparación con los accesos de matriz simple que pueden optimizarse muy bien.
• Muchos algoritmos requieren copiar algunos fragmentos de la matriz a estructuras temporales. Existen métodos eficientes para copiar matrices o sus fragmentos. Una instancia de List arbitraria, por otro lado, no se puede copiar fácilmente. Habría que asignar nuevas listas, lo que plantea dos problemas. En primer lugar, esto significa asignar algunos objetos nuevos, lo que probablemente sea más costoso que la asignación de matrices. Segundo, el algoritmo tendría que elegir qué implementación de List debería asignarse para esta estructura temporal. Hay dos soluciones obvias, ambas malas: simplemente elige una implementación codificada, por ejemplo, ArrayList , pero también podría asignar arreglos simples también (y si estamos generando arreglos, es mucho más fácil si la fuente es también un arreglo ). O bien, permita que el usuario proporcione un objeto de fábrica de listas, lo que hace que el código sea mucho más complicado.
• Relacionado con el problema anterior: no hay una forma obvia de copiar una lista en otra debido a cómo está diseñada la API. Lo mejor que ofrece la interfaz de la List es el método addAll() , pero probablemente no sea eficiente en la mayoría de los casos (piense en asignar previamente la nueva lista a su tamaño objetivo frente a agregar elementos uno por uno, lo que hacen muchas implementaciones).
• La mayoría de las listas que deben ordenarse serán lo suficientemente pequeñas para que otra copia no sea un problema.

Probablemente, los diseñadores pensaron en la eficiencia de la CPU y la simplicidad del código, y esto se logra fácilmente cuando la API acepta matrices. Algunos idiomas, por ejemplo, Scala, tienen métodos de clasificación que funcionan directamente en las listas, pero esto tiene un costo y, probablemente, es menos eficiente que la clasificación de matrices en muchos casos (o, a veces, es probable que haya una conversión hacia y desde una matriz realizada detrás de la escena). ).

Answer 4

Usa lo siguiente:

yourCollection.parallelStream().sorted().collect(Collectors.toList());

Esto será paralelo al ordenar, debido a parallelStream() . Creo que esto es lo que quieres decir con orden paralelo?