Le paramètre critique dans ce type de travail est le coût d'une recherche de disque individuel. Une recherche de disque a une latence innée, parce que les têtes de lecture/écriture doivent être déplacées à la bonne position. Sur un disque typique, vous pouvez compter sur une centaine de recherches par seconde. D'autre part, les disques sont très bons en lecture séquentielle, donc pour chaque recherche, vous pouvez lire, disons, un mégaoctet de données, pour un coût supplémentaire minime.
Je suppose ici que le "fichier texte" a un format régulier. Par exemple, chaque valeur de hachage utilise exactement 33 octets, 32 pour le résultat MD5 lui-même (en hexadécimal) et 1 octet supplémentaire pour un caractère "nouvelle ligne". Ajuster si nécessaire, en fonction du format exact. Avec ces chiffres, votre fichier texte a une longueur d'environ 3,3 Go. Comme MD5 agit principalement comme une fonction aléatoire, les 100 millions de hachages devraient être répartis uniformément dans l'espace des valeurs de 128 bits. Cela signifie que, étant donné une valeur de hachage, vous pouvez calculer la position approximative de cette valeur dans le fichier (s'il se trouve dans le fichier). Par exemple, la valeur de hachage 9378ec093d09863d008154f1c8f5ca8f doit être à un décalage proche de 0,5761 * n * 33, où n est le nombre de hachages dans le gros fichier et "33" est expliqué dans le paragraphe ci-dessus. 0,5761 est le résultat de 0x9378EC divisé par 0x1000000. Par conséquent, vous pouvez lire une valeur de un mégaoctet de votre fichier texte, centrée sur cette position calculée. Cela contiendra environ 30000 hachages. L'écart type pour 100 millions de valeurs aléatoires est de l'ordre de 10000, il y a donc de fortes chances que les 30000 hash contiennent les bonnes valeurs pour décider si votre hash est dans la liste ou non. Si l'estimation était désactivée, vous devrez lire un autre mégaoctet, mais cela n'arrivera pas souvent. Vous pourriez peut-être lire un peu plus d'un mégaoctet pour rendre cette occurrence rare: il y a un compromis, qui doit être ajusté par des mesures réelles. Une fois que vous avez un (petit) bloc de valeurs de hachage dans la RAM, utilisez une recherche binaire. Mais le coût initial de la recherche va complètement éclipser cette partie de toute façon.
Une autre solution utilise un fichier d'index supplémentaire. Construire un fichier secondaire qui contient un tous les 10000 hachages dans le gros fichier. Ce fichier aura une longueur d'environ 330 Ko. Gardez ce fichier dans la RAM autant que possible. Utilisez-le (avec une recherche binaire) pour savoir quelle séquence de 10000 hachages est pertinente pour votre recherche. Ensuite, lisez ce morceau du gros fichier.Le fichier d'index doit être reconstruit chaque fois que la liste des hachages est modifiée; C'est plutôt cher, mais moins que le gros changement de fichier. Selon le système qui produit le gros fichier, vous pouvez peut-être intégrer la génération du fichier d'index pour un coût supplémentaire négligeable.
+1 mieux que ce que j'allais suggérer (une hashtable de hachages définissant le point de départ et de fin de chaque segment pour permettre la recherche juste dans un ou deux segments). Bien qu'une recherche binaire de l'ensemble fonctionne, votre implémentation a l'avantage de réduire la portée de l'espace de recherche à <1% de l'ensemble. Très belle implémentation. –
Voilà une réponse intéressante. Je ne suis pas certain de le suivre, pensez-vous pouvoir poster des diagrammes à un moment donné pour l'illustrer? Ou au moins expliquer votre division de 0x1000000 un peu plus? – Ian
@Ian: Je prends les six premiers hexdigits de la valeur de hachage (six est quelque peu arbitraire, vous pouvez en prendre plus). Ils vont de 0x000000 à 0xFFFFFF; c'est une plage de longueur 16777216, qui est 0x1000000 en hexadécimal. 0x9378EC est à la position 57,61% dans cette gamme. –