Trouver un entier pas parmi quatre milliards donnés ceux

c'est une question d'interview:

donné un fichier d'entrée avec quatre milliards d'entiers, fournir 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. Suivre jusqu'à ce que vous feriez si vous n'avez que 10 MO de mémoire.

mon analyse:

La taille du fichier est 4×10 9 ×4 octets = 16 GO.

nous peut faire le tri externe, ainsi nous apprenons à connaître la portée des entiers. Ma question Est Quelle est la meilleure façon de détecter le nombre 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 des entiers distincts.

Cas 1: nous avons 1 GB = 1 * 10 9 * 8 bits = 8 milliards de bits mémoire. Solution: si on utilise un bit représentant un entier distinct, c'est suffisant. nous n'avons pas besoin de trier. Application:

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: mémoire de 10 MB= 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 le débit de fichiers.


une clarification pour ceux qui arrivent en retard: la question, comme demandé, 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 ça que la plupart des gens l'interprètent. Beaucoup de commentaires dans le fil de commentaire sont au sujet de cette variation de la tâche, cependant. Malheureusement, le commentaire que introduit il au fil de commentaire a été plus tard supprimé par son auteur, il semble maintenant que les réponses orphelines à elle juste mal compris tout. Il est très déroutant. Désolé.

647
demandé sur SecureFish 2011-08-23 01:11:47
la source

30 ответов

en supposant que" entier "signifie 32 bits : avoir 10 Mo d'espace est plus que suffisant pour compter combien de nombres il y a dans le fichier d'entrée avec n'importe quel préfixe de 16 bits donné, pour tous les préfixes de 16 bits possibles dans un passage à travers le fichier d'entrée. Au moins un des seaux aura été frappé moins de 2^16 fois. Faites un second passage pour trouver lequel des nombres possibles dans ce seau sont déjà utilisés.

si elle signifie plus que 32 bits, mais toujours de taille limitée : faire comme ci-dessus, en ignorant tous les numéros d'entrée qui se trouvent à l'extérieur de la gamme (signé ou non signé; votre choix) 32 bits.

Si "integer" signifie mathématique entier : Lire dans l'entrée une fois et de garder trace de la plus grand nombre la longueur de la plus longue nombre que vous avez jamais vu. Lorsque vous avez terminé, 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 la longueur de tout ce qui lui correspond).

512
répondu Henning Makholm 2011-08-23 02:02:13
la source

algorithmes statistiquement informés 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 qui est susceptible d'être unique en O(1) Temps. Un entier pseudo-aléatoire de 128 bits comme un GUID ne entrera en collision avec l'un des quatre milliards d'entiers existants dans l'ensemble dans moins d'un 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 une seule passe en utilisant beaucoup moins de 10 MB. 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 en collision est inférieure à une sur 12.000 milliards de milliards de milliards (probabilité d'une collision ^ 1000). Donc si un programme maintient une donnée structure contenant 1000 candidats pseudo-aléatoires et itérates à travers les entiers connus, en éliminant les correspondances des candidats, il est tout sauf certain de trouver au moins un entier qui n'est pas dans le fichier.

185
répondu Ben Haley 2014-12-28 12:54:01
la source

une discussion détaillée sur ce problème a été discutée dans Jon Bentley " colonne 1. La fissuration de l'Huître" "151980920 de Programmation" Perles 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 Bentley suggère est un algorithme de passage unique en utilisant bit fields , dont il appelle avec humour " Wonder Sort" :) Pour en venir au problème, 4 milliards de 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 solutions 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)); }
L'algorithme de

Bentley fait un passage simple au-dessus du fichier, set ting le bit approprié dans le tableau et examine ensuite ce tableau en utilisant la macro 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 (I. la mémoire pour manipuler 8 nombres) était disponible et la gamme était de 0 à 31, nous divisons ceci en gammes de 0 à 7, 8-15, 16-22 et ainsi de suite et manipulons cette gamme dans chacun de 32/8 = 4 passes.

HTH.

139
répondu vine'th 2011-08-24 14:38:21
la source

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

112
répondu Andris 2012-04-16 14:42:16
la source

pour la variante 1 Go de RAM vous pouvez utiliser un vecteur bit. Vous devez allouer 4 milliards de bits = = 500 MB Byte tableau. Pour chaque nombre que vous avez lu à partir de l'entrée, définissez le bit correspondant à '1'. Une fois que vous avez fait, itérez au-dessus des bits, trouvez le premier qui est encore '0'. Son indice est la réponse.

