Trouver un entier pas parmi 4 milliards compte tenu de ceux

Question

C'est une question d'entrevue:

Compte tenu d'un fichier d'entrée avec quatre milliards de nombres entiers, de fournir un algorithme permettant de générer un nombre entier qui n'est pas contenue dans le fichier. Supposons que vous disposez de 1 Go de mémoire. Suivre jusqu'à ce que vous feriez si vous n'avez que 10 mo de mémoire.

Mon analyse:

La taille du fichier est de 4 * 10⁹ * 4 octets = 16 GiB.

Nous pouvons faire de tri externe, ainsi, nous obtenons pour connaître la gamme des nombres entiers. Ma question est quel est le meilleur moyen de détecter des manque les entiers triés grand nombre entier de jeux?

Ma compréhension(après la lecture de toutes les réponses):

En supposant que nous parlons de nombres entiers de 32 bits. Il y a 2^32 = 4*10⁹ distincts entiers.

Cas 1: nous avons 1 Go = 1 * 10⁹ octets * 8 bits/octet = 8 milliards de bits de la mémoire. Solution: si on utilise un bit qui représente un net entier, c'est assez. nous n'avons pas besoin de trier. Mise en œuvre:

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 * 10⁶ * 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.

Step 1: Build the counter of each bucket through the first pass through the file.
Step 2: Scan the buckets, find the first one who has less than 65536 hit.
Step 3: Build new buckets whose high 16-bit prefixes are we found in step2
through second pass of the file
Step 4: 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 avons diminution de la mémoire à travers l'augmentation de fichier pass.

---

Une précision pour ceux qui arrivent en retard: La question posée, ne veut pas dire qu'il y a exactement un nombre entier qui n'est pas contenue dans le fichier -- au moins ce n'est pas la façon dont la plupart des gens l'interprètent. De nombreux commentaires dans le fil de commentaires sont sur que la variation de la tâche, bien que. Malheureusement, le commentaire qui introduit au fil de commentaires a été supprimé par son auteur, alors maintenant, il ressemble à l'orphelin réponses à juste mal compris tout. Il est très déroutant. Désolé.

Answer 1

En supposant que "integer" signifie 32 bits: 10 MO d'espace est plus que suffisant pour vous de compter le nombre de numéros il y a dans le fichier d'entrée avec une 16-bits de préfixe, pour tous les 16 bits les préfixes en un seul passage dans le fichier d'entrée. Au moins l'un des seaux devra être frappé de moins de 2^16 fois. Faire un deuxième passage pour trouver le ou les numéros possibles de ce compartiment sont déjà utilisées.

Si cela signifie plus de 32 bits, mais encore des délimitée taille: Faire comme ci-dessus, en ignorant l'entrée de tous les nombres qui se situent à l'extérieur de l' (signé ou non signé; votre choix) 32 bits de large.

Si "integer" signifie mathématique entier: Lire dans l'entrée une fois et de garder une trace de la plus grand nombre de la longueur de la plus longue nombre que vous avez jamais vu. Lorsque vous avez terminé, sortie le maximum de plus un un nombre aléatoire qui a un chiffre de plus. (L'un des numéros dans le fichier est peut-être un bignum qui dure plus de 10 MO pour représenter exactement, mais si l'entrée est un fichier, alors vous pouvez au moins représentent la longueur de tout ce qui s'insère dans).

Answer 2

Statistiquement informé algorithmes décrits ci-dessous résoudre 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 statistiquement susceptibles d'être unique en O(1) fois. Par exemple, un pseudo aléatoire de 128 bits entier comme un GUID ne entrer en collision avec l'un des quatre milliards d'entiers dans l'ensemble, moins d'un tous les 64 milliards de milliards de milliards de cas.

Si les entiers sont limités à 32 bits on peut générer un nombre statistiquement parlant, c'est probablement unique dans un seul passage, avec beaucoup moins de 10 MO. Les chances qu'un pseudo-aléatoire entier de 32 bits, va entrer en collision avec l'une des 4 milliards de dollars existant entiers est d'environ 93% (4e9 / 2^32). Les chances que les 1000 pseudo-aléatoires entiers vont se heurtent à moins de un en de 12 000 milliards de milliards de milliards (cote-de-un-collision ^ 1000). Donc, si un programme maintient une structure de données contenant 1000 pseudo-aléatoire des candidats et parcourt les connu entiers, pour les éliminatoires de la les candidats, il est certain de trouver au moins un entier qui n'est pas dans le fichier.

Answer 3

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

Bentley présente plusieurs approches, y compris les trier, de Fusion et de Tri à l'aide de plusieurs fichiers externes, etc., Mais la meilleure méthode Bentley indique est un seul passage de l'algorithme à l'aide de champs de bits, qui avec humour, il appelle la "Merveille de Tri" :) Pour en venir au problème, de 4 milliards de numéros peut être représenté dans :

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

Le code à mettre en œuvre le bitset est simple: (prises à partir de solutions de page )

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

Bentley de l'algorithme effectue un seul passage sur le fichier, setting le bit correspondant dans le tableau, puis examine ce tableau à l'aide d' test macro ci-dessus pour trouver le nombre manquant.

Si la mémoire disponible est inférieure à 0.466 GO, Bentley propose une k-passer de l'algorithme, qui divise l'entrée dans les gammes en fonction de la mémoire disponible. Pour prendre un exemple très simple, si seulement 1 octet (j'.e de mémoire pour gérer 8 chiffres ) est disponible et la plage est de 0 à 31, nous divisons ce dans des plages de fréquences de 0 à 7, 8 à 15, 16 à 22, et ainsi de gérer cette gamme dans chacune des 32/8 = 4 passe.

HTH.

Answer 4

Étant donné que le problème ne spécifie pas qu’il faut trouver le plus petit nombre possible qui est pas dans le fichier, nous pourrions tout simplement générer un nombre qui est plus longtemps que l’entrée du fichier lui-même. :)

Answer 5

Pour la variante de RAM de 1 Go, vous pouvez utiliser un vecteur de bits. Vous devez allouer de 4 milliards de bits == 500Mo tableau d’octets. Pour chaque numéro de que lecture à partir de l’entrée, définissez le correspondant peu à '1'. Une fois que vous, itérer sur les bits, trouver le premier celui qui est toujours ' 0'. Son indice est la réponse.