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 manera más eficiente? ¿Cuánto tiempo tomará?Cómo ordenar 100 GB de cadenas
estoy repitiendo básicamente Krystian's answer, pero elaboración:
Sí que tiene que hacer esto más o menos en su sitio, ya que tienen poca memoria 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.
Luego, cualquier algoritmo in situ como quicksort funciona bastante bien.
El tiempo de ejecución está seguramente 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.
Buen punto, pero estaría un poco preocupado por los tiempos de búsqueda. Este método parece requerir muchas búsquedas, por lo que un rendimiento sostenido de 100MB/seg puede no ser la mejor medida. Tenemos que mover alrededor de 100 * 2^30/2^8 ~ 100 * 2^22 cuerdas. Si no tenemos cuidado, podríamos necesitar decir una búsqueda por cada 100 escrituras. Si cada búsqueda es 4ms ~ 2^-8 seg, tomaría algo así como 2^14 sec ~ 4.5 h. – Krystian
Obviamente estoy un poco lento hoy, ¿cómo llenas el conjunto de índices? Veo que una vez que ha creado la matriz de índices, es fácil y rápido ordenarla en la memoria, pero no entiendo cómo se estableció para construirla en primer lugar. –
@Kristian - Creo que la estimación de 1 búsqueda por cada 100 registros escritos es muy optimista ... –
A1. Probablemente desee implementar algún tipo 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 la fusión para ordenar:
Combinar especie es tan intrínsecamente secuencial que es práctico para ejecutarlo utilizando unidades de cinta lentos como dispositivos de entrada y de salida. Requiere muy poca memoria y la memoria requerida no depende del número de los elementos de datos.
Por la misma razón, también es útil para ordenar datos en el disco que es demasiado grande para caber completamente en la memoria primaria. En las unidades de cinta que pueden ejecutarse hacia atrás y hacia adelante , las pasadas de fusión se pueden ejecutar en ambas direcciones , lo que evita el tiempo de rebobinado.
Merge sort no necesariamente ordena en el lugar, lo que significa que es imposible de hacer. –
¡No es imposible en absoluto! –
Cuidar para elaborar, @High? No ha tratado los requisitos de espacio de merge-sort. –
Suena como una tarea que requiere el método External sorting. 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.
@Krystian, ¿conoce un tipo externo que no requiera 2n espacio? –
Debería usar un trie (también conocido como: árbol de prefijos): para construir una estructura similar a un árbol que le permita caminar fácilmente por 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).
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.
Vea mi comentario a su comentario a continuación. –
Aquí es cómo lo haría:
Fase 1 es dividir el 100 Gb en 50 particiones de 2 GB, lea cada una de las 50 particiones en la memoria, ordenar el uso de la clasificación rápida, y escribir. Desea las particiones ordenadas en el extremo superior del disco.
La Fase 2 fusiona 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. Entonces ...
Haga una combinación de 50 vías para llenar los primeros 20Gb en la parte inferior del disco.
Deslice los datos restantes en las 50 particiones hacia arriba para hacer otros 20Gb de espacio libre contiguo al final de los primeros 20Gb.
Repita los pasos 1. y 2. hasta que finalice.
Esto hace un montón de disco IO, pero se puede hacer uso de su 2Gb de memoria para el buffer en el copiado y la fusión de pasos para obtener el caudal de datos, reduciendo al mínimo el número de disco busca y hacer grandes transferencias de datos .
EDIT - @meriton ha propuesto una forma ingeniosa 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 al leer las particiones al revé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ñale que cualquier predicción teórica del tiempo tomado 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.
estimación de tiempo basado en la cantidad de datos que está escrito (suponiendo que el cálculo puede hacerse en paralelo y por lo tanto es libre): 100 GB (primera fase) + 100 GB (salida final) + 80GB (diapositiva 1) + 60 GB (diapositiva 2) + 40 GB (diapositiva 3) + 20 GB (diapositiva 4) = 400 GB escritos. Alrededor de cuatro horas, suponiendo una escritura sostenida conservadora de 30 MB/s. Más rápido en hardware decente, pero ¿qué hardware decente solo tiene 2 GB de RAM? ;-) –
... pero añada algo de tiempo para el hecho de que la lectura/clasificación/escritura en la fase 1 no puede ser paralela. También una posible objeción sobre lo que significa "dado 2 GB de RAM". Ha asumido que la disponibilidad de 2 GB de espacio de direcciones contiguas, todas respaldadas por RAM, no son intercambiables, lo cual creo que es justo dado que es una pregunta hipotética. Pero si la * máquina * tiene 2 GB de RAM y direccionamiento de 32 bits, sus fragmentos en la primera fase tendrán que ser más pequeños, lo que dará como resultado una clasificación de más de 50 pasos más adelante. Eventualmente, una fusión demasiado múltiple será lenta. –
Creo que se puede hacer una combinación de N vías con las comparaciones de logN por registro escrito. –
Creo que debería 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. :)
+1 - por pura audacia :-) –
Casi definitivamente necesitarías un * algoritmo de clasificación * en el lugar *. – stakx
¿Cómo se delimitan las cadenas? Como en: ¿es una secuencia con caracteres nulos entre ellos o son un grupo de almacenamientos intermedios con cierta longitud de conjunto y llenos de caracteres? Mi pregunta básica es: ¿Qué tan fácil es encontrar y mover las cuerdas? –
Esta fue una pregunta de la entrevista de Google. Lo sé, porque recibí la pregunta cuando me entrevisté allí. –