53
répondu Itay Maman 2011-08-27 11:29:45
la source

S'ils sont entiers 32 bits (probablement du choix de ~4 milliards de nombres près de 2^32), votre liste de 4 milliards de nombres prendra au plus 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 (qui prendra 2^29 octets ~ 500 Mo de RAM; rappelez-vous un octet = 2^3 bits = 8 bits), lire à travers votre liste entière et pour chaque int définir l'élément de tableau de bits correspondant de 0 à 1; et puis lire à travers votre bit-array et retourner le premier bit qui est toujours 0.

dans le cas où vous avez moins de RAM (~10 MB), Cette solution doit être légèrement modifiée. 10 MB ~ 83886080 bits est encore assez pour faire un tableau de bits pour tous les nombres entre 0 et 83886079. Ainsi, vous pouvez lire votre liste d'ints; et n'enregistrer que les #s qui sont 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% par environ 10^-2592069 ), vous trouverez un manque int). En fait, si vous ne choisissez que les numéros de 1 à 2 048 (avec seulement 256 octets de RAM) que vous souhaitez toujours trouver un nombre manquant un pourcentage écrasant (99.99999999999999999999999999999999999999999999999999999999999995%) du temps.

mais disons au lieu d'avoir environ 4 milliards de nombres; vous aviez quelque chose comme 2^32-1 Nombres et moins de 10 MB de RAM; donc n'importe quelle petite gamme d'ints a seulement une petite possibilité de ne pas contenant le nombre.

si vous étiez assuré que chaque int dans la liste était unique, vous pourriez additionner les nombres et soustraire la somme avec un # manquant à la pleine somme (1/2) (2^32) (2^32 - 1) = 9223372034707292160 pour trouver l'int manquant. Cependant, si un int se 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 compter le nombre de nombres qui sont dans la première moitié (0 à 2^31-1) et la seconde moitié (2^31, 2^32). Ensuite, choisissez la fourchette avec moins de nombres et répétez en divisant cette fourchette en deux. (Par exemple, s'il y avait deux nombres en moins dans (2^31, 2^32) alors votre prochaine recherche compterait les nombres dans l'intervalle (2^31, 3*2^30-1), (3*2^30, 2^32). Continuez de répéter jusqu'à ce que vous trouviez une plage avec des nombres zéro et vous avez votre réponse. Devrait prendre o (lg N) ~ 32 lit à travers le tableau.

cette méthode était inefficace. Nous n'utilisent que deux entiers à chaque pas (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 des bacs contenant chacun 65536 numéros. Chaque bin nécessite 4 octets pour stocker son nombre, donc vous avez besoin de 2^18 octets = 256 kB. Donc ben 0 est (de 0 à 65535=2^16-1), bin 1 est (2^16=65536 à 2*2^16-1=131071), le réceptacle 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)

Lire grâce à la liste entière de ~4 milliards; et compter combien d'ints tombent dans chacun des 2^16 bins et trouver un incomplet_bin qui n'a pas tous les 65536 nombres. Ensuite, vous relisez la liste des 4 milliards d'entiers, mais cette fois, vous ne remarquez que les entiers se trouvant dans cette fourchette; vous retournez un peu lorsque 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
44
répondu dr jimbob 2013-07-10 20:59:44
la source

pourquoi le rendre si compliqué? Vous demandez un entier absent du 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, retournez un nombre 1 plus grand que cela.

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

35
répondu Pete 2011-08-23 18:38:13
la source

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

  1. commence par la fourchette de nombres autorisée, 0 à 4294967295 .

  2. calculez le point médian.

  3. boucle à travers le fichier, en comptant combien de nombres étaient égaux, inférieurs ou supérieurs à la valeur médiane.

  4. si aucun nombre n'est égal, c'est fini. Le point milieu est la réponse.

  5. sinon, choisissez la plage qui a le moins de nombres et répétez l'étape 2 avec cette nouvelle plage.

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

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

29
répondu hammar 2017-05-23 15:34:41
la source

EDIT Ok, ce n'était pas tout à fait réfléchi car il suppose que les entiers dans le fichier suivent une certaine 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 de 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 probabilite pour un entier de ne pas se produire dans le fichier est

