algorithm - Trouver un nombre entier pas parmi quatre milliards donnés




15 Answers

En supposant que «entier» signifie 32 bits : Avoir 10 Mo d'espace est plus que suffisant pour 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 dans un passage 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 borné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 : lisez l'entrée une fois et gardez la trace de la plus grande longueur de nombre du nombre le plus long que vous ayez jamais vu. Lorsque vous avez terminé, affichez le maximum plus 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 la longueur de tout ce qui s'y trouve).

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 de 4 × 10 9 × 4 octets = 16 GB.

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 * 10 9 entiers distincts.

Cas 1: nous avons 1 Go = 1 * 10 9 * 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 6 * 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 la passe 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. Beaucoup de commentaires dans le fil de commentaire sont à propos de cette variation de la tâche, cependant. Malheureusement, le commentaire qui l'a introduit dans le fil de commentaires a été plus tard supprimé par son auteur, alors maintenant il semble que les réponses orphelines ont tout simplement mal compris. C'est très confus. Pardon.




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

Bentley discute de plusieurs approches, y compris le tri externe, Merge Sort utilisant plusieurs fichiers externes, etc. Mais la meilleure méthode proposé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 bitset est simple: (tiré 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 un seul passage sur le fichier, en set le bit approprié dans le tableau, puis examine ce tableau en utilisant la macro de test 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 nombres) é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 passes.

HTH.




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.




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.




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

Il y a ≈4,3 milliards d'entiers 32 bits. Nous ne savons pas comment ils sont répartis dans le fichier, mais le pire est celui qui a 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é est élevée en moyenne, mais même dans ce cas le plus défavorable, nous avons une chance de 90% de trouver un nombre non-récurrent après 5 suppositions avec des entiers aléatoires. Créez simplement de tels nombres avec un générateur pseudo-aléatoire, stockez-les dans une liste. Puis 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 que vous ayez plus d'une estimation. Utilisez l'un d'entre eux. Dans le cas rare (10%, même dans le cas le plus défavorable) où il ne reste aucune estimation, obtenez un nouvel ensemble d'entiers aléatoires, peut-être plus cette fois (10-> 99%).

Consommation de mémoire: quelques douzaines d'octets, complexité: O (n), overhead: neclectable car la plupart du temps sera passé dans les accès au disque dur inévitable plutôt que de comparer ints de toute façon.

Le pire des cas, lorsque nous ne supposons pas une distribution statique, est que chaque entier se produit au maximum. une fois, car alors seulement 1 - 4000000000 / 2³² ≈ 6% de tous les entiers ne se produisent pas dans le fichier. Donc, vous aurez besoin de plus de suppositions, mais cela ne coûtera toujours pas beaucoup de mémoire.




Sur la base du libellé actuel de la question initiale, la solution la plus simple est la suivante:

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




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

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 nombre 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 dira le premier bit non-set.

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




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

La théorie

Étant donné toute gamme d'entiers basée sur 0 qui contient 2^n éléments avec un élément manquant, vous pouvez trouver cet élément manquant simplement en xorant ensemble les valeurs connues pour obtenir 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 modèle binaire de:

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

Maintenant, si nous regardons, chaque bit est fixé 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 nombre est manquant, l'exclusif-ou produira un nombre qui, lorsqu'il est exclusif avec le nombre manquant se traduira par 0. Par conséquent, le nombre manquant, et le nombre exclusif résultant sont exactement les mêmes. Si nous supprimons 2, le résultat obtenu sera 10 (ou 2).

Maintenant, regardons n + 1. Appelons le nombre de fois que chaque bit est défini dans n , x et le nombre de fois que chaque bit est défini dans n+1 y . The value of y will be equal to y = x * 2 because there are x elements with the n+1 bit set to 0, and x elements with the n+1 bit set to 1. And since 2x will always be even, n+1 will always have each bit set an even number of times.

Therefore, since n=2 works, and n+1 works, the xor method will work for all values of n>=2 .

The Algorithm For 0 Based Ranges

This is quite simple. It uses 2*n bits of memory, so for any range <= 32, 2 32 bit integers will work (ignoring any memory consumed by the file descriptor). And it makes a single pass of the file.

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

The Algorithm For Arbitrary Based Ranges

This algorithm will work for ranges of any starting number to any ending number, as long as the total range is equal to 2^n... This basically re-bases the range to have the minimum at 0. But it does require 2 passes through the file (the first to grab the minimum, the second to compute the missing int).

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;

Arbitrary Ranges

We can apply this modified method to a set of arbitrary ranges, since all ranges will cross a power of 2^n at least once. This works only if there is a single missing bit. It takes 2 passes of an unsorted file, but it will find the single missing number every time:

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;

Basically, re-bases the range around 0. Then, it counts the number of unsorted values to append as it computes the exclusive-or. Then, it adds 1 to the count of unsorted values to take care of the missing value (count the missing one). Then, keep xoring the n value, incremented by 1 each time until n is a power of 2. The result is then re-based back to the original base. Terminé.

Here's the algorithm I tested in PHP (using an array instead of a file, but same 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;
}

Fed in an array with any range of values (I tested including negatives) with one inside that range which is missing, it found the correct value each time.

Another Approach

Since we can use external sorting, why not just check for a gap? If we assume the file is sorted prior to the running of this algorithm:

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;



Trick question, unless it's been quoted improperly. Just read through the file once to get the maximum integer n , and return n+1 .

Of course you'd need a backup plan in case n+1 causes an integer overflow.




For some reason, as soon as I read this problem I thought of diagonalization. I'm assuming arbitrarily large integers.

Read the first number. Left-pad it with zero bits until you have 4 billion bits. If the first (high-order) bit is 0, output 1; else output 0. (You don't really have to left-pad: you just output a 1 if there are not enough bits in the number.) Do the same with the second number, except use its second bit. Continue through the file in this way. You will output a 4-billion bit number one bit at a time, and that number will not be the same as any in the file. Proof: it were the same as the nth number, then they would agree on the nth bit, but they don't by construction.




Just for the sake of completeness, here is another very simple solution, which will most likely take a very long time to run, but uses very little memory.

Let all possible integers be the range from int_min to int_max , and bool isNotInFile(integer) a function which returns true if the file does not contain a certain integer and false else (by comparing that certain integer with each integer in the file)

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



Strip the white space and non numeric characters from the file and append 1. Your file now contains a single number not listed in the original file.

From Reddit by Carbonetc.




Bit Elimination

One way is to eliminate bits, however this might not actually yield a result (chances are it won't). Psuedocode:

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

Bit Counts

Keep track of the bit counts; and use the bits with the least amounts to generate a value. Again this has no guarantee of generating a correct value.

Range Logic

Keep track of a list ordered ranges (ordered by start). A range is defined by the structure:

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

Go through each value in the file and try and remove it from the current range. This method has no memory guarantees, but it should do pretty well.




2 128*10 18 + 1 ( which is (2 8 ) 16*10 18 + 1 ) - cannot it be a universal answer for today? This represents a number that cannot be held in 16 EB file, which is the maximum file size in any current file system.




As Ryan said it basically, sort the file and then go over the integers and when a value is skipped there you have it :)

EDIT at downvoters: the OP mentioned that the file could be sorted so this is a valid method.




Related

algorithm

Tags

algorithm