Confronto di un array e ottenere la differenza

Question

Come confrontarei due array che potrebbero avere lunghezze diverse e ottenere la differenza tra ogni array?

Ad esempio:

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

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

Come dovrei confrontarli due array e farlo ritornare l'istanza di Alligator?

Answer 1

Suggerirei di chiarire la tua domanda. Attualmente, ognuno sta indovinando cosa si sta chiedendo in realtà.

• Gli array sono progettati per rappresentare insiemi, elenchi o qualcosa in mezzo? In altre parole, l'ordine degli elementi è importante e possono esserci duplicati?
• Che cosa significa "uguale"? new Cat() "uguale" new Cat()? Il tuo esempio suggerisce che lo faccia !!
• Cosa intendi per "differenza"? Intendi differenza di set?
• Che cosa vuoi che accada se i due array hanno la stessa lunghezza?
• È un confronto una tantum o si verifica ripetutamente per gli stessi array?
• Quanti elementi ci sono negli array (in media)?
• Perché stai utilizzando gli array?

facendo l'ipotesi che questi array sono destinati ad essere veri set, allora probabilmente dovrebbe utilizzare HashSet invece di array, e l'utilizzo di operazioni di raccolta come addAll e retainAll per calcolare la differenza set.

D'altra parte, se gli array sono pensati per rappresentare elenchi, non è del tutto chiaro cosa significhi "differenza".

Se è fondamentale che il codice funzioni velocemente, è necessario ripensare le strutture dati. Se inizi sempre con gli array, non sarai in grado di calcolare le "differenze" velocemente ... almeno nel caso generale.

Infine, se si intende utilizzare qualsiasi cosa che dipende dal metodo equals(Object) (e che include qualsiasi tipo di raccolta Java, è necessario avere una chiara comprensione di cosa significa "uguale" nella propria applicazione . sono tutti Cat casi uguali? sono tutte diverse? sono alcune Cat casi uguali e altri no? Se non capire questo, e implementare le equals e hashCode metodi di conseguenza si ottengono risultati confusi.

Answer 2

Bene, è possibile utilizzare lo Set e utilizzare il metodo removeAll().

Oppure si potrebbe usare il seguente algoritmo semplice e lento per fare:

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) 
    } 

Poi differences avranno tutti gli oggetti che si trovano in animals serie, ma non in animals2 array. In un modo simile puoi fare il contrario (prendi tutti gli oggetti che sono in animals2 ma non in animals).

Answer 3

suggerisco che mettete i vostri oggetti in set e quindi utilizzare un incrocio dei set:

// Considering you put your objects in setA and setB 

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

Dopo di che è possibile utilizzare removeAll per ottenere una differenza a qualsiasi dei due set:

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

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

Answer 4

si consiglia di guardare a questo articolo per ulteriori informazioni:

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

Come si è accennato, removeAll() è fatto per questo, ma si vuole farlo due volte, in modo che è possibile creare una lista di tutti che mancano in entrambi, e allora si potrebbe combinare questi due risultati a avere una lista di tutte le differenze.

Tuttavia, questa è un'operazione distruttiva, quindi se non si desidera perdere le informazioni, copiare il Set e operare su quello.

UPDATE:

Sembra che la mia assunzione di ciò che è nella matrice è sbagliato, quindi removeAll() non funziona, ma con un requisito di 5 ms, depeending sul numero di elementi per la ricerca potrebbe essere un problema.

Quindi, sembrerebbe un HashMap<String, Animal> sarebbe l'opzione migliore, in quanto è veloce nella ricerca.

Animal è un'interfaccia con almeno una proprietà, String name. Per ogni classe che implementa il codice di scrittura Animal per Equals e hashCode. Puoi trovare qualche discussione qui: http://www.ibm.com/developerworks/java/library/j-jtp05273.html. In questo modo, se vuoi che il valore hash sia una combinazione del tipo di animale e del nome, allora andrà bene.

Quindi, l'algoritmo di base è quello di mantenere tutto nelle hashmap e quindi cercare le differenze, basta ottenere una serie di chiavi e cercare attraverso per vedere se quella chiave è contenuta nell'altra lista, e se non è inseriscilo in un List<Object>, memorizzando il valore lì. Si consiglia di eseguire questa operazione due volte, quindi, se si dispone di almeno un processore dual-core, si potrebbe trarre qualche vantaggio dall'avere fatto entrambe le ricerche in thread separati, ma poi si vorrà utilizzare uno dei tipi di dati simultanei aggiunto in JDK5 in modo da non doversi preoccupare delle sincronizzazioni nell'elenco combinato delle differenze.

Quindi, vorrei scriverlo prima come un thread singolo e testare, per ottenere alcune idee su quanto è più veloce, confrontandolo anche con l'implmemntation originale. Quindi, se ne hai bisogno più velocemente, prova a utilizzare i thread, ancora una volta, confronta per vedere se c'è un aumento di velocità.

Prima di eseguire qualsiasi ottimizzazione, assicurarsi di disporre di alcune metriche su ciò che si ha già, in modo da poter confrontare e vedere se l'unica modifica porterà ad un aumento della velocità.

Se si apportano troppe modifiche alla volta, si può avere un notevole miglioramento della velocità, ma altre possono comportare una diminuzione delle prestazioni e non si vedrebbe, motivo per cui ogni modifica dovrebbe essere tempo.

Tuttavia, non perdere le altre implementazioni, utilizzando i test unitari e testare forse 100 volte ciascuno, è possibile avere un'idea di quali miglioramenti ogni cambiamento ti dà.

Answer 5

Non mi importa di perf per i miei utilizzi (e non dovresti neanche, a meno che tu non abbia una buona ragione, e scopri tramite il tuo profiler che questo codice è il collo di bottiglia).

Quello che faccio è simile alla risposta del funzionale. Io uso operatori set LINQ per ottenere l'eccezione di ciascuna lista:

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

Edit:

dispiace, non ho notato questo è Java. Scusa, vado in C# la-la land e sembrano molto simili :)