Ok, veamos necesito una forma eficiente de ordenar un archivo de de 100 GB, Cada registro del archivo son 36 Bytes en binario.
Usualmente lo hacia con archivos pequeños 10 o 5 GB pero en RAM. Esto con el algoritmo Introsort y es bastante eficiente, pero ahora estoy utilizando el mismo método pero en Disco duro ya que el archivo es muy grande, Lo que estoy haciendo es leer los registros del disco, cargarlos en memoria, compararlos y escribir en disco en caso de que necesiten ser ordenados. Este proceso es muy lento directo en el disco duro.
Podría tratar de dividir el proceso he ir cargando de 10 en 10 GB en RAM u otra cantidad ordenarlos en memoria y seguir con los demás pedazos, sin embargo el problema es ordenar entre pedazos separados.
El proceso de generación de registros es aleatorio y no se en que orden se generaran los registros, quiero hacer este proceso lo mas eficiente y rápido posible, ya que si funciona este archivo tendré que generar un archivo similar de 500 o 1000 GB. No tengo problemas de Espacio en disco.
¿Alguna idea adicional a hacerlo directo desde el disco duro?
Edit:
Ayer miestras publicaba este teme tambien pense en la solucion, pero no queria publicarla hasta implementarla.
Dado que la generación de los registros es aleatoria y es uniforme entre el rango de A a B entonces se me ocurre que una vez generado el archivo de 100 GB, dividir el rango de A a B en subrangos manejables en RAM
por decil algo tengo los siguientes rangos para registros de 32 bytes:
From 0000000000000000000000000000000000000000000000000000000000000000 to 0ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc
From 0ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc to 1999999999999999999999999999999999999999999999999999999999999998
From 1999999999999999999999999999999999999999999999999999999999999998 to 2666666666666666666666666666666666666666666666666666666666666664
From 2666666666666666666666666666666666666666666666666666666666666664 to 3333333333333333333333333333333333333333333333333333333333333330
From 3333333333333333333333333333333333333333333333333333333333333330 to 3ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc
From 3ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc to 4cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc8
From 4cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc8 to 5999999999999999999999999999999999999999999999999999999999999994
From 5999999999999999999999999999999999999999999999999999999999999994 to 6666666666666666666666666666666666666666666666666666666666666660
From 6666666666666666666666666666666666666666666666666666666666666660 to 733333333333333333333333333333333333333333333333333333333333332c
From 733333333333333333333333333333333333333333333333333333333333332c to 7ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff8
From 7ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff8 to 8cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc4
From 8cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc4 to 9999999999999999999999999999999999999999999999999999999999999990
From 9999999999999999999999999999999999999999999999999999999999999990 to a66666666666666666666666666666666666666666666666666666666666665c
From a66666666666666666666666666666666666666666666666666666666666665c to b333333333333333333333333333333333333333333333333333333333333328
From b333333333333333333333333333333333333333333333333333333333333328 to bffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff4
From bffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff4 to ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc0
From ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc0 to d99999999999999999999999999999999999999999999999999999999999998c
From d99999999999999999999999999999999999999999999999999999999999998c to e666666666666666666666666666666666666666666666666666666666666658
From e666666666666666666666666666666666666666666666666666666666666658 to f333333333333333333333333333333333333333333333333333333333333324
From f333333333333333333333333333333333333333333333333333333333333324 to ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
Entonces buscamos en el archivo los valores que entren en alguno de los rango anteriores, se ordenan en RAM y se escriben en un archivo aparte. Una vez completado el proceso para todos los sub-rangos se unen los archivos en uno solo y se borra el archivo desordenado.
Esto se puede hacer así debido a que la distribución de los registros es uniforme en el rango original de A a B, en caso de que la data este sesgada y existan mas valores en un sub-rango dado es conveniente poner un limite de cantidad de registros leídos para que el mismo no sobrepase la cantidad de RAM.
Saludos!
Mostrar Mensajes
