Question Trouver un nombre entier pas parmi quatre milliards donnés


C'est une question d'entrevue:

Étant donné un fichier d'entrée avec quatre milliards d'entiers, fournissez un algorithme pour générer un entier qui n'est pas contenu dans le fichier. Supposons que vous avez 1 Go de mémoire. Suivez ce que vous feriez si vous n'aviez que 10 Mo de mémoire.

Mon analyse:

La taille du fichier est 4 × 109× 4 octets = 16 Go.

Nous pouvons faire un tri externe, ainsi nous arrivons à connaître la gamme des entiers. Ma question est quelle est la meilleure façon de détecter l'entier manquant dans les grands ensembles entiers triés?

Ma compréhension (après avoir lu toutes les réponses):

En supposant que nous parlons d'entiers 32 bits. Il y a 2 ^ 32 = 4 * 109 entiers distincts.

Cas 1: nous avons 1 Go = 1 * 109 * 8 bits = 8 milliards de bits de mémoire.   Solution: si nous utilisons un bit représentant un entier distinct, cela suffit. nous ne le faisons pas   besoin de tri.   La mise en oeuvre:

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);
        }
    }
}

Cas 2: 10 Mo de mémoire = 10 * 106 * 8 bits = 80 millions 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.

Conclusion:     Nous diminuons la mémoire en augmentant le passage de fichier.


Une clarification pour ceux qui arrivent en retard: La question, telle que posée, ne dit pas qu'il y a exactement un entier qui n'est pas contenu dans le fichier - du moins ce n'est pas comme la plupart des gens l'interprètent. De nombreux commentaires dans le fil de commentaires sont à propos de cette variation de la tâche, cependant. Malheureusement le commentaire que introduit le fil de commentaires a été supprimé par son auteur plus tard, alors maintenant il semble que les réponses orphelines ont tout simplement mal compris. C'est très confus. Pardon.


641
2017-08-22 21:28


origine


Réponses:


En supposant que "entier" signifie 32 bits: Avoir 10 Mo d'espace est plus que suffisant pour que vous puissiez compter le nombre de nombres dans le fichier d'entrée avec un préfixe de 16 bits donné, pour tous les préfixes de 16 bits possibles en un seul passage dans le fichier d'entrée. Au moins un des godets aura été frappé moins de 2 ^ 16 fois. Effectuez un second passage pour trouver les numéros possibles dans ce compartiment.

Si cela signifie plus de 32 bits, mais toujours de taille délimitée: Faites comme ci-dessus, en ignorant tous les nombres d'entrée qui se trouvent en dehors de la plage 32 bits (signée ou non signée, votre choix).

Si "entier" signifie un nombre entier mathématique: Lire une fois l'entrée et garder une trace de la le plus grand nombre la longueur du plus long nombre que vous avez jamais vu. Lorsque vous avez terminé, la sortie le maximum plus un un nombre aléatoire qui a un chiffre de plus. (Un des nombres dans le fichier peut être un bignum qui prend plus de 10 Mo pour représenter exactement, mais si l'entrée est un fichier, alors vous pouvez au moins représenter le longueur de tout ce qui s'y trouve).


510
2017-08-23 05:04



Les algorithmes statistiquement informés résolvent ce problème en utilisant moins de passes que les approches déterministes.

Si de très grands entiers sont autorisés alors on peut générer un nombre qui est susceptible d'être unique en O (1) temps. Un entier pseudo-aléatoire de 128 bits comme un GUID n'entrera en collision avec l'un des quatre milliards d'entiers existants dans l'ensemble dans moins d'un cas sur 64 milliards de milliards de cas.

Si les entiers sont limités à 32 bits alors on peut générer un nombre qui est susceptible d'être unique en un seul passage en utilisant beaucoup moins de 10 Mo. La probabilité qu'un nombre entier 32 bits pseudo-aléatoire entre en collision avec l'un des 4 milliards d'entiers existants est d'environ 93% (4e9 / 2 ^ 32). Les probabilités que 1000 entiers pseudo-aléatoires entrent en collision sont inférieures à un sur 12 000 milliards de milliards de milliards (probabilité d'une collision ^ 1000). Donc, si un programme maintient une structure de données contenant 1000 candidats pseudo-aléatoires et itère à travers les entiers connus, en éliminant les correspondances des candidats, il est presque certain de trouver au moins un entier qui n'est pas dans le fichier.


184
2017-08-23 04:20



Une discussion détaillée sur ce problème a été discutée dans Jon Bentley "Colonne 1. Cracking l'huître" Perles de programmation Addison-Wesley pp.3-10

Bentley discute de plusieurs approches, y compris le tri externe, Merge Sort en utilisant plusieurs fichiers externes, etc. Mais la meilleure méthode que Bentley suggère est un algorithme en un seul passage utilisant champs de bits, qu'il appelle avec humour "Wonder Sort" :) Pour en venir au problème, 4 milliards de numéros peuvent être représentés dans:

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

Le code pour implémenter le bitset est simple: (tiré de page de solutions )

#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)); }

L'algorithme de Bentley fait un seul passage sur le fichier, setting le bit approprié dans le tableau, puis examine ce tableau en utilisant test macro ci-dessus pour trouver le nombre manquant.

Si la mémoire disponible est inférieure à 0,466 Go, Bentley suggère un algorithme k-pass, qui divise l'entrée en plages en fonction de la mémoire disponible. Pour prendre un exemple très simple, si seulement 1 octet (c'est-à-dire la mémoire pour gérer 8 numéros) était disponible et la gamme était de 0 à 31, nous divisons cela en plages de 0 à 7, 8-15, 16-22 et ainsi de suite et gérer cette gamme dans chacun des 32/8 = 4 passe.

HTH.


138
2017-08-23 11:07



Puisque le problème ne spécifie pas que nous devons trouver le plus petit nombre possible qui ne soit pas dans le fichier, nous pourrions simplement générer un nombre plus long que le fichier d'entrée lui-même. :)


111
2017-08-22 21:17



Pour la variante RAM de 1 Go, vous pouvez utiliser un vecteur de bits. Vous devez allouer 4 milliards de bits == 500 Mo byte array. Pour chaque numéro lu à l'entrée, réglez le bit correspondant sur '1'. Une fois que vous avez terminé, parcourez les bits, trouvez le premier qui est encore '0'. Son index est la réponse.


53
2017-08-23 05:58



Si ce sont des entiers de 32 bits (probablement du choix de ~ 4 milliards de nombres proches de 2 ^ 32), votre liste de 4 milliards de nombres occupera au maximum 93% des entiers possibles (4 * 10 ^ 9 / (2 ^ 32)). Donc, si vous créez un tableau de bits de 2 ^ 32 bits avec chaque bit initialisé à zéro (ce qui prendra 2 ^ 29 octets ~ 500 Mo de RAM, rappelez-vous un octet = 2 ^ 3 bits = 8 bits), lisez votre liste entière et pour chaque int définir l'élément de tableau de bits correspondant de 0 à 1; puis lisez votre tableau de bits et renvoyez le premier bit qui est toujours 0.

Dans le cas où vous avez moins de RAM (~ 10 Mo), cette solution doit être légèrement modifiée. 10 Mo ~ 83886080 bits est encore suffisant pour faire un tableau de bits pour tous les nombres compris entre 0 et 83886079. Ainsi, vous pouvez lire votre liste d'ints; et n'enregistre que les # compris entre 0 et 83886079 dans votre tableau de bits. Si les numéros sont distribués au hasard avec une probabilité écrasante (il diffère de 100% par environ 10 ^ -2592069) vous trouverez un int manquant). En fait, si vous choisissez seulement les numéros 1 à 2048 (avec seulement 256 octets de RAM) vous trouverez toujours un nombre manquant un pourcentage écrasant (99.99999999999999999999999999999999999999999999999999999999999995%) du temps.

Mais disons plutôt que d'avoir environ 4 milliards de numéros; vous aviez quelque chose comme 2 ^ 32 - 1 numéros et moins de 10 Mo de RAM; donc toute petite plage d'ints a seulement une petite possibilité de ne pas contenir le nombre.

Si vous aviez la garantie que chaque int dans la liste était unique, vous pouvez additionner les nombres et soustraire la somme avec un # manquant à la somme totale (1/2)(2 ^ 32)(2 ^ 32 - 1) = 9223372034707292160 pour trouver l'int. Cependant, si un int s'est produit deux fois, cette méthode échouera.

Cependant, vous pouvez toujours diviser et conquérir. Une méthode naïve consisterait à lire le tableau et à compter le nombre de nombres compris dans la première moitié (0 à 2 ^ 31-1) et dans la seconde moitié (2 ^ 31, 2 ^ 32). Ensuite, choisissez la gamme avec moins de nombres et répétez la division de cette gamme de moitié. (Dites s'il y avait deux nombres de moins dans (2 ^ 31, 2 ^ 32) alors votre prochaine recherche compterait les nombres dans la gamme (2 ^ 31, 3 * 2 ^ 30-1), (3 * 2 ^ 30, 2 ^ 32) Continuez à répéter jusqu'à ce que vous trouviez une plage avec des nombres nuls et que vous ayez votre réponse.Vous devriez prendre O (lg N) ~ 32 lectures à travers le tableau.

Cette méthode était inefficace. Nous n'utilisons que deux entiers dans chaque étape (ou environ 8 octets de RAM avec un entier de 4 octets (32 bits)). Une meilleure méthode serait de diviser en sqrt (2 ^ 32) = 2 ^ 16 = 65536 bins, chacun avec 65536 numéros dans une corbeille. Chaque bin nécessite 4 octets pour stocker son compte, vous avez donc besoin de 2 ^ 18 octets = 256 Ko. Donc bin 0 est (0 à 65535 = 2 ^ 16-1), bin 1 est (2 ^ 16 = 65536 à 2 * 2 ^ 16-1 = 131071), bin 2 est (2 * 2 ^ 16 = 131072 à 3 * 2 ^ 16-1 = 196607). En python, vous auriez quelque chose comme:

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)

Lisez la liste des entiers ~ 4 milliards; et comptez combien d'ints tombent dans chacune des 2 ^ 16 cases et trouvez un incomplete_bin qui n'a pas tous les 65536 nombres. Ensuite, vous lisez à nouveau la liste des 4 milliards d'entiers; mais cette fois-ci, remarquez seulement quand les entiers sont dans cette gamme; retournant un peu quand vous les trouvez.

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



Pourquoi le rendre si compliqué? Vous demandez un nombre entier non présent dans le fichier?

Selon les règles spécifiées, la seule chose que vous devez stocker est le plus grand entier que vous avez rencontré jusqu'à présent dans le fichier. Une fois le fichier entier lu, renvoyez un nombre 1 supérieur à celui-ci.

Il n'y a aucun risque de toucher maxint ou quoi que ce soit, car selon les règles, il n'y a pas de restriction à la taille de l'entier ou au nombre renvoyé par l'algorithme.


35
2017-08-23 20:17