Pregunta Encuentre un entero no entre los cuatro mil millones dados


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 con lo que haría si solo tiene 10 MB de memoria.

Mi análisis:

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

Podemos hacer una clasificación externa, así podemos conocer el rango de los enteros. Mi pregunta es ¿cuál es la mejor forma de detectar el entero faltante en los conjuntos de enteros grandes ordenados?

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

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

Caso 1: tenemos 1 GB = 1 * 109 * 8 bits = 8 mil millones de bits de memoria.   Solución: si usamos un bit que representa un entero distinto, es suficiente. nosotros no   necesito ordenar   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 * 106 * 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 pase de archivos.


Una aclaración para los que llegan tarde: la pregunta, como se le preguntó, no dice que hay exactamente un entero que no está contenido en el archivo, al menos no es así como la mayoría de las personas lo interpretan. Muchos comentarios en el hilo de comentarios son sobre la variación de la tarea, sin embargo. Lamentablemente, el comentario que introducido al hilo de comentarios más tarde lo borró su autor, por lo que ahora parece que las respuestas huérfanas simplemente lo malinterpretaron. Es muy confuso Lo siento.


641
2017-08-22 21:28


origen


Respuestas:


Suponiendo que "entero" significa 32 bits: Tener 10 MB de espacio es más que suficiente para contar 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 pasada a través del archivo de entrada. Al menos uno de los cubos habrá sido golpeado menos de 2 ^ 16 veces. Haga una segunda pasada para averiguar cuál de los posibles números en ese cubo ya se usa.

Si significa más de 32 bits, pero aún de tamaño limitado: Haga lo anterior, ignorando todos los números de entrada que caen fuera del rango de 32 bits (firmado o no, su elección).

Si "entero" significa entero matemático: Lea la entrada una vez y realice un seguimiento de la número más grande longitud del número más largo que hayas visto Cuando hayas terminado, salida el máximo más uno un número aleatorio que tiene un dígito más. (Uno de los números en el archivo puede ser un bignum que requiere más de 10 MB para representar exactamente, pero si la entrada es un archivo, entonces al menos puede representar el longitud de cualquier cosa que encaje en ella).


510
2017-08-23 05:04



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

Si se permiten números enteros muy grandes entonces uno puede generar un número que probablemente sea único en O (1) tiempo. 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 números enteros están limitados a 32 bits entonces uno puede generar un número que probablemente sea único en un solo pase utilizando 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 es aproximadamente 93% (4e9 / 2 ^ 32). La probabilidad de que 1000 enteros pseudoaleatorios colisionen es menos de uno en 12,000 billones de billones (odds-of-one-collision ^ 1000). Entonces, si un programa mantiene una estructura de datos que contiene 1000 candidatos pseudoaleatorios y recorre los enteros conocidos, eliminando las coincidencias de los candidatos, es casi seguro que encontrará al menos un entero que no está en el archivo.


184
2017-08-23 04:20



Una discusión detallada sobre este problema ha sido discutida en Jon Bentley "Columna 1. Cracking the Oyster" Programación de perlas Addison-Wesley pp.3-10

Bentley analiza varios enfoques, incluido el ordenamiento externo, Merge Sort utilizando varios archivos externos, etc., pero el mejor método que Bentley sugiere es un algoritmo de paso único usando campos de bits, que él humorísticamente llama "Wonder Sort" :) Al llegar al problema, se pueden representar 4 mil millones de números en:

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

El código para implementar el conjunto de bits es simple: (tomado de 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, setting el bit apropiado en la matriz y luego examina esta matriz usando test macro arriba para encontrar el número que falta.

Si la memoria disponible es menor a 0.466 GB, Bentley sugiere un algoritmo 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 y así sucesivamente y manejar este rango en cada uno de 32/8 = 4 pasa.

HTH.


138
2017-08-23 11:07



Como el problema no especifica que tenemos que encontrar el número más pequeño posible que no está en el archivo, podríamos generar un número que sea más largo que el archivo de entrada en sí. :)


