Vida de un Programador

Experiencias, ideas y programas

Challenge 4 – Missing numbers: Busca en detalle todo que puedas optimizar

Descripción del reto

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.
integer_1

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…
integer_2

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.

3 Respuestas a “Challenge 4 – Missing numbers: Busca en detalle todo que puedas optimizar

  1. Pingback:Tuenti Challenge 3 finalizado + Soluciones | Vida de un Programador

  2. Guillem Mateos (@guillemmateos) 08/05/2013 en 23:42

    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!😉

    • shoghicp 08/05/2013 en 23:45

      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.

Responder

Por favor, inicia sesión con uno de estos métodos para publicar tu comentario:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: