Étant donné un fichier contenant 4,30 milliards d'entiers 32 bits, comment pouvons-nous trouver un nombre apparu au moins deux fois?

Question

J'ai mis au point un algorithme de division et de conquête pour cela. Je voulais juste savoir si cela fonctionnerait ou non?

La première mi est calculée à partir de la plage de nombres entiers ie (0+ (1 < < 32-1)) >> 1, puis cette idée est appliquée: plage de nombre de début à mi ou du milieu à la fin sera toujours moins que les nombres que nous allons considérer comme nous considérons des nombres de milliard et il y aura certainement quelques nombres qui vont être répétés pendant que la gamme de 32bit entier est beaucoup plus petite comparée aux nombres de milliard.

def get_duplicate(input, start, end): 
    while True: 
    mid = (start >> 1) + end - (end >> 1) 
    less_to_mid = 0 
    more_to_mid = 0 
    equal_to_mid = 0 
    for data in input: 
     data = int(data, 16) 
     if data < mid: 
      less_to_mid += 1 
     elif data == mid: 
      equal_to_mid += 1 
     else: 
      more_to_mid += 1 
    if equal_to_mid > 1: 
     return mid 
    elif mid-start < less_to_mid: 
     end = mid-1 
    elif end-mid < more_to_mid: 
     start = mid+1 

with open("codes\output.txt", 'r+') as f: 
    content = f.read().split() 
    print(get_duplicate(content, 0, 1<<32-1)) 

Je sais que nous pouvons utiliser le tableau de bits, mais je veux juste avoir votre avis sur cette solution et si la mise en œuvre est buggy.

Answer 1

Votre méthode est OK. Mais vous aurez probablement besoin de lire l'entrée plusieurs fois pour trouver la réponse.

Voici une variante, qui vous permet de trouver un doublon avec peu de mémoire, mais il vous suffit de lire l'entrée deux fois.

1. Initialiser un tableau A[65536] d'entiers à zéro.
2. Lire les numéros un par un. Chaque fois qu'un numéro x est lu, ajoutez 1 à A[x mod 65536].
3. Lorsque la lecture se termine, il doit y avoir au moins un i tel que A[i] soit strictement supérieur à 65536. C'est parce que 65536 * 63356 < 4.3 billion. Disons A[i0] est plus grand que 65536. Videz le tableau A à zéro.
4. Relisez les numéros, mais cette fois-ci, ne regardez que les numéros x tels que x mod 65536 = i0. Pour chacun de ces x, ajoutez 1 à A[x/65536].
5. Lorsque la lecture se termine, il doit y avoir au moins un j tel que A[j] soit strictement supérieur à 1. Ensuite, le numéro 65536 * j + i0 est la réponse finale.

Answer 2

La mémoire de 2^32 bits n'a rien de spécial pour les systèmes modernes. Donc, vous devez utiliser bitset, cette structure de données ne nécessite qu'un peu par numéro et toutes les langues modernes ont une implémentation. Voici l'idée - vous vous souvenez juste si un nombre a déjà été vu:

void print_twice_seen (Iterator &it)//iterates through all numbers 
{ 
    std::bitset< (1L<<32) > seen;//bitset for 2^32 elements, assume 64bit system 

    while(it.hasNext()){ 
     unsigned int val=it.next();//return current element and move the iterator 
     if(seen[val]) 
      std::cout<<"Seen at least twice: "<<val<<std::endl; 
     else 
      seen.set(val, true);//remember as seen 
    } 
}