muse - types of algorithms




Encuentra un número entero no entre cuatro mil millones dados (20)

Es una pregunta de entrevista:

Dado un archivo de entrada con cuatro mil millones de enteros, proporcione un algoritmo para generar un entero que no esté contenido en el archivo. Supongamos que tiene 1 GB de memoria. Haga un seguimiento de lo que haría si solo tuviera 10 MB de memoria.

Mi análisis:

El tamaño del archivo es 4 × 10 9 × 4 bytes = 16 GB.

Podemos hacer una clasificación externa, por lo que podemos conocer el rango de los enteros. Mi pregunta es ¿cuál es la mejor manera de detectar el número entero faltante en los grandes conjuntos enteros ordenados?

Mi comprensión (después de leer todas las respuestas):

Suponiendo que estamos hablando de enteros de 32 bits. Hay 2 ^ 32 = 4 * 10 9 enteros distintos.

Caso 1: tenemos 1 GB = 1 * 10 9 * 8 bits = 8 mil millones de bits de memoria. Solución: si usamos un bit que representa un entero distinto, es suficiente. no necesitamos orden Implementación:

int radix = 8;
byte[] bitfield = new byte[0xffffffff/radix];
void F() throws FileNotFoundException{
    Scanner in = new Scanner(new FileReader("a.txt"));
    while(in.hasNextInt()){
        int n = in.nextInt();
        bitfield[n/radix] |= (1 << (n%radix));
    }

    for(int i = 0; i< bitfield.lenght; i++){
        for(int j =0; j<radix; j++){
            if( (bitfield[i] & (1<<j)) == 0) System.out.print(i*radix+j);
        }
    }
}

Caso 2: 10 MB de memoria = 10 * 10 6 * 8 bits = 80 millones de bits

Solution: For all possible 16-bit prefixes, there are 2^16 number of
integers = 65536, we need 2^16 * 4 * 8 = 2 million bits. We need build
65536 buckets. For each bucket, we need 4 bytes holding all possibilities because
 the worst case is all the 4 billion integers belong to the same bucket.

step1: Build the counter of each bucket through the first pass through the file.
step2: Scan the buckets, find the first one who has less than 65536 hit.
step3: Build new buckets whose high 16-bit prefixes are we found in step2
through second pass of the file
step4: Scan the buckets built in step3, find the first bucket which doesnt
have a hit.

The code is very similar to above one.

Conclusión: disminuimos la memoria al aumentar el paso del archivo.

Una aclaración para aquellos que llegan tarde: la pregunta, como se hizo, no dice que exista exactamente un entero que no esté contenido en el archivo, al menos no es así como la mayoría de la gente lo interpreta. Sin embargo, muchos comentarios en el hilo de comentarios se refieren a esa variación de la tarea. Desafortunadamente, el comentario que lo introdujo en el hilo de comentarios fue posteriormente eliminado por su autor, por lo que ahora parece que las respuestas huérfanas simplemente lo malinterpretaron todo. Es muy confuso. Lo siento.


Elimine los espacios en blanco y los caracteres no numéricos del archivo y adjúntelos 1. Su archivo ahora contiene un solo número que no figura en el archivo original.

Desde Reddit por Carbonetc.


¿Por qué hacerlo tan complicado? ¿Pides un entero no presente en el archivo?

De acuerdo con las reglas especificadas, lo único que necesita almacenar es el entero más grande que haya encontrado hasta ahora en el archivo. Una vez que se haya leído el archivo completo, devuelva un número 1 mayor que eso.

No hay riesgo de golpear maxint ni nada, porque de acuerdo con las reglas, no hay ninguna restricción al tamaño del número entero o al número devuelto por el algoritmo.


Esto se puede resolver en muy poco espacio usando una variante de búsqueda binaria.

  1. Comience con el rango permitido de números, 0 a 4294967295 .

  2. Calcula el punto medio.

  3. Recorra el archivo y cuente cuántos números eran iguales, menores o mayores que el valor del punto medio.

  4. Si no hay números iguales, ya está hecho. El número del punto medio es la respuesta.

  5. De lo contrario, elija el rango que tenga menos números y repita desde el paso 2 con este nuevo rango.

Esto requerirá hasta 32 exploraciones lineales a través del archivo, pero solo usará unos pocos bytes de memoria para almacenar el rango y los conteos.

Esta es esencialmente la misma que la solución de Henning , excepto que usa dos contenedores en lugar de 16k.


Los algoritmos estadísticamente informados resuelven este problema utilizando menos pases que los enfoques deterministas.

Si se permiten enteros muy grandes, entonces se puede generar un número que probablemente sea único en el tiempo O (1). Un entero pseudoaleatorio de 128 bits como un GUID solo colisionará con uno de los cuatro mil millones de enteros existentes en el conjunto en menos de uno de cada 64 mil millones de billones de casos.

Si los enteros están limitados a 32 bits, entonces se puede generar un número que probablemente sea único en una sola pasada usando mucho menos de 10 MB. Las probabilidades de que un entero pseudoaleatorio de 32 bits colisione con uno de los 4 mil millones de enteros existentes son aproximadamente el 93% (4e9 / 2 ^ 32). Las probabilidades de que 1000 enteros pseudoaleatorios colisionen son menos de uno en 12,000 billones de billones (probabilidad de una colisión ^ 1000). Entonces, si un programa mantiene una estructura de datos que contiene 1000 candidatos pseudoaleatorios e itera a través de los enteros conocidos, eliminando las coincidencias de los candidatos, es casi seguro encontrar al menos un entero que no está en el archivo.


Pueden estar buscando para ver si ha oído hablar de un filtro Bloom probabilístico que puede determinar de manera muy eficiente si un valor no es parte de un conjunto grande (pero solo puede determinar con alta probabilidad que es un miembro del conjunto).


Según la redacción actual de la pregunta original, la solución más sencilla es:

Encuentre el valor máximo en el archivo, luego agregue 1.


Si le falta un entero del rango [0, 2 ^ x - 1], entonces solo xo todos ellos juntos. Por ejemplo:

>>> 0 ^ 1 ^ 3
2
>>> 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 6 ^ 7
5

(Sé que esto no responde exactamente a la pregunta, pero es una buena respuesta a una pregunta muy similar).


Si no hay un límite de tamaño, la forma más rápida es tomar la longitud del archivo y generar la longitud del archivo + 1 número de dígitos aleatorios (o simplemente "11111 ..." s). Ventaja: ni siquiera necesita leer el archivo, y puede minimizar el uso de memoria casi a cero. Desventaja: Imprimirás miles de millones de dígitos.

Sin embargo, si el único factor era minimizar el uso de la memoria, y nada más es importante, esta sería la solución óptima. Incluso podría obtener un premio por "el peor abuso de las reglas".


Una discusión detallada sobre este problema ha sido discutida en Jon Bentley "Columna 1. Rompiendo la ostra" Programando Perlas Addison-Wesley pp.3-10

Bentley discute varios enfoques, incluyendo la clasificación externa, Combinar clasificación usando varios archivos externos, etc., pero el mejor método que Bentley sugiere es un algoritmo de un solo paso que usa campos de bits , que con humor llama "Wonder Sort" :) Llegando al problema, 4 mil millones Los números se pueden representar en:

4 billion bits = (4000000000 / 8) bytes = about 0.466 GB

El código para implementar el conjunto de bits es simple: (tomado de la página de soluciones )

#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];

void set(int i) {        a[i>>SHIFT] |=  (1<<(i & MASK)); }
void clr(int i) {        a[i>>SHIFT] &= ~(1<<(i & MASK)); }
int  test(int i){ return a[i>>SHIFT] &   (1<<(i & MASK)); }

El algoritmo de Bentley hace una sola pasada sobre el archivo, set el bit apropiado en la matriz y luego examina esta matriz utilizando la macro de test arriba para encontrar el número faltante.

Si la memoria disponible es inferior a 0,466 GB, Bentley sugiere un algoritmo de K-pass, que divide la entrada en rangos dependiendo de la memoria disponible. Para tomar un ejemplo muy simple, si solo estaba disponible 1 byte (es decir, memoria para manejar 8 números) y el rango era de 0 a 31, lo dividimos en rangos de 0 a 7, 8-15, 16-22, etc. y manejar este rango en cada uno de 32/8 = 4 pases.

HTH.


Utilice un BitSet . 4 mil millones de enteros (asumiendo hasta 2 ^ 32 enteros) empaquetados en un BitSet a 8 por byte es 2 ^ 32/2 ^ 3 = 2 ^ 29 = aprox. 0.5 Gb.

Para agregar un poco más de detalles, cada vez que lea un número, establezca el bit correspondiente en el BitSet. Luego, haga un pase sobre el BitSet para encontrar el primer número que no está presente. De hecho, puede hacer esto con la misma eficacia al seleccionar repetidamente un número aleatorio y probar si está presente.

En realidad, BitSet.nextClearBit (0) le dirá el primer bit no establecido.

Al observar la API de BitSet, parece que solo es compatible con 0..MAX_INT, por lo que es posible que necesite 2 BitSets, uno para los números + ve y otro para los números, pero los requisitos de memoria no cambian.


Eliminación de bits

Una forma es eliminar los bits, sin embargo, esto podría no producir un resultado (es probable que no lo haga). Psuedocode:

long val = 0xFFFFFFFFFFFFFFFF; // (all bits set)
foreach long fileVal in file
{
    val = val & ~fileVal;
    if (val == 0) error;
}

Bit Counts

Mantenga un registro de los recuentos de bits; y usa los bits con las cantidades mínimas para generar un valor. De nuevo esto no tiene garantía de generar un valor correcto.

Logica de rango

Mantenga un registro de los rangos ordenados de una lista (ordenados por inicio). Un rango está definido por la estructura:

struct Range
{
  long Start, End; // Inclusive.
}
Range startRange = new Range { Start = 0x0, End = 0xFFFFFFFFFFFFFFFF };

Ir a través de cada valor en el archivo y tratar de eliminarlo del rango actual. Este método no tiene garantías de memoria, pero debería funcionar bastante bien.


Suponiendo que "entero" significa 32 bits : tener 10 MB de espacio es más que suficiente para que cuente cuántos números hay en el archivo de entrada con cualquier prefijo de 16 bits dado, para todos los posibles prefijos de 16 bits en una sola pasada el archivo de entrada. Al menos uno de los cubos será golpeado menos de 2 ^ 16 veces. Haga una segunda pasada para averiguar cuál de los posibles números de ese grupo ya se está utilizando.

Si significa más de 32 bits, pero aún de tamaño acotado : haga lo mismo que antes, ignorando todos los números de entrada que caigan fuera del rango de 32 bits (firmado o sin firmar; su elección).

Si "entero" significa entero matemático : lea la entrada una vez y haga un seguimiento de la longitud del número más grande del número más largo que haya visto. Cuando haya terminado, envíe el máximo más uno un número aleatorio que tenga un dígito más. (Uno de los números en el archivo puede ser un bignum que toma más de 10 MB para representar exactamente, pero si la entrada es un archivo, al menos puede representar la longitud de cualquier cosa que se ajuste).


Creo que este es un problema resuelto (ver más arriba), pero hay un caso secundario interesante que se debe tener en cuenta porque puede que se le pregunte:

Si hay exactamente 4,294,967,295 (2 ^ 32 - 1) enteros de 32 bits sin repeticiones, y por lo tanto solo falta uno, hay una solución simple.

Inicie un total acumulado en cero, y para cada entero en el archivo, agregue ese entero con desbordamiento de 32 bits (efectivamente, runningTotal = (runningTotal + nextInteger)% 4294967296). Una vez completado, agregue 4294967296/2 al total acumulado, nuevamente con un desbordamiento de 32 bits. Resta esto de 4294967296, y el resultado es el entero que falta.

El problema de "solo falta un entero" puede resolverse con una sola ejecución y solo 64 bits de RAM dedicados a los datos (32 para el total acumulado, 32 para leer en el siguiente entero).

Corolario: la especificación más general es extremadamente simple de igualar si no nos preocupa la cantidad de bits que debe tener el resultado entero. Simplemente generamos un número entero lo suficientemente grande como para que no pueda estar contenido en el archivo que se nos da. De nuevo, esto ocupa una memoria RAM absolutamente mínima. Ver el pseudocódigo.

# Grab the file size
fseek(fp, 0L, SEEK_END);
sz = ftell(fp);
# Print a '2' for every bit of the file.
for (c=0; c<sz; c++) {
  for (b=0; b<4; b++) {
    print "2";
  }
}

Mientras estemos haciendo respuestas creativas, aquí hay otra.

Utilice el programa de clasificación externa para ordenar el archivo de entrada numéricamente. Esto funcionará para cualquier cantidad de memoria que pueda tener (usará el almacenamiento de archivos si es necesario). Lea el archivo ordenado y muestre el primer número que falta.


Puede usar marcas de bit para marcar si un entero está presente o no.

Después de recorrer todo el archivo, escanee cada bit para determinar si el número existe o no.

Suponiendo que cada entero sea de 32 bits, cabrán convenientemente en 1 GB de RAM si se realiza el marcado de bits.


Solo para completar, aquí hay otra solución muy simple, que probablemente demorará mucho tiempo en ejecutarse, pero usa muy poca memoria.

Deje que todos los enteros posibles sean el rango de int_mina int_max, y bool isNotInFile(integer)una función que devuelve verdadero si el archivo no contiene un cierto número entero y falso lo demás (mediante la comparación de que ciertos entero con cada número entero en el archivo)

for (integer i = int_min; i <= int_max; ++i)
{
    if (isNotInFile(i)) {
        return i;
    }
}

2 128 * 10 18 + 1 (que es (2 8 ) 16 * 10 18 + 1): ¿no puede ser una respuesta universal para hoy? Esto representa un número que no se puede mantener en un archivo de 16 EB, que es el tamaño máximo de archivo en cualquier sistema de archivos actual.


Por alguna razón, tan pronto como leí este problema, pensé en la diagonalización. Estoy asumiendo enteros arbitrariamente grandes.

Lea el primer número. A la izquierda, rellene con cero bits hasta que tenga 4 mil millones de bits. Si el primer bit (orden alto) es 0, salida 1; de lo contrario, salida 0. (Realmente no tiene que usar el pad izquierdo: simplemente genera un 1 si no hay suficientes bits en el número). Haga lo mismo con el segundo número, excepto que use el segundo bit. Continuar a través del archivo de esta manera. Obtendrá un número de 4 billones de bits un bit a la vez, y ese número no será el mismo que cualquier otro en el archivo. Prueba: era el mismo que el número n, entonces estarían de acuerdo en el nth bit, pero no lo hacen por construcción.


Si no asume la restricción de 32 bits, simplemente devuelva un número de 64 bits generado aleatoriamente (o 128 bits si es un pesimista). La posibilidad de colisión es 1 in 2^64/(4*10^9) = 4611686018.4(aproximadamente 1 en 4 mil millones). ¡Tendrías razón la mayor parte del tiempo!

(Bromeando ... algo así.)


Verifique el tamaño del archivo de entrada, luego emita cualquier número que sea demasiado grande para ser representado por un archivo de ese tamaño. Esto puede parecer un truco barato, pero es una solución creativa para un problema de entrevista, evita el problema de la memoria y técnicamente es O (n).

void maxNum(ulong filesize)
{
    ulong bitcount = filesize * 8; //number of bits in file

    for (ulong i = 0; i < bitcount; i++)
    {
        Console.Write(9);
    }
}

Debe imprimir 10 bitcount - 1 , que siempre será mayor que 2 bitcount . Técnicamente, el número que debe superar es 2 bitcount - (4 * 10 9 - 1) , ya que sabe que hay (4 billones - 1) otros enteros en el archivo, e incluso con una compresión perfecta, ocuparán al menos un bit cada uno.





algorithm