Vida de un Programador
Experiencias, ideas y programas
Challenge 4 – Missing numbers: Busca en detalle todo que puedas optimizar
Publicado por en 07/05/2013
Descripción del reto
En este reto tenías que buscar los números enteros no negativos (de 0 a 2147483647) que faltaban en un archivo, exactamente 100.
El archivo en cuestión ocupaba 8GB (menos unos bytes), y tras resolver unos «problemas» con PHP y archivos grandes, me puse mano a la obra.
Para ver como estaban guardados los números, y lo «desordenados» que estaban, lo abrí en un editor hexadecimal.
Según la descripción, el primer numero debía ser 2147459344. Los primeros 4 bytes 10 A1 FF 7F, leidos como Little-Endian, era eso. Si os fijais, el byte con mas valor (el ultimo en LE) es siempre 00 o 7F. Curioseando, y bajando un poco mas abajo, encontré esto…
A partir del byte 399800 los enteros estaban ordenados, del 10000 hasta el 2147383647. Descontando eso a los números iniciales, resulta que fuera de este rango solo hay 9900 + 10000 enteros sobre los que encontrar los 100 que faltan.
Esto es de gran importancia para la manera de desarrollar la prueba. De esta forma, la solución se puede encontrar en pocos segundos sin recorrer todo el archivo.
Mi solución consigue primero el indice desde el que los números van en orden automágicamente, seguido de la obtención del índice por el otro extremo.
Entonces, lee los números del inicio, los del final, los ordena, y busca los huecos en los que faltan números. Dan exactamente 100 enteros.
Luego, lee la entrada, y devuelve los números necesarios para pasar la prueba. En total, ~10 segundos.
Tal como dice el post, hay que intentar buscar siempre una optimización, ya que cargar todo el archivo en memoria y buscar en el puede resolver el problema si el archivo fuese completamente aleatorio, pero en este caso es mas eficiente de esta manera.
Vida de un Programador 
Pingback:Tuenti Challenge 3 finalizado + Soluciones | Vida de un Programador
Si no tienes manera de encontrar un patrón de los que faltan y/o te pueden modificar el fichero en que faltan números, la mejor alternativa que se me ocurrió es primero crear un fichero todo 0s (en linux lo haces usando /dev/zero) de nº de números total que debería tener el fichero de entrada bits (si fueran 2000000 de nums, 2000000 de bits). Luego empiezas a leer el fichero en que estan desordenados y a medida que lees cada número pones un 1 en la posición del fichero de 0 (para indicar que lo has encontrado). Esto lleva un rato, pero cuando lo tienes, buscar el número X que falta es francamente rápido. Como alternativa luego puedes leer de este fichero y guardar en otro cada número que te falta en una línea y buscarlo allí ya es ultrarrápido.
Saludos y felicidades por tu logro! 😉
También he visto en las soluciones partir el archivo en varias partes, y en cada una de ellas ordenar los números. Luego de busca dentro de cada parte por el número.