Quel est le moyen le plus rapide de vérifier si les fichiers sont identiques?

Question

Si vous avez 1,000,0000 fichiers source, vous pensez qu'ils sont tous les mêmes, et que vous voulez comparer, ce qui est le courant à jeun méthode pour comparer ces fichiers? Supposons qu'ils sont les fichiers Java et de la plateforme où la comparaison est faite n'est pas important. cksum est de me faire pleurer. Quand je veux dire identiques je veux dire, TOUTES identiques.

Mise à jour: - je savoir sur la génération de sommes de contrôle. diff est risible ... je veux de la vitesse.

Mise à jour: Ne restez pas coincé sur le fait qu'ils sont des fichiers source. Prétendre par exemple que vous avez pris un million de pistes d'un programme avec de très réglementé de sortie. Vous voulez prouver à tous les 1 000 000 de versions de la sortie sont les mêmes.

Mise à jour: lire le nombre de blocs plutôt qu'en octets? Immédiatement jeter ceux-là? Est que plus rapide que de trouver le nombre d'octets?

Mise à jour: Est-ce si différent de la façon la plus rapide pour comparer deux fichiers?

Answer 1

J'avais opter pour quelque chose comme l'approche adoptée par l' cmp programme: ouvrir deux fichiers (dire le fichier 1 et le fichier 2), lire un bloc de chacune, et de les comparer, octet par octet. Si elles correspondent, de lire le prochain bloc de chacun, de les comparer octet-par-octet, etc. Si vous arrivez à la fin de ces deux fichiers sans détecter d'éventuelles différences, de retourner au début du fichier 1, fermer le fichier 2 et ouvrir le fichier 3 à sa place, et répétez jusqu'à ce que vous avez vérifié tous les fichiers. Je ne pense pas qu'il existe un moyen d'éviter de lire tous les octets de tous les fichiers s'ils sont tous identiques, mais je pense que cette approche est (ou proche de) la façon la plus rapide de détecter toute différence qui pourrait exister.

Modification de l'OP: Levé important commentaire de Marque de Bessey

"une autre optimisation évidente si les fichiers sont censés être la plupart du temps identiques, et s'ils sont relativement petits, est de garder l'un des fichiers entièrement en mémoire. Qui coupe bas sur l'écroulement d'essayer de lire les deux fichiers à la fois."

Answer 2

La plupart des gens dans leurs réponses ignorent le fait que les fichiers doivent être comparés à plusieurs reprises. Ainsi, les sommes de contrôle sont plus rapides car elles sont calculées une fois et stockées en mémoire (au lieu de lire les fichiers séquentiellement n fois).

Answer 3

En supposant que l'espoir est que les fichiers sont les mêmes (ce que le scénario), puis traiter avec les sommes de contrôle/hachages est une perte de temps - il est probable qu'ils vont être la même et que vous auriez à re-lire les fichiers pour obtenir la preuve finale (je suis aussi en supposant que, puisque vous voulez pour "prouver ... ce sont les mêmes", ont eux hachage à la même valeur n'est pas assez bon).

Si c'est le cas, je pense que la solution proposée par David est assez proche de ce que vous devez faire. Un couple de choses qui peut être fait pour optimiser la comparaison, une augmentation du niveau de complexité:

• vérifier si les tailles des fichiers sont les mêmes avant de faire la comparaison
• utiliser de la manière la plus rapide memcmp() que vous pouvez (en comparant les mots au lieu d'octets plus C temps de fonctionnement devrait le faire déjà)
• l'utilisation de plusieurs threads pour faire le bloc de mémoire compare (jusqu'au nombre de processeurs disponibles sur le système, en allant sur qui serait la cause de votre fils à se battre les uns les autres)
• l'utilisation se chevauchent/asynchronous I/O pour garder les canaux I/O aussi occupé que possible, mais aussi attentivement le profil de sorte que vous thrash entre les fichiers aussi peu que possible (si les fichiers sont répartis entre plusieurs disques et des ports d'e/S, d'autant mieux)

Answer 4

Eh bien, l'algorithme le plus optimal dépendra du nombre de fichiers en double.

En supposant que quelques-uns sont identiques, mais la plupart sont différents et les fichiers sont volumineux.

Filtrez ceux qui ne sont évidemment pas les mêmes en utilisant une simple vérification de la longueur du fichier.

Choisissez des octets aléatoires dans le fichier, calculez un hachage et comparez (minimisation des recherches de disque)

Suivez cela avec un fichier complet SHA1.