¿Cuál es la forma más rápida de comprobar si los archivos son idénticos?

La mayoría de las personas en sus respuestas ignoran el hecho de que los archivos deben compararse repetidamente. Por lo tanto, las sumas de comprobación son más rápidas ya que la suma de comprobación se calcula una vez y se almacena en la memoria (en lugar de leer los archivos secuencialmente n veces).

Suponiendo que la expectativa es que los archivos serán los mismos (suena como que ese es el escenario), entonces tratar con sumas de verificación/hashes es una pérdida de tiempo - es probable que sean los mismos y tendría que volver a leer los archivos para obtener la prueba final (también estoy asumiendo que ya que desea "probar ... son los mismos", que tenerlos hash al mismo valor no es suficiente).

Si ese es el caso, creo que la solución propuesta por David está bastante cerca de lo que tendrías que hacer. Un par de cosas que se podrían hacer para optimizar la comparación, en el aumento del nivel de complejidad:

• compruebe si los tamaños de archivo son los mismos antes de hacer la comparación
• usa la memcmp () más rápida que puedas (comparando palabras en lugar de bytes-la mayoría de los tiempos de ejecución de C ya deberían hacer esto)
• use varios subprocesos para hacer las comparaciones de bloques de memoria (hasta el número de procesadores disponibles en el sistema, repasando eso haría que su subproceso luche con cada uno los demás)
• use E/S superpuestas / asincrónicas para mantener los canales de E/S lo más ocupados posible, pero también perfile cuidadosamente para que pueda moverse entre los archivos lo menos posible (si los archivos están divididos entre varios discos diferentes y puertos de E/S, mejor)

Actualización: No se quede atascado en el hecho de que son archivos de origen. Imagina, por ejemplo, que tomaste un millón de ejecuciones de un programa con una salida muy regulada. Desea demostrar que todas las 1.000.000 versiones de la salida son las mismas.

Si tiene control sobre la salida, haga que el programa que crea los archivos / salida cree un md5 sobre la marcha e incrustarlo en el archivo o flujo de salida o incluso canalice la salida a través de un programa que crea el md5 en el camino y lo almacena junto al datos de alguna manera, el punto es hacer los cálculos cuando los bytes ya están en memoria.

Si no puede lograr esto, entonces como otros han dicho, compruebe los tamaños de los archivos y luego haga una comparación de byte por byte en archivos del mismo tamaño, no veo cómo cualquier tipo de división binaria o cálculo md5 es mejor que una comparación directa, tendrá que tocar cada byte para demostrar la igualdad de cualquier manera que lo corte, por lo que también podría cortar la cantidad de cálculo necesario por byte y ganar la capacidad de córtalo en cuanto encuentres un error.

El cálculo md5 sería útil si planeas compararlos de nuevo más tarde con nuevas salidas, pero básicamente regresas a mi primer punto de calcular el md5 lo antes posible

Bueno, el algoritmo más óptimo dependerá del número de archivos duplicados.

Suponiendo que unos pocos son iguales pero la mayoría son diferentes y los archivos son grandes.

Filtre los que obviamente no son los mismos usando una simple comprobación de la longitud del archivo.

Elija bytes aleatorios del archivo, calcule un hash y compare (minimizando las búsquedas de disco)

Siga esto con un archivo SHA1 completo.

Hay una serie de programas que comparan un conjunto de archivos en general para encontrar otros idénticos. FDUPES es bueno: Link . Un millón de archivos no debería ser un problema, dependiendo de la naturaleza exacta de la entrada. Creo que FDUPES requiere Linux, pero hay otros programas similares para otras plataformas.

Intenté escribir un programa más rápido, pero excepto en casos especiales, FDUPES fue más rápido.

De todos modos, la idea general es empezar por comprobar los tamaños de la file. Los archivos que tienen diferentes tamaños no pueden ser iguales, por lo que solo necesita mirar grupos de archivos con el mismo tamaño. Entonces se vuelve más complicado si desea un rendimiento óptimo: Si es probable que los archivos sean diferentes, debe comparar pequeñas partes de los archivos, con la esperanza de encontrar diferencias pronto, para que no tenga que leer el resto de ellos. Sin embargo, si es probable que los archivos sean idénticos, puede ser más rápido leer cada archivo para calcular una suma de verificación, porque entonces puede leer secuencialmente desde el disco en lugar de saltar de un lado a otro entre dos o más archivos. (Esto asume discos normales, por lo que SSD: s puede ser diferente.)

En mis puntos de referencia al intentar hacer un programa más rápido (algo para mi sorpresa) resultó ser más rápido leer primero cada archivo para calcular una suma de verificación, y luego si las sumas de verificación eran iguales, comparar los archivos directamente leyendo un bloque alternativamente de cada archivo, que simplemente leer bloques alternativamente sin la suma de verificación anterior los cálculos! Resultó que al calcular las sumas de comprobación, Linux almacenaba ambos archivos en caché en la memoria principal, leyendo cada archivo secuencialmente, y las segundas lecturas eran muy rápidas. Al comenzar con lecturas alternas, los archivos no fueron leídos (físicamente) secuencialmente.