( (232-1)/232 ) * .4

plus l'entropie de Shannon est faible, plus cette probabilité est élevée 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 conjectures avec des entiers aléatoires. Il suffit de créer de tels nombres avec un générateur de pseudorandom, les stocker dans une liste. Ensuite, lisez int après int et comparez - le à toutes vos suppositions. Quand il ya une correspondance, supprimer cette entrée de la liste. Après avoir parcouru tout le dossier, il y a de fortes chances qu'il vous reste plus d'une estimation. Utiliser l'un d'eux. Dans le cas rare (10%, même dans le pire des cas) où il ne reste aucune 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), overhead: neclectable que la plupart du temps sera passé dans les inévitables accès disque dur plutôt que de comparer les ints de toute façon.


Le pire cas réel, quand nous faisons pas supposer une distribution statique, est que chaque entier se produit max. une fois, parce qu'alors seulement 1-4000000000/232 ≈ 6% de tous les entiers ne se produisent pas dans le fichier. Donc vous aurez besoin de plus de conjectures, mais cela ne coûtera toujours pas des quantités blessantes de mémoire.
26
répondu leftaroundabout 2011-08-24 00:12:21
la source

si vous avez un entier manquant dans la gamme [0, 2^ x - 1] puis 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 à la question exactement , mais c'est une bonne réponse à une question très similaire.)

24
répondu rfrankel 2011-08-24 06:43:07
la source

D'après le libellé actuel de la question initiale, la solution la plus simple est:

Trouver la valeur maximale dans le fichier, puis ajouter 1.

17
répondu oosterwal 2011-08-23 07:04:09
la source

ils peuvent être à la recherche de voir si vous avez entendu parler d'un probabiliste filtre de fleur qui peut très efficacement déterminer absolument si une valeur ne fait pas partie d'un grand ensemble, (mais ne peut déterminer avec une forte probabilité, il est un membre de l'ensemble.)

16
répondu Paul 2011-08-24 01:20:45
la source

utiliser un BitSet . 4 milliards d'entiers (en supposant jusqu'à 2^32 entiers) empaqueté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 nombre qui n'est pas présent. En fait, vous pouvez le faire tout aussi efficacement en choisissant un nombre aléatoire et en le 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 supporter que 0..MAX_INT, donc vous pouvez avoir besoin de 2 BitSets - un pour les numéros +'ve et un pour les numéros -'ve - mais les exigences de mémoire ne changent pas.

14
répondu dty 2011-08-23 01:22:20
la source

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 tout 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. Désavantage: 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. Il pourrait même vous obtenir une récompense pour "le pire abus des règles".

12
répondu vsz 2015-10-25 15:37:50
la source

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

La Théorie

étant donné n'importe quelle gamme 0 basée d'entiers qui a 2^n les éléments avec un élément manquant, vous pouvez trouver cet élément manquant par simplement xor-ing les valeurs connues ensemble 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 modèle de bit de:

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

maintenant, si on regarde, chaque bit est réglé exactement deux fois. Par conséquent, puisqu'il est fixé un nombre pair de fois, et exclusif-ou des nombres donnera 0. Si un le nombre simple est manquant, l'exclusif-ou donnera un nombre que lorsque exclusif-ored avec le nombre manquant aura pour résultat 0. Par conséquent, le nombre manquant, et le nombre exclusif-ored 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 où chaque bit est défini dans n , x et le nombre de fois où chaque bit est défini dans n+1 y . La valeur de y sera égale à y = x * 2 parce qu'il y a des éléments x avec le bit n+1 mis à 0, et des éléments x avec le bit n+1 mis à 1. Et puisque 2x sera toujours Pair, n+1 aura toujours chaque bit mis un nombre pair de fois.

donc, depuis n=2 works, et n+1 works, la méthode xor fonctionnera pour toutes les valeurs de n>=2 .

L'Algorithme De 0 Basée Sur Des Plages

c'est assez simple. Il utilise 2 * N bits de mémoire, donc pour toute plage < = 32, les entiers de 2 32 bits fonctionneront (ignorant toute mémoire consommée par le descripteur de fichier). Et ça 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 Arbitraire Basée Sur Des Plages

cet algorithme fonctionnera pour les plages de n'importe quel nombre de départ à n'importe quel nombre de fin, aussi longtemps que la plage totale est égale à 2 ^ N... Cela permet de baser la gamme pour avoir le minimum à 0. Mais il faut 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;

