java - descending - Cómo ordenar 100 GB de cadenas
quicksort java (7)
A1. Es probable que desee implementar alguna forma de merge-sort .
A2: más tiempo de lo que sería si tuviera 256 GB de RAM en su máquina.
Editar: picado por la crítica, cito el artículo de Wikipedia sobre el tipo de fusión:
La clasificación de fusión es tan inherentemente secuencial que es práctico ejecutarla usando unidades de cinta lentas como dispositivos de entrada y salida. Requiere muy poca memoria, y la memoria requerida no depende de la cantidad de elementos de datos.
Por la misma razón, también es útil para ordenar los datos en el disco que es demasiado grande para caber completamente en la memoria primaria. En las unidades de cinta que pueden ejecutarse tanto hacia atrás como hacia delante, las pasadas de fusión se pueden ejecutar en ambas direcciones, lo que evita el tiempo de rebobinado.
Dado un disco duro con 120 GB, 100 de los cuales están llenos con las cadenas de longitud 256 y 2 GB Ram, ¿cómo puedo ordenar esas cadenas en Java de la manera más eficiente? ¿Cuánto tiempo tardará?
AFAIK, merge-sort requiere tanto espacio libre como datos. Esto puede ser un requisito para cualquier clasificación externa que evite el acceso aleatorio, aunque no estoy seguro de esto.
Así es como lo haría:
La fase 1 consiste en dividir los 100 Gb en 50 particiones de 2 Gb, leer cada una de las 50 particiones en la memoria, ordenarlas con quicksort y escribirlas. Desea las particiones ordenadas en el extremo superior del disco.
La Fase 2 es fusionar las 50 particiones ordenadas. Este es el truco porque no tienes suficiente espacio en el disco para almacenar las particiones Y la salida ordenada final. Asi que ...
Haga una fusión de 50 vías para llenar los primeros 20 Gb en el extremo inferior del disco.
Deslice los datos restantes en las 50 particiones hacia arriba para hacer otros 20Gb de espacio libre contiguos al final de los primeros 20Gb.
Repita los pasos 1. y 2. hasta que se complete.
Esto genera una gran cantidad de discos IO, pero puede utilizar su memoria de 2 GB para almacenar en búfer los pasos de copiado y fusión para obtener el rendimiento de datos al minimizar el número de búsquedas de disco y realizar grandes transferencias de datos.
EDITAR - @meriton ha propuesto una manera inteligente de reducir la copia. En lugar de deslizarse, sugiere que las particiones se clasifiquen en orden inverso y se lean hacia atrás en la fase de fusión. Esto permitiría al algoritmo liberar el espacio de disco utilizado por las particiones (fase 2, paso 2) simplemente truncando los archivos de partición.
Las posibles desventajas de esto son una mayor fragmentación del disco y la pérdida de rendimiento debido a la lectura de las particiones hacia atrás. (En este último punto, leer un archivo hacia atrás en Linux / UNIX requiere más llamadas de sistema, y la implementación de FS puede no ser capaz de hacer "lectura anticipada" en la dirección inversa).
Finalmente, me gustaría señalar que cualquier predicción teórica del tiempo empleado por este algoritmo (y otros) son en gran parte conjeturas. El comportamiento de estos algoritmos en un disco JVM + real real OS + real es demasiado complejo para los cálculos de "retroceso para el sobre" para dar respuestas confiables. Un tratamiento adecuado requeriría una implementación, ajuste y evaluación comparativa reales.
Básicamente estoy repitiendo la respuesta de Krystian , pero elaborando:
Sí, necesita hacer esto más o menos en su lugar, ya que tiene poca RAM disponible. Pero los ingenuos en el lugar serían un desastre aquí solo por el costo de mover las cuerdas.
En lugar de mover las cuerdas, simplemente haga un seguimiento de las cadenas que deben intercambiarse con otras y moverlas, una vez, al final, hasta su punto final. Es decir, si tenía 1000 cadenas, haga una matriz de 1000 ints. array [i] es el lugar donde la cadena i debería terminar. Si array [17] == 133 al final, significa que la cadena 17 debería terminar en el lugar de la cadena 133. array [i] == i para que i comience. El intercambio de cadenas, entonces, es solo cuestión de intercambiar dos entradas.
Entonces, cualquier algoritmo in situ como quicksort funciona bastante bien.
El tiempo de ejecución seguramente está dominado por el movimiento final de las cuerdas. Suponiendo que cada uno se mueve, está moviendo alrededor de 100 GB de datos en escrituras de tamaño razonable. Podría suponer que el disco / controlador / sistema operativo puede mover alrededor de 100MB / seg por usted. Entonces, 1000 segundos más o menos? ¿20 minutos?
Pero cabe en la memoria? Tiene 100 GB de cadenas, cada una de las cuales tiene 256 bytes. ¿Cuántas cuerdas? 100 * 2 ^ 30/2 ^ 8, o alrededor de 419M de cuerdas. Necesita 419 millones de entradas, cada una de 4 bytes o aproximadamente 1,7 GB. Voila, cabe en tu 2GB.
Creo que deberías usar BogoSort. Puede que tenga que modificar el algoritmo un poco para permitir la clasificación en el lugar, pero eso no debería ser demasiado difícil. :)
Debe usar un trie (también conocido como: un árbol de prefijos): para construir una estructura similar a un árbol que le permita recorrer fácilmente sus cadenas de una manera ordenada comparando sus prefijos. De hecho, no necesita almacenarlo en la memoria. Puede construir el trie como un árbol de directorios en su sistema de archivos (obviamente, no del que provienen los datos).
Suena como una tarea que requiere un método de clasificación externo . El Volumen 3 de "El arte de la programación de computadoras" contiene una sección con amplia discusión de métodos de clasificación externos.