EDITAR:

Algunas personas han expresado sorpresa final incluso duda de que podría ser más rápido leer los archivos dos veces que leerlos solo una vez. Tal vez no logré explicar muy claramente lo que estaba haciendo. Soy hablando de precarga de caché, con el fin de tener los archivos en caché de disco cuando más tarde acceder a ellos de una manera que sería lento para hacer en la unidad de disco físico. Aquí es una página web donde he tratado de explicar más en detalle, con imágenes, código C y medidas.

Sin embargo, esto tiene (en el mejor de los casos) relevancia marginal para la pregunta original.

Usar cksum no es tan confiable como usar algo como md5sum. Pero yo optaría por la máxima fiabilidad, lo que significa una comparación byte-by-byte usando cmp.

Debe leer cada byte en ambos archivos para todos los métodos de comprobación, por lo que también puede optar por el que sea más confiable.

Como primera pasada, puede comprobar la lista de directorios para ver si los tamaños son diferentes. Esa es una forma rápida de obtener comentarios más rápidos para diferentes archivos.

Yo ejecutaría algo como esto

find -name \*.java -print0 | xargs -0 md5sum | sort

Luego vea qué archivos tienen diferentes sumas MD5. Esto agrupará los archivos por suma de comprobación.

Puede reemplazar md5sum que sha1sum o incluso rmd160 si lo desea.

No creo que el hashing vaya a ser más rápido que las comparaciones byte por byte. La comparación byte por byte se puede optimizar un poco al canalizar la lectura y comparación de los bytes, también se pueden comparar varias secciones del archivo en subprocesos paralelos. Sería algo como esto:

• Compruebe si los tamaños de los archivos difieren
• Leer bloques de los archivos en la memoria de forma asíncrona
• Manejarlos a hilos de trabajo para hacer las comparaciones

O simplemente ejecute un cmp (o el equivalente para su sistema operativo) en paralelo. Esto podría ser escrito fácilmente y usted todavía obtiene el beneficio del paralelismo.

Más allá de la comparación, sincronizar dos carpetas, super rápido! lo usamos todo el tiempo, todos los días.

El hash MD5 sería más rápido que la comparación, pero más lento que un CRC-check normal. Tienes que averiguar el tipo de fiabilidad que quieres en comparación.

¿Por qué reinventar la rueda? ¿Qué tal una aplicación de terceros? Por supuesto que no tiene API, pero no me imagino que poner su auto en esta situación a menudo. Me gusta esta aplicación doublekiller acaba de hacer una copia de seguridad antes de empezar. :) Es rápido y gratis!

Primero compare las longitudes de archivo de todos los millones. Si tienes una manera barata de hacerlo, comienza con los archivos más grandes. Si todos pasan eso, entonces compare cada archivo usando un patrón de división binaria; esto fallará más rápido en archivos que son similares pero no iguales. Para información sobre este método de comparación ver método Knuth-Morris-Pratt.

Acabo de escribir una aplicación de c# que hace algo similar a lo que quieres. Lo que mi código hace es esto.

Lee todos los tamaños de cada archivo en una lista o matriz.

Utilice un bucle for para comprobar si alguno de estos tamaños es el mismo. si son del mismo tamaño, compare un byte de un archivo con un byte del otro archivo. Si los dos bytes son iguales, pase al siguiente byte. Si se encuentra una diferencia, devuelva que los archivos son diferentes.

Si el final de ambos archivos es alcanzado, y los dos últimos bytes son los mismos, los archivos deben ser idénticos.

He experimentado con la comparación de hashes MD5 de archivos en lugar de pasar por byte por byte, y he encontrado que los archivos idénticos a menudo se pierden con este método, sin embargo, es significativamente más rápido.

Utilice el concepto de Filtro Bloom. Una explicación simple aquí: http://crzyjcky.com/2013/01/03/the-magical-bloom-filter /

Te da un tiempo constante de comparación. Sin embargo, este método no puede utilizarse solo. Apache Cassandra y HBase están utilizando esta técnica internamente.

Básicamente le dice a u que los archivos no son idénticos de manera muy rápida. Si dice que el archivo es idéntico, tiene que hacer otra ronda de comprobación utilizando un método confiable.

En mi opinión, esta es una operación de sistema de archivos. Así que primero, elija su sistema de archivos con cuidado. Siguiente, deduplicar. A continuación, comparar inodos. Como:

% find / -inum "$(ls -di "./test.file" | grep -E '^[0-9]*')"
<list of identical files provided in a few seconds to a minute>

Si desea comparar archivos uno por uno, utilice ExamDiff.