zwei listen vergleichen und unterschiede anzeigen

[asdfghjklöä]

hallo,

ich habe zwei listen mit objekten von der klasse class1. die liste sei hier mit liste1 und liste2 gekenzeichnet. die objekte in der liste also der klasse class1 sind wie folgt aufgebaut:

string | string | string | int | long | string

die lsiten sind unsortiert.

ich möchte jetzt gerne wissen wie ich herausfinde welche objekte aus der liste1 noch nicht in der liste2 sind.

ich hatte mir überlegt einen hashwert über die jeweiligen objekte der liste1 und liste2 zu erstellen und dann mit einer for schleife zu schauen ob jeweils ein objekt aus der liste1 schon in liste2 vorhanden ist. dazu müsste ich aber jedesmal für jedes objekt aus der liste1 ein vergleich mit allen objekten der liste2 machen.

da gibt es doch bestimmt schon etwas in java oder ratiopharm 🙂. was performant ist und einfach umzusetzten.

welche möglichkeiten habe ich?

grüeß und danke asdfghjklöä

 

[Templon]

Ich würde die equals Methode überschreiben (http://java.sun.com/j2se/1.4.2/docs/api/java/lang/Object.html#equals(java.lang.Object). Danach kannst du über eine Liste iterieren und dann mit list2.contains(element) überprüfen ob es in der anderen Liste dieses Objekt schon gibt.

 

[diggaa1984]

reden wir hier von listen im Sinne des Collection-Interfaces?

dann geht vielleicht sowas:

Collection<class1> list1 = new ...();
Collection<class1> list2 = new ...();

<elemente einfügen und was nicht alles>

// was aus liste 1 ist nicht in liste 2 enthalten?
Collection<class1> tempList = new ..();
tempList.addAll(list1); //kopie von liste 1, eventuell keine tiefe Kopie!?
tempList.removeAll(list2); //alles was in Liste 2 ist raushaun, tempList enthält nun alles aus 1 was nicht in 2 ist

danach hast du weiterhin liste 1 und 2 wie vor der Überprüfung rumliegen, also nichts geändert an der Menge

 

[0x7F800000]

hmm, naja, wenn die listen länger sind, und auf der menge der Elemente eine sinnvolle Ordnung definiert werden kann, dann solltest du das tun und die Listen sortieren, dann kannst du die Listen nämlich in linearer zeit miteinander vergleichen, das ist eben um eine größenordnung schneller, als in O(n²) auf unsortierten Listen herumzusuchen oder da irgendwelche elemente daraus zu entfernen.

Wenn du zwei aufsteigend sortierte listen A und B hast, dann gehst du so vor:

-erstelle eine neue Liste C. in dieser werden elemente von A\B gespeichert.
-setze "aktuelle zeiger" auf 0 0 in beiden listen, du fängst also mit der betrachtung der kleinsten elemente an
solange elemente da sind:
-siehe das aktuelle element a der Liste A an
-siehe das aktuelle element b der Liste B an
-vergleiche a und b
  -sind sie gleich, dann kommen sie in beiden listen drin vor
  -ist a<b dann füge a in C ein, erhöhe den zeiger der Liste A
  -ist a>b dann erhöhe den zeiger der Liste B
-wenn ein zeiger null wird, dann füge die restlichen Elemente der Liste A in C ein und gebe C zurück
 (kann man sich sparen, wenn die elemente in A zuerst ausgegangen sind, dann kann man direkt C ausgeben)

Wie du siehst, erhöht man so in jedem schritt entweder den einen oder den anderen zeiger, die worst case-laufzeit ist dann O(|A|log(|A|))+O(|B|log(|B|))+O(|A|+|B|)~O(n log(n)) < O(n^2)

in code kriegst du das hoffentlich schon irgendwie umgeschrieben, 😉 ich bin grad ein wenig unter zeitdruck :roll: