elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Usando Git para manipular el directorio de trabajo, el índice y commits (segunda parte)


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  Ordenar archivo binario de 100GB
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Ordenar archivo binario de 100GB  (Leído 1,509 veces)
AlbertoBSD
Programador y
Moderador Global
***
Desconectado Desconectado

Mensajes: 3.674


🏴 Libertad!!!!!


Ver Perfil WWW
Ordenar archivo binario de 100GB
« en: 21 Enero 2021, 05:02 am »

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:

Código:
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!


« Última modificación: 21 Enero 2021, 14:01 pm por AlbertoBSD » En línea

Donaciones
1Coffee1jV4gB5gaXfHgSHDz9xx9QSECVW
Keyhunters telegram group (English)
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
leer archivo BINARIO « 1 2 3 4 »
Programación Visual Basic
WestOn 37 18,832 Último mensaje 3 Octubre 2008, 18:22 pm
por WestOn
Listar archivo binario
Programación C/C++
Teby45 0 1,770 Último mensaje 17 Septiembre 2010, 21:31 pm
por Teby45
Leer archivo binario en Vbs
Scripting
kapo.damy 2 3,566 Último mensaje 14 Diciembre 2011, 04:51 am
por kapo.damy
recorrer archivo binario
Programación C/C++
m@o_614 3 2,524 Último mensaje 25 Octubre 2013, 17:59 pm
por rir3760
Desensamblado de un archivo binario
Ingeniería Inversa
Omar_2013 3 2,344 Último mensaje 26 Noviembre 2014, 19:43 pm
por Omar_2013
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines