algorithm - trouver - nombre premier liste 1000




Trouver un nombre entier pas parmi quatre milliards donnés (20)

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.

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.


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

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

  2. Calculez le point milieu.

  3. Parcourez le fichier en boucle, en comptant combien de nombres étaient égaux, inférieurs ou supérieurs à la valeur du point central.

  4. Si aucun chiffre n'était égal, vous avez terminé. Le numéro de milieu est la réponse.

  5. Sinon, choisissez la plage ayant le moins de numéros et répétez l'étape 2 avec cette nouvelle plage.

Cela nécessitera jusqu'à 32 balayages linéaires à travers le fichier, mais il utilisera seulement quelques octets de mémoire pour stocker la gamme et les comptes.

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


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, on peut générer un nombre susceptible d'être unique en O (1). Un nombre entier pseudo-aléatoire de 128 bits comme un GUID ne va entrer en collision avec l'un des quatre milliards d'entiers existants dans l'ensemble que dans un cas sur 64 milliards de milliards de milliards.

Si les entiers sont limités à 32 bits, 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.


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.


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. :)


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 ..." s). Avantage: vous n'avez même pas besoin de lire le fichier, et vous pouvez minimiser l'utilisation de la mémoire presque à zéro. Inconvénient: Vous allez imprimer des milliards de chiffres.

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


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;

Si vous avez un nombre entier manquant dans la plage [0, 2 ^ x - 1] alors juste xor les 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.)


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.


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.


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.


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.


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.


As long as we're doing creative answers, here is another one.

Use the external sort program to sort the input file numerically. This will work for any amount of memory you may have (it will use file storage if needed). Read through the sorted file and output the first number that is missing.


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.


For the 10 MB memory constraint:

  1. Convert the number to its binary representation.
  2. Create a binary tree where left = 0 and right = 1.
  3. Insert each number in the tree using its binary representation.
  4. If a number has already been inserted, the leafs will already have been created.

When finished, just take a path that has not been created before to create the requested number.

4 billion number = 2^32, meaning 10 MB might not be sufficient.

MODIFIER

An optimization is possible, if two ends leafs have been created and have a common parent, then they can be removed and the parent flagged as not a solution. This cuts branches and reduces the need for memory.

EDIT II

There is no need to build the tree completely too. You only need to build deep branches if numbers are similar. If we cut branches too, then this solution might work in fact.


I will answer the 1 GB version:

There is not enough information in the question, so I will state some assumptions first:

The integer is 32 bits with range -2,147,483,648 to 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;
    }
}

If you don't assume the 32-bit constraint, just return a randomly generated 64-bit number (or 128-bit if you're a pessimist). The chance of collision is 1 in 2^64/(4*10^9) = 4611686018.4 (roughly 1 in 4 billion). You'd be right most of the time!

(Joking... kind of.)


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.


You can use bit flags to mark whether an integer is present or not.

After traversing the entire file, scan each bit to determine if the number exists or not.

Assuming each integer is 32 bit, they will conveniently fit in 1 GB of RAM if bit flagging is done.







algorithm