Alternativa al lazo anidado para comparación

Question

Actualmente estoy escribiendo un programa que necesita comparar cada archivo en un ArrayList de tamaño variable. En este momento, la forma en que estoy haciendo esto es a través de un código de bucle anidado:

  if(tempList.size()>1){ 
      for(int i=0;i<=tempList.size()-1;i++) 
       //Nested loops. I should feel dirty? 
       for(int j=i+1;j<=tempList.size()-1;j++){ 
        //*Gets sorted. 
        System.out.println(checkBytes(tempList.get(i), tempList.get(j))); 
       } 
      } 

He leído algunas opiniones divergentes sobre la necesidad de bucles anidados, y me preguntaba si alguien tenía una alternativa más eficiente .

A primera vista, cada comparación va a tener que hacer, de cualquier manera, por lo que el rendimiento debe ser bastante estable, pero estoy convencido de moderadamente hay una forma más limpia de hacer esto. ¿Alguna sugerencia?

EDIT :: Esta es solo una parte de la función, para mayor claridad. Los archivos han sido comparados y puestos en cubos en función de la longitud: después de recorrer el mapa del conjunto y encontrar un depósito que es mayor que uno, lo ejecuta. Entonces, estos son todos archivos del mismo tamaño. Haré una comparación de suma de comprobación antes de llegar a los bytes también, pero ahora mismo estoy tratando de limpiar el ciclo.

Además, holy cow este sitio responde rápido. Gracias chicos.

EDIT2 :: Lo siento, para mayor aclaración: Creo que la parte de manejo de archivos que tengo una buena comprensión, primero, la comparo y ordeno por longitud, luego por suma de comprobación, luego por bytes, el problema que tengo es cómo lidiar adecuadamente con la necesidad de comparar todos los archivos en el ArrayList de manera eficiente, suponiendo que todos deben ser comparados. Si un ciclo anidado es suficiente para esto, es genial, solo quería comprobar que este era un método adecuado, según la convención.

Answer 1

Mi respuesta a su pregunta Edit2 consta de dos partes

La parte es que si usted tiene un pequeño número de archivos, entonces su enfoque de bucle anidado debe estar bien. El rendimiento es O(N**2) y la solución óptima es O(N). Sin embargo, si N es lo suficientemente pequeño, no tendrá mucha importancia el enfoque que use. Solo necesita considerar una solución alternativa si está seguro de que N puede ser grande.

La segunda parte detalla un algoritmo que explota hashes de archivos para obtener una solución O(N) para detectar duplicados. Esto es a lo que se refieren las respuestas anteriores.

1. Cree una clase FileHash para representar los valores hash de archivo. Esto necesita definir los métodos equals(Object) y hashCode() que implementan la igualdad por bytes de los valores hash de archivos.

2. Crea una instancia de mapa HashMap<FileHash, List<File>>.

3. Para cada File en su entrada ArrayList:

   1. Calcular el hash del archivo y crear un objeto FileHash por ello.
   2. de búsqueda de la FileHash en el mapa:
   3. Si encuentra una entrada, realice una comparación byte a byte del archivo actual con cada uno de los archivos de la lista que ha recibido del mapa. Si encuentra un archivo duplicado en la lista, ¡BINGO! De lo contrario, agregue el archivo actual a la lista.
   4. Si no encuentra una entrada, crear una nueva entrada de mapa con el "FileHash` como la clave y el archivo actual como el primer elemento de la lista de valores.

(Nota que el mapa de arriba es realmente un mapa múltiple, y que hay implementaciones de terceros disponibles, por ejemplo, en las colecciones comunes de Apache y en las colecciones de Google.He presentado el algoritmo en el formulario anterior en aras de la simplicidad)

algunos problemas de rendimiento:.

• Si utiliza una buena función hash criptográfica para generar sus hash de archivo, entonces las posibilidades de encontrar una entrada en 3.3 que tiene más de un elemento en la lista es infinitamente pequeña, y las posibilidades de que la comparación byte-wise de los archivos no diga que los archivos son iguales también son muy pequeñas. Sin embargo, el costo de calcular el hash criptográfico será mayor que el costo de calcular un hash de menor calidad.

• Si usted hace uso de un hash de menor calidad, que pueden mitigar el costo potencial de la comparación de más archivos al mirar los tamaños de los archivos antes de hacer la comparación byte a byte. Si lo hace, puede hacer que el tipo de mapa HashMap<FileHash, List<FileTuple>> donde FileTuple sea una clase que contenga tanto un File como su longitud.