111
2017-08-22 21:17



Para la variante de RAM de 1 GB puede usar un vector de bits. Debe asignar 4 mil millones de bits == 500 MB de matriz de bytes. Para cada número que lea desde la entrada, ajuste el bit correspondiente a '1'. Una vez que lo hayas hecho, itera sobre los bits, encuentra el primero que todavía es '0'. Su índice es la respuesta.


53
2017-08-23 05:58



Si son enteros de 32 bits (probablemente por la elección de ~ 4 mil millones de números cerca de 2 ^ 32), su lista de 4 mil millones de números ocupará como máximo el 93% de los enteros posibles (4 * 10 ^ 9 / (2) ^ 32)). Por lo tanto, si crea una matriz de bits de 2 ^ 32 bits con cada bit inicializado en cero (que ocupará 2 ^ 29 bytes ~ 500 MB de RAM, recuerde un byte = 2 ^ 3 bits = 8 bits), lea atentamente lista de enteros y para cada int establece el elemento de matriz de bits correspondiente de 0 a 1; y luego lee tu matriz de bits y devuelve el primer bit que sigue siendo 0.

En el caso de que tenga menos RAM (~ 10 MB), esta solución debe modificarse ligeramente. 10 MB ~ 83886080 bits es aún suficiente para hacer una matriz de bits para todos los números entre 0 y 83886079. Así que podría leer su lista de entradas; y solo grabe #s que están entre 0 y 83886079 en su matriz de bits. Si los números se distribuyen al azar; con una probabilidad abrumadora (difiere en un 100% en aproximadamente 10 ^ -2592069) encontrará una int faltante). De hecho, si solo elige los números del 1 al 2048 (con solo 256 bytes de RAM), igual encontrará un porcentaje que falta (un porcentaje abrumador (99.99999999999999999999999999999999999999999999999999999999999995%) del tiempo.

Pero digamos que en lugar de tener alrededor de 4 mil millones de números; tenía algo así como 2 ^ 32 - 1 números y menos de 10 MB de RAM; por lo que cualquier rango pequeño de ints solo tiene una pequeña posibilidad de no contener el número.

Si tuviera garantizado que cada int en la lista fuera único, podría sumar los números y restar la suma con un # faltante a la suma completa (1/2)(2 ^ 32)(2 ^ 32 - 1) = 9223372034707292160 para encontrar la int faltante. Sin embargo, si un int se produjo dos veces, este método fallará.

