On m'a posé cette 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 disposiez de 1 Go de mémoire. Suivez ce que vous feriez si vous ne disposez que de 10 Mo de mémoire.

Mon analyse:

La taille du fichier est de 4 × 10 ⁹ × 4 octets = 16 Go.

Nous pouvons effectuer un tri externe, nous permettant ainsi de connaître la plage 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 ³² = 4 * 10 ⁹ entiers distincts.

Cas 1: nous avons 1 Go = 1 * 10 ⁹ * 8 bits = 8 milliards de bits de mémoire.

Solution:

Si nous utilisons un bit représentant un entier distinct, cela suffit. nous n'avons pas besoin de trier.

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 * 10 ⁶ * 8 bits = 80 millions de bits

Solution:

Pour tous les préfixes 16 bits possibles, il y a 2 ¹⁶ nombres entiers = 65536, nous avons besoin de 2 ¹⁶ * 4 * 8 = 2 millions de bits. Nous avons besoin de construire 65536 godets. Pour chaque compartiment, nous avons besoin de 4 octets contenant toutes les possibilités, car le pire des cas est que les 4 milliards d'entiers appartiennent au même compartiment.

1. Créez le compteur de chaque compartiment lors du premier passage dans le fichier.
2. Scannez les seaux, trouvez le premier qui a touché moins de 65536.
3. Créez de nouveaux compartiments dont les préfixes 16 bits élevés se trouvent dans les étapes 2 à 2 du deuxième passage du fichier
4. Scannez les compartiments construits à l'étape 3, trouvez le premier compartiment qui n'a pas de succès.

Le code est très similaire à celui ci-dessus.

Conclusion: nous diminuons la mémoire en augmentant le nombre de passes de fichiers.

^{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 ainsi que la plupart des gens l'interprètent. De nombreux commentaires dans le fil de commentaires sont sur cette variation de la tâche, cependant. Malheureusement, le commentaire qui l'a introduit dans le fil de commentaires a été supprimé par la suite par son auteur, alors maintenant il semble que les réponses orphelines y aient tout simplement mal compris. C'est très déroutant, désolé.}

En supposant que "entier" signifie 32 bits : 10 Mo d'espace sont plus que suffisants pour que vous puissiez compter le nombre de numéros dans le fichier d'entrée avec un préfixe 16 bits donné, pour tous les préfixes 16 bits possibles en un seul passage à travers le fichier d'entrée. Au moins un des seaux aura été touché moins de 2 ¹⁶ fois. Faites un deuxième passage pour trouver lequel des numéros possibles dans ce compartiment est déjà utilisé.

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

Si "entier" signifie entier mathématique : Lisez une fois l'entrée et gardez une trace de la plus grande longueur de nombre du plus long que vous ayez jamais vu. Lorsque vous avez terminé, sortez le maximum plus un un nombre aléatoire qui a un chiffre de plus. (L'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 la longueur de tout ce qui s'y trouve).

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 nombres entiers sont autorisés, alors on peut générer un nombre qui est susceptible d'être unique dans le temps O (1). Un entier pseudo-aléatoire de 128 bits comme un GUID n'entrera en collision qu'avec l'un des quatre milliards d'entiers existants dans l'ensemble dans moins d'un cas sur 64 milliards de milliards de milliards.

Si les entiers sont limités à 32 bits, alors on peut générer un nombre qui est susceptible d'être unique en une seule passe en utilisant beaucoup moins de 10 Mo. La probabilité qu'un entier pseudo-aléatoire de 32 bits entre en collision avec l'un des 4 milliards d'entiers existants est d'environ 93% (4e9 / 2 ^ 32). La probabilité que 1000 entiers pseudo-aléatoires entrent tous en collision est inférieure à un sur 12 000 milliards de milliards de dollars (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, éliminant les correspondances des candidats, il est presque certain de trouver au moins un entier qui ne figure pas dans le fichier.

Une discussion détaillée sur ce problème a été discutée dans Jon Bentley "Colonne 1. Cracking the Oyster" Programming Pearls Addison-Wesley pp.3-10

Bentley discute plusieurs approches, y compris le tri externe, le tri par fusion à l'aide de plusieurs fichiers externes, etc., mais la meilleure méthode suggérée par Bentley est un algorithme à un seul passage utilisant des champs de bits , qu'il appelle avec humour "Wonder Sort" :). les nombres peuvent être représentés dans:

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

Le code pour implémenter le jeu de bits est simple: (extrait de la page des 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 effectue une seule passe sur le fichier, en settingant le bit approprié dans le tableau, puis examine ce tableau à l'aide de la testmacro 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 de la mémoire pour gérer 8 chiffres) était disponible et que la plage était de 0 à 31, nous la divisons en plages de 0 à 7, 8-15, 16-22, etc. et gérer cette plage dans chacune des 32/8 = 4passes.

HTH.

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

Pour la variante 1 Go de RAM, vous pouvez utiliser un vecteur de bits. Vous devez allouer 4 milliards de bits == 500 Mo d'octets. Pour chaque nombre que vous lisez à partir de l'entrée, définissez le bit correspondant sur «1». Une fois que vous avez terminé, parcourez les bits, trouvez le premier qui est toujours «0». Son indice est la réponse.

S'il s'agit d'entiers 32 bits (probablement parmi le choix de ~ 4 milliards de nombres proches de 2 ³² ), votre liste de 4 milliards de nombres occupera au plus 93% des entiers possibles (4 * 10 ⁹ / (2 ³² ) ). Donc, si vous créez un tableau de bits de 2 ³² bits avec chaque bit initialisé à zéro (ce qui prendra 2 ²⁹ octets ~ 500 Mo de RAM; rappelez-vous un octet = 2 ³ bits = 8 bits), lisez votre liste d'entiers et pour chaque int, définissez 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 sont encore suffisants pour faire un tableau de bits pour tous les nombres entre 0 et 83886079. Vous pouvez donc lire votre liste d'entiers; et enregistrez uniquement les numéros compris entre 0 et 83886079 dans votre tableau de bits. Si les nombres sont distribués au hasard; avec une probabilité écrasante (il diffère de 100% d'environ 10 ^-2592069 ), vous trouverez un int manquant). En fait, si vous choisissez uniquement les nombres 1 à 2048 (avec seulement 256 octets de RAM), vous trouverez toujours un nombre manquant avec un pourcentage écrasant (99,9999999999999999999999999999999999999999999999999999999999999999999999999995%) du temps.

Mais disons au lieu d'avoir environ 4 milliards de numéros; vous aviez quelque chose comme 2 ³² - 1 numéros et moins de 10 Mo de RAM; de sorte que toute petite plage d'entiers n'a qu'une petite possibilité de ne pas contenir le nombre.

Si vous étiez assuré que chaque int de la liste était unique, vous pouvez additionner les nombres et soustraire la somme avec un # manquant à la somme complète (½) (2 ³² ) (2 ³² - 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 serait de lire le tableau et de compter le nombre de nombres qui se trouvent dans la première moitié (0 à 2 ³¹ -1) et la seconde moitié (2 ³¹ , 2 ³² ). Ensuite, choisissez la plage avec moins de nombres et répétez la division en deux. (Supposons qu'il y ait deux nombres en moins dans (2 ³¹ , 2 ³² ), votre prochaine recherche comptera les nombres dans la plage (2 ³¹ , 3 * 2 ³⁰ -1), (3 * 2 ³⁰ , 2 ³² ). répéter jusqu'à ce que vous trouviez une plage avec des nombres nuls et que vous ayez votre réponse. Devrait prendre O (lg N) ~ 32 lectures dans le tableau.

Cette méthode était inefficace. Nous n'utilisons que deux entiers à 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 ³² ) = 2 ¹⁶ = 65536 cases, chacune avec 65536 numéros dans une case. Chaque bac nécessite 4 octets pour stocker son nombre, vous avez donc besoin de 2 ¹⁸ octets = 256 Ko. Donc, le bac 0 est (0 à 65535 = 2 ¹⁶ -1), le bac 1 est (2 ¹⁶ = 65536 à 2 * 2 ¹⁶ -1 = 131071), le bac 2 est (2 * 2 ¹⁶ = 131072 à 3 * 2 ¹⁶ - 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 ~ 4 milliards d'entiers; et comptez combien d'ints tombent dans chacun des 2 ¹⁶ bacs et trouvez un incomplet_bin qui n'a pas tous les 65536 nombres. Ensuite, vous relisez la liste des 4 milliards d'entiers; mais cette fois, ne remarquez que lorsque les nombres entiers sont dans cette plage; 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

Pourquoi rendre cela si compliqué? Vous demandez un 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 que le fichier entier a été lu, renvoyez un nombre supérieur à 1.

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

Cela peut être résolu dans très peu d'espace en utilisant une variante de recherche binaire.

1. Commencez avec la plage de nombres autorisée, 0jusqu'à 4294967295.

2. Calculez le point médian.

3. Parcourez le fichier en comptant le nombre de nombres égaux, inférieurs ou supérieurs à la valeur médiane.

4. Si aucun nombre n'était égal, vous avez terminé. Le nombre médian est la réponse.

5. Sinon, choisissez la plage qui avait le moins de nombres et répétez à partir de l'étape 2 avec cette nouvelle plage.

Cela nécessitera jusqu'à 32 analyses linéaires du fichier, mais il n'utilisera que quelques octets de mémoire pour stocker la plage et les nombres.

C'est essentiellement la même que la solution de Henning , sauf qu'elle utilise deux bacs au lieu de 16k.

EDIT Ok, cela n'a pas été bien pensé car cela suppose que les entiers dans le fichier suivent une distribution statique. Apparemment, ils n'en ont pas besoin, mais même alors, il faut essayer ceci:

Il y a environ 4,3 milliards d'entiers 32 bits. Nous ne savons pas comment ils sont distribués dans le fichier, mais le pire des cas est celui avec l'entropie de Shannon la plus élevée: une distribution égale. Dans ce cas, la probabilité qu'un nombre entier ne se produise pas dans le fichier est

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

Plus l'entropie de Shannon est faible, plus cette probabilité augmente en moyenne, mais même dans le pire des cas, nous avons une chance de 90% de trouver un nombre non récurrent après 5 suppositions avec des nombres entiers aléatoires. Il suffit de créer de tels nombres avec un générateur pseudo-aléatoire, de les stocker dans une liste. Ensuite, lisez int après int et comparez-le à toutes vos suppositions. En cas de correspondance, supprimez cette entrée de liste. Après avoir parcouru tout le fichier, il y a de fortes chances qu'il vous reste plus d'une supposition. Utilisez l'un d'eux. Dans le cas rare (10% même dans le pire des cas) où il n'y a plus de supposition, obtenez un nouvel ensemble d'entiers aléatoires, peut-être plus cette fois (10-> 99%).

Consommation de mémoire: quelques dizaines d'octets, complexité: O (n), surcharge: non détectable car la plupart du temps sera consacré aux accès inévitables au disque dur plutôt que de comparer les ints de toute façon.

Si un entier manque dans la plage [0, 2 ^ x - 1], il suffit de les xor tous ensemble. Par exemple:

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

(Je sais que cela ne répond pas exactement à la question , mais c'est une bonne réponse à une question très similaire.)

Ils peuvent chercher à voir si vous avez entendu parler d'un filtre Bloom probabiliste qui peut très efficacement déterminer absolument si une valeur ne fait pas partie d'un grand ensemble, (mais ne peut déterminer qu'avec une forte probabilité qu'il fait partie de l'ensemble.)

Sur la base du libellé actuel de la question d'origine, la solution la plus simple est:

Recherchez la valeur maximale dans le fichier, puis ajoutez-y 1.

Utilisez a BitSet. 4 milliards d'entiers (en supposant jusqu'à 2 ^ 32 entiers) compressés dans un BitSet à 8 par octet est 2 ^ 32/2 ^ 3 = 2 ^ 29 = environ 0,5 Go.

Pour ajouter un peu plus de détails - chaque fois que vous lisez un nombre, définissez le bit correspondant dans le BitSet. Ensuite, faites un passage sur le BitSet pour trouver le premier numéro qui n'est pas présent. En fait, vous pouvez le faire tout aussi efficacement en choisissant à plusieurs reprises un nombre aléatoire et en testant s'il est présent.

En fait, BitSet.nextClearBit (0) vous indiquera le premier bit non défini.

En regardant l'API BitSet, il semble ne prendre en charge que 0..MAX_INT, vous pouvez donc avoir besoin de 2 BitSets - un pour les numéros + et un pour les numéros have - mais les besoins en mémoire ne changent pas.

S'il n'y a pas de limite de taille, le moyen le plus rapide est de prendre la longueur du fichier et de générer la longueur du fichier + 1 nombre de chiffres aléatoires (ou simplement "11111 ..."). Avantage: vous n'avez même pas besoin de lire le fichier et vous pouvez réduire l'utilisation de la mémoire presque à zéro. Inconvénient: vous imprimerez des milliards de chiffres.

Cependant, si le seul facteur était de minimiser l'utilisation de la mémoire, et rien d'autre n'est important, ce serait la solution optimale. Cela pourrait même vous valoir le prix du «pire abus des règles».

Si nous supposons que la plage de nombres sera toujours 2 ^ n (une puissance paire de 2), alors exclusif ou fonctionnera (comme le montre une autre affiche). En ce qui concerne pourquoi, prouvons-le:

La théorie

Étant donné toute plage d'entiers basée sur 0 qui a des 2^néléments avec un élément manquant, vous pouvez trouver cet élément manquant simplement en xorant ensemble les valeurs connues pour produire le nombre manquant.

La preuve

Regardons n = 2. Pour n = 2, nous pouvons représenter 4 entiers uniques: 0, 1, 2, 3. Ils ont un motif binaire de:

• 0 - 00
• 1 - 01
• 2 - 10
• 3 - 11

Maintenant, si nous regardons, chaque bit est défini exactement deux fois. Par conséquent, étant donné qu'il est défini un nombre pair de fois, et exclusif-ou des nombres donnera 0. Si un seul numéro est manquant, l'exclusif-ou produira un nombre qui, lorsqu'il sera exclusif-oré avec le numéro manquant, entraînera 0. Par conséquent, le nombre manquant et le nombre exclusif oré résultant sont exactement les mêmes. Si nous supprimons 2, le xor résultant sera 10(ou 2).

Maintenant, regardons n + 1. Appelons le nombre de fois chaque bit est situé dans n, xet le nombre de fois chaque bit est situé dans n+1 y. La valeur de ysera égale à y = x * 2car il y a des xéléments avec le n+1bit mis à 0 et des xéléments avec le n+1bit mis à 1. Et puisque 2xsera toujours pair, n+1chaque bit sera toujours mis un nombre pair de fois.

Par conséquent, puisque n=2fonctionne et n+1fonctionne, la méthode xor fonctionnera pour toutes les valeurs de n>=2.

L'algorithme pour les plages basées sur 0

C'est assez simple. Il utilise 2 * n bits de mémoire, donc pour toute plage <= 32, 2 entiers 32 bits fonctionneront (en ignorant toute mémoire consommée par le descripteur de fichier). Et il fait un seul passage du fichier.

long supplied = 0;
long result = 0;
while (supplied = read_int_from_file()) {
    result = result ^ supplied;
}
return result;

L'algorithme pour les plages arbitraires

Cet algorithme fonctionnera pour des plages de n'importe quel nombre de début à n'importe quel nombre de fin, tant que la plage totale est égale à 2 ^ n ... Cela re-base essentiellement la plage pour avoir le minimum à 0. Mais cela nécessite 2 passes à travers le fichier (le premier pour saisir le minimum, le second pour calculer l'int manquant).

long supplied = 0;
long result = 0;
long offset = INT_MAX;
while (supplied = read_int_from_file()) {
    if (supplied < offset) {
        offset = supplied;
    }
}
reset_file_pointer();
while (supplied = read_int_from_file()) {
    result = result ^ (supplied - offset);
}
return result + offset;

Plages arbitraires

Nous pouvons appliquer cette méthode modifiée à un ensemble de plages arbitraires, car toutes les plages traverseront une puissance de 2 ^ n au moins une fois. Cela ne fonctionne que s'il y a un seul bit manquant. Il faut 2 passages d'un fichier non trié, mais il trouvera le numéro manquant unique à chaque fois:

long supplied = 0;
long result = 0;
long offset = INT_MAX;
long n = 0;
double temp;
while (supplied = read_int_from_file()) {
    if (supplied < offset) {
        offset = supplied;
    }
}
reset_file_pointer();
while (supplied = read_int_from_file()) {
    n++;
    result = result ^ (supplied - offset);
}
// We need to increment n one value so that we take care of the missing 
// int value
n++
while (n == 1 || 0 != (n & (n - 1))) {
    result = result ^ (n++);
}
return result + offset;

Fondamentalement, re-base la plage autour de 0. Ensuite, il compte le nombre de valeurs non triées à ajouter pendant qu'il calcule le ou exclusif. Ensuite, il ajoute 1 au nombre de valeurs non triées pour prendre soin de la valeur manquante (compter la valeur manquante). Ensuite, continuez à xorer la valeur n, incrémentée de 1 à chaque fois jusqu'à ce que n soit une puissance de 2. Le résultat est ensuite re-basé sur la base d'origine. Terminé.

Voici l'algorithme que j'ai testé en PHP (en utilisant un tableau au lieu d'un fichier, mais même concept):

function find($array) {
    $offset = min($array);
    $n = 0;
    $result = 0;
    foreach ($array as $value) {
        $result = $result ^ ($value - $offset);
        $n++;
    }
    $n++; // This takes care of the missing value
    while ($n == 1 || 0 != ($n & ($n - 1))) {
        $result = $result ^ ($n++);
    }
    return $result + $offset;
}

Alimenté dans un tableau avec n'importe quelle plage de valeurs (j'ai testé y compris les négatifs) avec un à l'intérieur de cette plage qui manque, il a trouvé la bonne valeur à chaque fois.

Une autre approche

Puisque nous pouvons utiliser le tri externe, pourquoi ne pas simplement rechercher un écart? Si nous supposons que le fichier est trié avant l'exécution de cet algorithme:

long supplied = 0;
long last = read_int_from_file();
while (supplied = read_int_from_file()) {
    if (supplied != last + 1) {
        return last + 1;
    }
    last = supplied;
}
// The range is contiguous, so what do we do here?  Let's return last + 1:
return last + 1;

Question piège, sauf si elle a été mal citée. Il suffit de lire le fichier une fois pour obtenir l'entier maximum net de revenir n+1.

Bien sûr, vous auriez besoin d'un plan de sauvegarde en cas de n+1débordement d'entier.

Vérifiez la taille du fichier d'entrée, puis sortez n'importe quel nombre qui est trop grand pour être représenté par un fichier de cette taille. Cela peut sembler une astuce bon marché, mais c'est une solution créative à un problème d'entrevue, il évite soigneusement le problème de mémoire et c'est techniquement 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);
    }
}

Doit imprimer 10 ^bitcount - 1 , qui sera toujours supérieur à 2 ^bitcount . Techniquement, le nombre à battre est de 2 ^bits - (4 * 10 ⁹ - 1) , car vous savez qu'il y a (4 milliards - 1) autres entiers dans le fichier, et même avec une compression parfaite, ils prendront au moins un bit chacun.

• L'approche la plus simple consiste à trouver le nombre minimum dans le fichier et à renvoyer 1 de moins que cela. Cela utilise le stockage O (1) et le temps O (n) pour un fichier de n nombres. Cependant, il échouera si la plage de numéros est limitée, ce qui pourrait rendre min-1 pas un nombre.

• La méthode simple et directe d'utilisation d'un bitmap a déjà été mentionnée. Cette méthode utilise le temps et le stockage O (n).

• Une méthode en 2 passes avec 2 ^ 16 seaux de comptage a également été mentionnée. Il lit 2 * n entiers, utilise donc le temps O (n) et le stockage O (1), mais il ne peut pas gérer les ensembles de données avec plus de 2 ^ 16 nombres. Cependant, il est facilement étendu à (par exemple) 2 ^ 60 entiers 64 bits en exécutant 4 passes au lieu de 2, et facilement adapté à l'utilisation de mémoire minuscule en utilisant uniquement autant de casiers que la mémoire et en augmentant le nombre de passes en conséquence, dans dans ce cas, le temps d'exécution n'est plus O (n) mais plutôt O (n * log n).

• La méthode de XOR'ing tous les nombres ensemble, mentionnée jusqu'ici par rfrankel et longuement par ircmaxell répond à la question posée dans stackoverflow # 35185 , comme l'a souligné ltn100. Il utilise le stockage O (1) et le temps d'exécution O (n). Si pour le moment nous supposons des entiers 32 bits, XOR a une probabilité de 7% de produire un nombre distinct. Justification: étant donné ~ 4G numéros distincts XOR ensemble, et ca. 300M pas dans le fichier, le nombre de bits définis dans chaque position de bit a une chance égale d'être impair ou pair. Ainsi, 2 ^ 32 nombres ont une probabilité égale d'apparaître comme résultat XOR, dont 93% sont déjà dans le fichier. Notez que si les nombres dans le fichier ne sont pas tous distincts, la probabilité de succès de la méthode XOR augmente.

Pour une raison quelconque, dès que j'ai lu ce problème, j'ai pensé à la diagonalisation. Je suppose des entiers arbitrairement grands.

Lisez le premier chiffre. Remplissez-le avec zéro bit jusqu'à ce que vous ayez 4 milliards de bits. Si le premier bit (d'ordre élevé) est 0, sortie 1; sinon, sortez 0. (Vous n'avez pas vraiment besoin de gauche-pad: vous sortez juste un 1 s'il n'y a pas assez de bits dans le nombre.) Faites de même avec le deuxième nombre, sauf utilisez son deuxième bit. Continuez à travers le fichier de cette façon. Vous sortirez un nombre de 4 milliards de bits un bit à la fois, et ce nombre ne sera pas le même que n'importe quel autre dans le fichier. Preuve: c'était le même que le nième nombre, alors ils seraient d'accord sur le nième bit, mais ils ne le sont pas par construction.

Vous pouvez utiliser des indicateurs de bits pour indiquer si un entier est présent ou non.

Après avoir parcouru le fichier entier, scannez chaque bit pour déterminer si le nombre existe ou non.

En supposant que chaque entier est de 32 bits, ils s'adapteront commodément à 1 Go de RAM si le balisage de bits est effectué.

Supprimez l'espace blanc et les caractères non numériques du fichier et ajoutez-les 1. Votre fichier contient maintenant un seul numéro qui ne figure pas dans le fichier d'origine.

De Reddit par Carbonetc.

Dans un souci d'exhaustivité, voici une autre solution très simple, qui prendra très probablement beaucoup de temps à exécuter, mais utilise très peu de mémoire.

Soit tous les entiers possibles la plage de int_minà int_max, et bool isNotInFile(integer)une fonction qui retourne vrai si le fichier ne contient pas un certain entier et faux sinon (en comparant cet certain entier avec chaque entier du fichier)

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

Pour la contrainte de mémoire de 10 Mo:

1. Convertissez le nombre en sa représentation binaire.
2. Créez un arbre binaire où gauche = 0 et droite = 1.
3. Insérez chaque nombre dans l'arbre en utilisant sa représentation binaire.
4. Si un numéro a déjà été inséré, les feuilles seront déjà créées.

Une fois terminé, il suffit de prendre un chemin qui n'a pas été créé auparavant pour créer le numéro demandé.

Nombre de 4 milliards = 2 ^ 32, ce qui signifie que 10 Mo peuvent ne pas être suffisants.

ÉDITER

Une optimisation est possible, si deux feuilles d'extrémité ont été créées et ont un parent commun, elles peuvent être supprimées et le parent signalé comme n'étant pas une solution. Cela coupe les branches et réduit le besoin de mémoire.

EDIT II

Il n'est pas nécessaire non plus de construire complètement l'arbre. Vous n'avez besoin de construire des branches profondes que si les nombres sont similaires. Si nous coupons aussi des branches, cette solution pourrait fonctionner en fait.

Je répondrai à la version 1 Go:

Il n'y a pas suffisamment d'informations dans la question, je vais donc énoncer quelques hypothèses d'abord:

L'entier est de 32 bits avec une plage de -2 147 483 648 à 2 147 483 647.

Pseudo-code:

var bitArray = new bit[4294967296];  // 0.5 GB, initialized to all 0s.

foreach (var number in file) {
    bitArray[number + 2147483648] = 1;   // Shift all numbers so they start at 0.
}

for (var i = 0; i < 4294967296; i++) {
    if (bitArray[i] == 0) {
        return i - 2147483648;
    }
}

Tant que nous faisons des réponses créatives, en voici une autre.

Utilisez le programme de tri externe pour trier le fichier d'entrée numériquement. Cela fonctionnera pour n'importe quelle quantité de mémoire que vous pourriez avoir (il utilisera le stockage de fichiers si nécessaire). Lisez le fichier trié et sortez le premier numéro manquant.

Élimination des bits

Une façon consiste à éliminer les bits, mais cela pourrait ne pas produire de résultat (il est probable que ce ne sera pas le cas). Psuedocode:

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

Nombre de bits

Gardez une trace du nombre de bits; et utiliser les bits avec le moins de quantités pour générer une valeur. Là encore, cela n'a aucune garantie de générer une valeur correcte.

Logique de portée

Gardez une trace d'une liste de plages ordonnées (triées par début). Une plage est définie par la structure:

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

Parcourez chaque valeur du fichier et essayez de la supprimer de la plage actuelle. Cette méthode n'a aucune garantie de mémoire, mais elle devrait plutôt bien fonctionner.

2 ^{128 * 10 18} + 1 (qui est (2 ⁸ ) ^{16 * 10 18} + 1) - ne peut-il pas être une réponse universelle pour aujourd'hui? Cela représente un nombre qui ne peut pas être conservé dans un fichier 16 EB, qui est la taille de fichier maximale dans n'importe quel système de fichiers actuel.

Je pense que c'est un problème résolu (voir ci-dessus), mais il y a un cas secondaire intéressant à garder à l'esprit car il pourrait être demandé:

S'il existe exactement 4 294 967 295 (2 ^ 32 - 1) entiers 32 bits sans répétition, et donc qu'un seul est manquant, il existe une solution simple.

Démarrez un total cumulé à zéro et, pour chaque entier du fichier, ajoutez cet entier avec un débordement 32 bits (en fait, runningTotal = (runningTotal + nextInteger)% 4294967296). Une fois terminé, ajoutez 4294967296/2 au total cumulé, toujours avec débordement 32 bits. Soustrayez ceci de 4294967296, et le résultat est l'entier manquant.

Le problème "un seul entier manquant" peut être résolu avec une seule exécution et seulement 64 bits de RAM dédiés aux données (32 pour le total en cours d'exécution, 32 pour lire dans le prochain entier).

Corollaire: La spécification plus générale est extrêmement simple à mettre en correspondance si nous ne sommes pas concernés par le nombre de bits que le résultat entier doit avoir. Nous générons juste un entier suffisamment grand pour qu'il ne puisse pas être contenu dans le fichier qui nous est donné. Encore une fois, cela prend de la RAM absolument minime. Voir le pseudocode.

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

Comme Ryan l'a dit en gros, triez le fichier, puis passez en revue les entiers et lorsqu'une valeur est ignorée, vous l'avez :)

EDIT chez downvoters: l'OP a mentionné que le fichier pouvait être trié, c'est donc une méthode valide.

Si vous n'assumez pas la contrainte 32 bits, renvoyez simplement un nombre 64 bits généré aléatoirement (ou 128 bits si vous êtes un pessimiste). Le risque de collision est 1 in 2^64/(4*10^9) = 4611686018.4(environ 1 sur 4 milliards). Vous auriez raison la plupart du temps!

(En plaisantant ... en quelque sorte.)