• Usted puede disminuir potencialmente el coste de hash mediante el uso de un hash de (digamos) el primer bloque de cada archivo. Pero eso aumenta la probabilidad de que dos archivos tengan el mismo hash pero sigan siendo diferentes; p.ej. en el 2 ° bloque Si esto es significativo depende de la naturaleza de los archivos. (Pero por ejemplo si sólo suma de comprobación de los primeros 256 bytes de una colección de archivos de código fuente, se puede obtener un gran número de colisiones ... debido a la presencia de las cabeceras de los derechos de autor idénticos!)

Answer 2

Comparando todo con todo lo demás, debe ser O (n²). Pero hay trucos que puedes probar. El principal es hacer comparaciones más baratas; esto se puede hacer generando un código hash para cada archivo y comparando los primeros, lo que al menos evitará la mayoría de las comparaciones (utilice un algoritmo lo suficientemente bueno y evitará prácticamente todas). También puede acelerar las cosas si no necesita retener información sobre qué archivos son iguales; produzca un Set de hashcodes de cada archivo y en la prueba final para ver si el tamaño del conjunto es el mismo que el tamaño de la lista de archivos.

Answer 3

Una buena optimización sería calcular primero todos los valores hash de los archivos y luego hacer un solo bucle sobre la lista.

Esto básicamente porque tendrás que verificar cada par de archivos de tu lista, pero esto implicará solo una complejidad O (1) para cada par en lugar de calcular un montón de cosas para cada uno que vas a comprobar.

Puede ser algo como:

HashSet<YourFile> fileSet = new HashSet<YourFile>(); 
ArrayList<YourFile> files = new ArrayList<YourFile>(); 

class YourFile 
{ 
    int hashcode = -1; 

    public int hashCode() 
    { 
    // override it to provide an hashcode based on file contents 
    // you can also cache it to avoid recalculating anything 

    if (hashcode == -1) 
     hashcode = calculateIt(); 

    return hashcode; 
    } 
} 

// fill up files 
files.add(...); 

// do comparisons 
for (YourFile f : files) 
{ 
    if (fileSet.contains(f)) 
    // f and fileSet.get(f) are equal: this is a tricky utilization of the hashCode() method so be careful about it! 
    else 
    { 
    fileSet.put(f); 
    // since there's not a file with same hashcode you just add this one 
    } 
} 

En realidad, esto se reducirá el bucle interno, ya que cuando se utiliza hashSet.contains se comprobará todos los archivos ya agregados, pero con un O (1) la complejidad.

Según lo indicado en doublep, debe tener cuidado con las interpretaciones, ya que cuando simplemente comprueba los bytes, se detendrá tan pronto como encuentre dos bytes diferentes mientras calcula el hash y tendrá que comprobar todo el archivo. Esto funcionará bien cuando tenga muchos archivos o cuando el archivo sea bastante pequeño. Lo mejor que puede hacer es comparar ambos enfoques y ver si hay diferencias notables.

Answer 4

Según lo que esté haciendo exactamente, puede obtener una aceleración considerable al no comparar nunca archivos de diferentes tamaños. Entre los archivos del mismo tamaño, compare solo aquellos con el mismo hash (por cualquier algoritmo), como se sugiere en otras respuestas.

EDIT:

Calculando el hash puede ser conunterproductive, sin embargo. Primero, nunca lo haga si compara el archivo solo entre sí: necesita leer el archivo completamente para crear un hash, y una lectura ya es suficiente para comparar, de modo que no obtendrá nada.

En segundo lugar, si rara vez espera una coincidencia y los archivos difieren considerablemente (desde el principio), el cálculo del hash puede ser contraproducente independientemente del número de archivos para comparar. Esto se debe a que la comparación fallida en una situación de este tipo fallará temprano (es decir, no leerá todo el archivo), mientras que para una creación de hash necesitará una lectura completa. Alternativamente, puede compilar hash "parcial" (por ejemplo, un hash de los primeros 10 kb de un archivo), pero luego recuerde usar partes iguales de todos los archivos.

Answer 5

Una pequeña limpieza sería eliminar la prueba de tamaño inicial: si el tamaño es inferior a 2, simplemente se caerá sin haber hecho ninguna comparación. Una mejor adherencia a las convenciones de codificación de Java sería, en los bucles, para comparar i < tempList.size() en lugar de i <= tempList.size() - 1 - eso simplemente hará que su código sea más fácil de entender para otros programadores. Ninguno de estos cambios tiene ningún impacto en el rendimiento.

for (int i = 0; i < tempList.size(); i++) 
    for (int j = i + 1; j < tempList.size(); j++) { 
     //*Gets sorted. 
     System.out.println(checkBytes(tempList.get(i), tempList.get(j))); 
    }