Comparando una matriz y obteniendo la diferencia

Question

¿Cómo compararía dos matrices que podrían tener diferentes longitudes y obtendría la diferencia entre cada matriz?

Por ejemplo:

Cat cat = new Cat(); 
Dog dog = new Dog(); 
Alligator alligator = new Alligator(); 

Animal animals[] = { cat, dog }; 
Animal animals2[] = { cat, dog, alligator }; 

¿Cómo les comparar dos matrices y hacer que devolver la instancia de Alligator?

Answer 1

Yo sugeriría que su pregunta debe ser aclarada. Actualmente, todo el mundo está adivinando qué es lo que en realidad estás preguntando.

• ¿Las matrices están destinadas a representar conjuntos, listas o algo intermedio? En otras palabras, ¿importa el orden de los elementos, y puede haber duplicados?
• ¿Qué significa "igual"? ¿new Cat() "igual" new Cat()? ¡Tu ejemplo sugiere que sí!
• ¿Qué quiere decir con la "diferencia"? ¿Te refieres a establecer la diferencia?
• ¿Qué desea que suceda si las dos matrices tienen la misma longitud?
• ¿Se trata de una comparación única o se produce repetidamente para las mismas matrices?
• ¿Cuántos elementos hay en las matrices (en promedio)?
• ¿Por qué está usando matrices en absoluto?

Haciendo la suposición de que estas matrices están destinadas a ser verdaderos conjuntos, entonces probablemente debería utilizar HashSet en lugar de matrices, y el uso de las operaciones de recogida y como addAllretainAll para calcular la diferencia de conjuntos.

Por otro lado, si las matrices están destinadas a representar listas, no está del todo claro qué significa "diferencia".

Si es fundamental que el código se ejecute rápidamente, entonces seguramente necesita replantear sus estructuras de datos. Si siempre comienzas con matrices, no podrás calcular las "diferencias" rápidamente ... al menos en el caso general.

Finalmente, si va a usar algo que depende del método equals(Object) (y que incluye cualquiera de los tipos de colección Java, realmente necesita tener una idea clara de lo que se supone que significa "igual" en su aplicación . Son todos los casos Cat iguales? ¿Son todos diferentes? Son algunas Cat casos iguales y otros no? Si no resolver esto, y poner en práctica los métodos equals y hashCode consecuencia obtendrá resultados confusos.

Answer 2

Bueno, podrías usar Set y usar el método removeAll().

o puede utilizar el siguiente algoritmo simple y lento para hacer:

List<Animal> differences = new ArrayList<Animal>(); 

    for (Animal a1 : animals) { 
     boolean isInSecondArray = false; 
     for (Animal a2 : animals2) { 
      if (a1 == a2) { 
       isInSecondArray = true; 
       break; 
      } 
     } 

     if (!isInSecondArray) 
      differences.add(a1) 
    } 

Entonces differences tendrá todos los objetos que están en animals matriz, pero no en animals2 matriz. De manera similar, puede hacer lo opuesto (obtener todos los objetos que están en animals2 pero no en animals).

Answer 3

me sugieren que usted pone sus objetos en grupos y luego utiliza una intersección de los conjuntos:

// Considering you put your objects in setA and setB 

Set<Object> intersection = new HashSet<Object>(setA); 
intersection.retainAll(setB); 

Después de que se puede utilizar removeAll para obtener una diferencia de cualquiera de los dos conjuntos:

setA.removeAll(intersection); 
setB.removeAll(intersection); 

Inspirado por: http://hype-free.blogspot.com/2008/11/calculating-intersection-of-two-java.html

Answer 4

Es posible que desee ver en este artículo para obtener más información: 012

http://download-llnw.oracle.com/javase/tutorial/collections/interfaces/set.html

Como se ha mencionado, removeAll() está hecho para esto, pero tendrá que hacerlo dos veces, por lo que se puede crear una lista de todo lo que no están presentes en ambos, y entonces se podría combinar estos dos resultados a tener una lista de todas las diferencias.

Pero esta es una operación destructiva, por lo que si no quiere perder la información, copie Set y opere en esa.

ACTUALIZACIÓN:

Parece que mi suposición de lo que es en la matriz está mal, por lo removeAll() no va a funcionar, pero con un requisito de 5 ms, depeending en el número de elementos para buscar podría ser un problema.

Por lo tanto, parece que HashMap<String, Animal> sería la mejor opción, ya que es rápido en la búsqueda.

Animal es una interfaz con al menos una propiedad, String name. Para cada clase que implemente Animal escriba el código para Equals y hashCode. Puede encontrar alguna discusión aquí: http://www.ibm.com/developerworks/java/library/j-jtp05273.html. De esta forma, si quieres que el valor de hash sea una combinación del tipo de animal y el nombre, entonces eso estará bien.

Por lo tanto, el algoritmo básico es mantener todo en los hashmaps, y luego buscar diferencias, simplemente obtener una matriz de claves, y buscar para ver si esa clave está contenida en la otra lista, y si no está No lo pongas en List<Object>, almacenando el valor allí. Querrá hacer esto dos veces, por lo tanto, si tiene al menos un procesador de doble núcleo, puede obtener algún beneficio de que ambas búsquedas se realicen en hilos separados, pero luego querrá usar uno de los tipos de datos concurrentes agregado en JDK5 para que no tenga que preocuparse por las sincronizaciones en la lista combinada de diferencias.

Por lo tanto, lo escribiría primero como un solo hilo y prueba, para obtener algunas ideas sobre cuánto más rápido es, también lo comparo con la implmemntación original. Luego, si lo necesita más rápido, intente usar hilos, de nuevo, compare para ver si hay un aumento de velocidad.

Antes de realizar cualquier optimización, asegúrese de tener algunas métricas sobre lo que ya tiene, de modo que pueda comparar y ver si el único cambio conducirá a un aumento en la velocidad.

Si realiza demasiados cambios a la vez, uno puede tener una gran mejora en la velocidad, pero otros pueden llevar a una disminución del rendimiento, y no se verá, por lo que cada cambio debe ser uno a hora.

No pierda las otras implementaciones, sin embargo, usando pruebas unitarias y probando quizás 100 veces cada una, puede hacerse una idea de qué mejora le brinda cada cambio.

Answer 5

No me importa la perf de mis usos (y usted tampoco, a menos que tenga una buena razón para hacerlo, y averigua a través de su perfil que este código es el cuello de botella).

Lo que hago es similar a la respuesta funcional. Yo uso operadores de conjuntos de LINQ para obtener la excepción en cada lista:

http://msdn.microsoft.com/en-us/library/bb397894.aspx

Editar:

Lo sentimos, no me di cuenta que esto es Java. Lo siento, estoy fuera en C# la-la tierra, y se ven muy similares :)