Hola, lo vi como una pregunta de entrevista y pensé que era una pregunta interesante de la que no estoy seguro acerca de la respuesta.¿Cuál es la mejor manera de ordenar 30 gb de cadenas con una computadora con 4 gb de RAM utilizando Ruby como lenguaje de scripting?
¿Cuál sería la mejor manera?
Suponiendo * nix:
system("sort <input_file >output_file")
"tipo" puede usar los archivos temporales para trabajar con archivos de entrada más grande que la memoria. Tiene interruptores para ajustar la cantidad de memoria principal y la cantidad de archivos temporales que usará, si es necesario.
Si no * nix, o el entrevistador frunce el ceño debido a la respuesta lateral, entonces codificaré un merge sort externo. Consulte la respuesta de @ psyho para obtener un buen resumen de un algoritmo de clasificación externo.
Gracias, esto es exactamente lo que creo que la respuesta debería ser ... No sé * nix, pero creo que aparece en la pregunta en algún momento. –
De nada, y gracias por la marca de verificación. –
Colóquelos en una base de datos y deje que la base de datos se preocupe por ello.
Los sistemas de bases de datos ya están manejando bien este problema en particular.
Una buena respuesta es usar el algoritmo merge-sort, adaptándolo a los datos del spool hacia y desde el disco según sea necesario para los pasos de fusión. Esto se puede hacer con demandas mínimas en la memoria.
Bueno, esta es una pregunta interesante para la entrevista ... casi todas estas preguntas tienen el propósito de poner a prueba tus habilidades y, afortunadamente, no se aplican directamente a ejemplos de la vida real. Esto se ve como uno, así que entremos en el rompecabezas
Cuando su entrevistador pregunta por "lo mejor", creo que solo habla sobre el rendimiento.
30 GB de cadenas es gran cantidad de datos. Todos los algoritmos de comparación-intercambio son Omega(n logn), por lo que llevará mucho tiempo. Si bien hay algoritmos O(n), como el conteo de ordenación, no están en su lugar, por lo que multiplicarás los 30GB y tienes solo 4GB de RAM (considera la cantidad de intercambio ...), así que iría con quicksort
Comience a pensar en la clasificación de conteo. Es posible que desee dividir primero las cadenas en grupos (utilizando el método de ordenamiento de radix), uno para cada letra. Es posible que desee escanear el archivo y, para cada letra inicial, mueva la cadena (por lo tanto, copie y elimine, sin desperdicio de espacio) en un archivo temporal. Es posible que desee repetir el proceso para los primeros 2, 3 o 4 caracteres de cada cadena. Luego, para reducir la complejidad de ordenar muchos archivos, puede ordenar por separado la cadena dentro de cada uno (usando quicksort ahora) y finalmente fusionar todos los archivos en orden.De esta manera usted todavía tiene una forma O(n logn) pero justo en menor n
Uno de hacer esto es utilizar un external sorting algorithm:
Suena como un algoritmo de dividir y vencer, con resultados almacenados en archivos separados y luego fusionados al final. – Omar