Arbitraire Des Plages

nous pouvons appliquer cette méthode modifiée à un ensemble de plages arbitraires, puisque toutes les plages croisent une puissance de 2^n au moins une fois. Cela ne fonctionne que si il y a un seul morceau. Il faut 2 passages d'un fichier non trié, mais il trouvera le numéro unique manquant à 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;

essentiellement, re-bases La gamme autour de 0. Ensuite, il compte le nombre de ménagères de valeurs à ajouter qu'il calcule le ou-exclusif. Ensuite, il ajoute 1 au nombre de valeurs non triées pour s'occuper de la valeur manquante (compter la valeur manquante). Puis, 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 alors re-basé à la base d'origine. Faire.

Voici l'algorithme que j'ai testé en PHP (en utilisant un tableau au lieu d'un fichier, mais le 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 gamme de valeurs (j'ai testé y compris négatifs) avec un à l'intérieur de cette gamme qui est manquant, il a trouvé la valeur correcte à chaque fois.

Une Autre Approche

puisque nous pouvons utiliser le tri externe, pourquoi ne pas simplement vérifier un trou? 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;
9
répondu ircmaxell 2011-11-02 16:27:00
la source

Vérifiez la taille du fichier d'entrée, puis sortie n'importe quel nombre qui est trop grand pour être représenté par un fichier de cette taille. cela peut sembler être une astuce bon marché, mais c'est une solution créative à un problème d'interview, il évite soigneusement la question de la mémoire, et il 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 écrire 10 bitcount - 1 , qui sera toujours plus grand que 2 bitcount . Techniquement, le nombre que vous devez battre est 2 bitcount - (4 * 10 9 - 1) , puisque vous savez qu'il y a (4 milliards - 1) d'autres entiers dans le fichier, et même avec une compression parfaite, ils prendront au moins un peu chacun.

9
répondu Justin Morgan 2018-06-08 21:22:53
la source

question piège, à moins qu'elle n'ait été mal Citée. Il suffit de lire le fichier une fois pour obtenir l'entier maximum n , et de retourner n+1 .

bien sûr, vous avez besoin d'un plan de sauvegarde au cas où n+1 provoque un débordement d'entier.

8
répondu Mark Ransom 2011-08-23 01:37:48
la source
  • la méthode la plus simple consiste à trouver le nombre minimum dans le fichier et à en retourner un de moins. Ceci utilise le stockage O(1), et le temps O(n) pour un fichier de n nombres. Cependant, il échouera si la plage de nombres 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 fait appel au temps et à l'entreposage.

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

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

8
répondu James Waldby - jwpat7 2017-05-23 13:31:14
la source

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

Lire le premier numéro. Mettez-le à gauche jusqu'à ce que vous ayez 4 milliards de bits. Si le premier bit (de haut ordre) est 0, sortie 1; sinon sortie 0. (Vous n'avez pas vraiment à gauche-pad: vous venez de sortir un 1 s'il n'y a pas assez de bits dans le nombre.) Faire la même chose avec le second nombre, sauf utiliser son second bit. Continuer à travers le fichier dans de cette façon. Vous aurez une sortie de 4 milliards de bits un bit à la fois, et ce nombre ne sera pas le même que dans le fichier. Preuve: il était le même que le nième nombre, puis ils seraient d'accord sur le nième bit, mais ils ne le font pas par la construction.

7
répondu Jonathan Amsterdam 2011-08-24 18:49:07
la source

vous pouvez utiliser des drapeaux de bits pour marquer si un entier est présent ou non.

après avoir traversé tout le fichier, 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 dans 1 Go de RAM si le marquage de bit est fait.

6
répondu Shamim Hafiz 2011-08-23 01:18:40
la source

juste par souci d'exhaustivité, voici une autre solution très simple, qui sera très probablement très longue à exécuter, mais utilise très peu de mémoire.

laisser tous les entiers possibles être la gamme de int_min à int_max , et bool isNotInFile(integer) une fonction qui retourne true si le fichier ne contient pas un certain nombre entier et false autrement (en comparant ce certain nombre entier avec chaque entier dans le fichier)

for (integer i = int_min; i <= int_max; ++i)
{
    if (isNotInFile(i)) {
        return i;
    }
}
6
répondu deg 2011-08-27 11:35:35
la source