Sin embargo, siempre puedes dividir y conquistar. Un método ingenuo sería leer a través de la matriz y contar el número de números que están en la primera mitad (0 a 2 ^ 31-1) y la segunda mitad (2 ^ 31, 2 ^ 32). Luego elige el rango con menos números y repite dividir ese rango por la mitad. (Digamos que si hubiera dos números menos en (2 ^ 31, 2 ^ 32) su próxima búsqueda contaría los números en el rango (2 ^ 31, 3 * 2 ^ 30-1), (3 * 2 ^ 30, 2 ^ 32). Sigue repitiendo hasta que encuentres un rango con cero números y tengas tu respuesta. Deberías tomar O (lg N) ~ 32 lecturas a través de la matriz.

Ese método fue ineficiente. Solo estamos usando dos enteros en cada paso (o aproximadamente 8 bytes de RAM con un entero de 4 bytes (32 bits)). Un mejor método sería dividir en sqrt (2 ^ 32) = 2 ^ 16 = 65536 bins, cada uno con 65536 números en un bin. Cada contenedor requiere 4 bytes para almacenar su conteo, por lo que necesita 2 ^ 18 bytes = 256 kB. Entonces bin 0 es (0 a 65535 = 2 ^ 16-1), bin 1 es (2 ^ 16 = 65536 a 2 * 2 ^ 16-1 = 131071), bin 2 es (2 * 2 ^ 16 = 131072 a 3 * 2 ^ 16-1 = 196607). En Python tendrías algo así como:

import numpy as np
nums_in_bin = np.zeros(65536, dtype=np.uint32)
for N in four_billion_int_array:
    nums_in_bin[N // 65536] += 1
for bin_num, bin_count in enumerate(nums_in_bin):
    if bin_count < 65536:
        break # we have found an incomplete bin with missing ints (bin_num)

Lea la lista de enteros de ~ 4 mil millones; y cuente cuántas casillas caen en cada uno de los 2 ^ 16 bandejas y encuentre un incomplete_bin que no tenga todos los 65536 números. Luego, vuelve a leer la lista de 4 mil millones de enteros; pero esta vez solo notamos cuando los enteros están en ese rango; volteando un poco cuando los encuentres.

del nums_in_bin # allow gc to free old 256kB array
from bitarray import bitarray
my_bit_array = bitarray(65536) # 32 kB
my_bit_array.setall(0)
for N in four_billion_int_array:
    if N // 65536 == bin_num:
        my_bit_array[N % 65536] = 1
for i, bit in enumerate(my_bit_array):
    if not bit:
        print bin_num*65536 + i
        break

43
2017-08-23 14:38



¿Por qué hacerlo tan complicado? Usted pregunta por un entero que no está presente en el archivo?

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

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


35
2017-08-23 20:17



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. Calcule el punto medio.

  3. Pasa por el archivo, contando cuántos números eran iguales, menores o más altos que el valor del punto medio.

  4. Si no hay números iguales, terminaste. El número de punto medio es la respuesta.

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

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

Esto es esencialmente lo mismo que La solución de Henning, excepto que usa dos contenedores en lugar de 16k.


29
2017-08-23 01:49



EDITAR Ok, esto no fue muy bien pensado ya que supone que los enteros en el archivo siguen una distribución estática. Aparentemente no es necesario, pero aun así uno debería intentar esto:


Hay inte4.3 mil millones de enteros de 32 bits. No sabemos cómo se distribuyen en el archivo, pero el peor caso es el que tiene la más alta entropía de Shannon: una distribución igual. En este caso, la probabilidad de que un entero no ocurra en el archivo es

((2³²-1) / 2³²) ⁴ ⁰⁰⁰ ⁰⁰⁰ 4 ≈ .4

Cuanto menor es la entropía de Shannon, mayor es la probabilidad en promedio, pero incluso en este peor caso, tenemos una probabilidad del 90% de encontrar un número no recurrente después de 5 conjeturas con enteros aleatorios. Simplemente cree esos números con un generador pseudoaleatorio, guárdelos en una lista. Luego lea int después de int y compárelo con todas sus suposiciones. Cuando hay una coincidencia, elimine esta entrada de la lista. Después de haber revisado todo el archivo, es probable que te quede más de una estimación. Usa cualquiera de ellos. En el caso raro (10% incluso en el peor de los casos) de que no quede ninguna conjetura, obtenga un nuevo conjunto de enteros aleatorios, tal vez más esta vez (10-> 99%).

Consumo de memoria: algunas docenas de bytes, complejidad: O (n), sobrecarga: neclectable, ya que la mayor parte del tiempo se utilizará en los inevitables accesos al disco duro en lugar de compararlos de todos modos.


El peor caso real, cuando lo hacemos no asumir una distribución estática, es que cada entero se produce como máximo. una vez, porque solo entonces 1 - 4000000000 / 2³² ≈ 6% de todos los enteros no ocurren en el archivo. Por lo tanto, necesitará algunas suposiciones más, pero eso no costará cantidades hirientes de memoria.


26
2017-08-24 02:43



Si tiene un entero que falta en el rango [0, 2 ^X - 1] luego simplemente xor todos juntos. Por ejemplo:

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

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


24
2017-08-23 03:04