Déterminez si un très grand tableau contient un doublon

Question

Pour un tableau de taille normale, nous pouvons déterminer s'il contient des doublons en triant ou en utilisant hashset, etc. Mais si nous avons un très grand tableau, disons que la longueur est de 10 milliards, comment Pouvons-nous déterminer s'il contient des doublons? Suivi: si nous savons qu'il doit exister un doublon dans ce grand tableau, comment pourrions-nous déterminer lequel est-il?

Mon idée utilise le tri, mais je ne sais pas s'il existe une meilleure façon de gérer ces situations.

Answer 1

D'abord, placez vos données dans des compartiments K avec un code comme celui-ci.

files = array of K file handles 
for each d in data { 
    write d to files[hash(d) % K] 
} 
close each file 

Si vous choisissez K assez grand, chaque godet peut facilement entrer dans la RAM. Assurez-vous de choisir une bonne fonction de hachage, sinon les seaux seront déséquilibrés. Le code réel dépendra également du système de stockage que vous utilisez. Par exemple, si vous utilisez un disque dur ordinaire, les recherches coûtent cher et il faut faire attention à ne pas écraser le disque. Une approche possible consisterait à lire autant de données que possible dans la RAM, puis à les parcourir à intervalles réguliers, en les ajoutant à un seul des fichiers de sortie de chaque passage.

Ensuite, il suffit de parcourir chaque compartiment à tour de rôle et de voir s'il contient des doublons. Vous pouvez utiliser n'importe quel algorithme efficace pour détecter les doublons. Une solution alternative consisterait à utiliser un map-reduce framework.

L'étape de carte ressemblera à ceci:

map(value) { 
    emit(key=hash(value), value=value) 
} 

Et la réduction étape ressemblera à ceci:

reduce(key, values) { 
    if there's a duplicate in values { 
     emit the duplicate value. 
    } 
} 

Notez que chaque réducteur ne voir plusieurs valeurs quand il y a un double, ou quand il y a des collisions de hachage. Si vous avez choisi une fonction de hachage raisonnable, celle-ci sera extrêmement rare.