Pour les 10 MO de mémoire contrainte:

  1. convertissez le nombre en sa représentation binaire.
  2. crée un arbre binaire où left = 0 et right = 1.
  3. insérer chaque nombre dans l'arbre en utilisant sa représentation binaire.
  4. si un nombre a déjà été inséré, les leafs auront déjà été créés.

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

4 milliards nombre = 2^32, ce qui signifie 10 MB pourrait ne pas être suffisant.

MODIFIER

une optimisation est possible, si deux feuilles d'extrémité ont été créées et ont un parent commun, alors ils peuvent être enlevés et le parent signalé comme non une solution. Cela coupe les branches et réduit le besoin de mémoire.

EDIT II

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

5
répondu Jérôme Verstrynge 2011-08-23 22:25:03
la source

rayer du fichier l'espace blanc et les caractères non numériques et ajouter 1. Votre fichier contient maintenant un seul numéro n'est pas répertorié dans le fichier d'origine.

de Reddit by Carbonetc.

5
répondu Ashley 2011-08-24 16:39:39
la source

je vais répondre à la version 1 GB:

il n'y a pas assez d'information dans la question, donc je vais é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;
    }
}
5
répondu BobTurbo 2011-08-27 11:33:54
la source

Élimination De Bits

une façon est d'éliminer les bits, mais cela pourrait ne pas réellement produire un résultat (les chances sont qu'il ne sera pas). Psuedocode:

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

Compte

garder la trace du nombre de bits; et utiliser les bits avec le moins de montants pour générer une valeur. De nouveau, cela n'a aucune garantie de générer une valeur correcte.

gamme La logique de

garder la trace d'une liste de gammes ordonnées (ordonnées par start). Une gamme 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 courante. Cette méthode n'a aucune garantie de mémoire, mais elle devrait plutôt bien fonctionner.

4
répondu Jonathan Dickinson 2011-08-23 16:26:37
la source

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

utilisez le programme de tri externe pour trier numériquement le fichier d'entrée. Cela fonctionnera pour n'importe quelle quantité de mémoire que vous pouvez avoir (il utilisera le fichier de stockage si nécessaire). Lisez le fichier trié et produisez le premier nombre qui manque.

4
répondu Rhialto 2013-07-12 23:38:35
la source

2 128*10 18 + 1 ( qui est (2 8 ) 16*10 18 + 1 ) - ne peut-elle pas être une réponse universelle pour aujourd'hui? Cela représente un nombre qui ne peut pas être tenu dans le fichier EB 16, qui est la taille maximale de fichier dans n'importe quel système de fichier courant.

3
répondu Michael Sagalovich 2011-08-24 13:57:39
la source

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 parce qu'il pourrait être demandé:

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

lancer un total courant à zéro, et pour chaque entier dans le fichier, ajouter cet entier avec un débordement de 32 bits (en fait, runningTotal = (runningTotal + nextInteger) % 4294967296). Une fois terminé, ajouter 4294967296/2 au total courant, encore une fois avec un débordement de 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 d'exécution, 32 à lire dans l'entier suivant).

corollaire: la spécification plus générale est extrêmement simple à faire correspondre si nous ne sommes pas concernés par combien de bits le résultat entier doit avoir. Nous générons juste un entier assez grand qu'il ne peut pas être contenu dans le fichier que nous sommes donnés. Encore une fois, cela prend RAM absolument minimal. Voir le pseudo-code.

# 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";
  }
}
3
répondu Syntaera 2011-08-24 14:48:46
la source

comme Ryan l'a dit essentiellement, trier le fichier et puis passer en revue les entiers et quand une valeur est sautée là vous l'avez:)

" EDIT à downvoters: L'OP a mentionné que le fichier pourrait être trié de sorte qu'il s'agit d'une méthode valide.

3
répondu ratchet freak 2011-08-27 11:28:33
la source

si vous ne supposez pas la contrainte de 32 bits, retournez simplement un nombre de 64 bits généré au hasard (ou 128 bits si vous êtes un pessimiste). Le risque de collision est de 1 in 2^64/(4*10^9) = 4611686018.4 (environ 1 sur 4 milliards). Vous avez raison la plupart du temps!

(une Blague... genre de.)

2
répondu Peter Gibson 2011-08-27 11:34:42
la source

Autres questions sur algorithm