Duplikate aus Liste entfernen

[jfkoernjf]

Hallo,
ich hatte jetzt schon öfters das Problem, dass ich eine Liste von Objekten habe, die ich von Duplikaten befreien wollte. Das ganze soll natürlich möglichst schick, schnell und elegant gehen.

Stellt euch vor ich habe eine Liste von Personen, die alle einen Vor- und Nachnamen haben.
Jetzt möchte ich jede Person nur einmal in meiner Liste haben.

Bis hier ist es für mich noch ganz klar- einfach ein Set nehmen, equals und hashCode in der Klasse überschreiben und dann mit addAll() hinzufügen.

So jetzt kommts:
Stellt euch vor ich möchte jetzt für jede Familie nur eine Person haben (den Sinn klammern wir jetzt mal aus). Was ist der schönste Weg eine List<Person> jetzt von den lästigen anderen Familienmitgliedern zu befreien?
Am liebsten wäre mir hier sowas wie ein Comparator, den ich für diese eine Operation anwenden kann- aber das gibts sicher nicht oder?

Mir fällt jetzt nur der umständliche Weg hier ein:
- Set<String> für alle Familiennamen erzeugen
- jedes Element in der Liste durchgehen und prüfen, ob der Name im Set vorhanden ist wenn nein hinzufügen und Element in meine Zielliste kopieren

Ich hatte noch die andere Idee von Person eine Klasse abzuleiten und der dann einen eigenen equals() und hashCode zu spendieren- aber irgendwie bin ich mir hier auch unsicher, ob das so schick ist. Um Schreibarbeit zu sparen könnte man hier ja eine anonyme Klasse verwenden.

Also mir gehts nur um schönen Programmierstil.
Wie würdet ihrs machen?

 

[Xeonkryptos]

Könntest du nicht einfach eine eigene add-Methode schreibe, die vor dem Hinzufügen prüft, ob dieser Name schon vorhanden ist und ihn erst bei nicht auffinden übergibt? Das wäre wohl die einfachste Variante.

 

[jfkoernjf]

Helf mir mal- wie würdest du das genau machen?
Ich müsste ja in der Add-Methode die ganze Liste durchgehen und in jedes einzelne Objekt hineinschauen und nen String-Vergleich machen.
Ist das bei großen Listen nicht sehr langsam? Oder verstehe ich Dich falsch?

 

[Xeonkryptos]

Im Grunde ja, oder du ersparst dir das einfach und prüfst mit der contains-Methode von der ArrayList bzw List allgemein. 🙂

Edit: contains

 

[nillehammer]

Ich müsste ja in der Add-Methode die ganze Liste durchgehen und in jedes einzelne Objekt hineinschauen und nen String-Vergleich machen.
Ist das bei großen Listen nicht sehr langsam? Oder verstehe ich Dich falsch?

Genau das ist der Weg. Wenn Du Dir den Quellcode von z.B. contains() in ArrayList anschaust, machen die auch nix anderes als die komplette Liste durchzuiterieren. Listen sind eben für den Zugriff über Index gemacht. Optimierte Zugriffe bspw. mittels Hash oder über einen Tree können die leider nicht.

 

[jfkoernjf]

Nein so einfach gehts denke ich nicht. Contains geht auf equals und hashcode (jetzt habe ich wieder Vor und Nachnamen).
Übrigens- wenn contains gehen würde, dann könnte ich auch ein Set nehmen 🙂

 

[SlaterB]

ein Set mit intelligenter Implementierung, etwa funktionieren Hash-Werten + HashSet, wäre in jedem Fall schneller als in der Liste zu prüfen,
ob man das später macht oder gleich beim Einfügen, ist da zweitrangig

bei Liste kann gerade noch Sortierung vom ärgsten quadratischen Aufwand auf n log n senken, das Set ist im Idealfall linear schnell

 

[bygones]

Reden wir hier von zwei unterschiedlichen Anforderungen ?

wenn nicht versteh ich nicht was genau das problem ist

Bis hier ist es für mich noch ganz klar- einfach ein Set nehmen, equals und hashCode in der Klasse überschreiben und dann mit addAll() hinzufügen

du schreibst selbst, per equals / hashCode kannst du dein Set manipulieren. Wenn du nun nur eine Person einer Familie haben willst passe deine equals/hashCode an.

 

[Marco13]

Das Problem dürfte/könnte sein, dass man üblicherweise zwei Personen ("Hans Müller" und "Anne Müller") NICHT als equals ansehen will - und nur für diesen zweck eine equals/hashCode zu schreiben, die sich ansonsten "falsch" verhält, geht eben nicht.

Wenn es nur EIN Kriterium ist, nach dem die "Gleichheit" entschieden werden sollte, könnte man einfach sowas machen wie

        Map<String, Person> map = new LinkedHashMap<String, Person>();
        for (Person p : input)
        {
            map.put(p.getFirst(), p);
        }
        List<Person> output = new ArrayList<Person>(map.values());

Bei mehreren Kriterien könnte man einen ähnlichen Ansatz verwenden, aber statt 'String' for den Key eben sowas verwenden wie
new PersonID(person)
und bei PersonID dann die relevanten Sachen aus der Person rausholen und in einer dort implementierten equals/hashCode passend verwursten.

 

[jfkoernjf]

Genau so wies Marco verstanden hat, habe ich es gemeint. 🙂
Die equals-Methode in der Klasse Person wollte ich nicht anfassen, da ich ja nur an einer Stelle die Duplikate entfernen möchte. An einer anderen Stelle sind Anne Müller und Peter Müller natürlich unterschiedliche Personen.

Die Frage ist jetzt, ob die for-Schleife wie Marco sie gezeigt hat wirklich die schnellste und einfachste Möglichkeit ist, die Duplikate zu entfernen - sie funktioniert ja so ähnlich wie die, die ich zu Beginn erwähnt habe. Gerade bei Reports oder anderen Übersichten, wo Daten zusammengefasst werden müssen, habe ich bis jetzt solche Konstrukte immer wieder schreiben müssen.

Warum gibt es eigentlich kein Objekt, in dem ich equals und HashCode definierenkann? Dieses Objekt könnte ich dann einem Set mitgeben und gut ist. Beim Comparator geht das doch analog mit compareTo auch?

 

[Marco13]

Ja, mit einer leicht "funktionalen" Anhauchung könnte man SEHR vieles (speziell auch, aber nicht nur in den Collections-Klassen) SEHR viel eleganter und allgemeingültiger machen. Gibt's aber erstmal nicht. Damit muss man entweder leben, oder man schreibt es sich selbst. Da kann man beliebig weit gehen um dann bei Functional Java zu landen, oder man schreibt sich was spezielles für den konkreten Fall selbst .

class FunctionalHashSet<T> implements Set<T>
{
    public FunctionalHashSet(UnaryFunction<T, Integer> hashFunction, BinaryFunction<T,T,Boolean> equality) 
    {
        ...
    }
}

Und los 🙂


EDIT: Hey, ich glaube, das wäre gar nicht sooo aufwändig...?! Bei Gelegenheit mal schauen :reflect:

 

[...ButAlive]

Ich würde das mit Comparator und TreeSet machen. Das sieht dann so aus:

Person.java

package person;

public class Person
{
	private final String vorname;
	private final String nachname;
	
	public Person(String vorname, String nachname)
	{
		this.vorname = vorname;
		this.nachname = nachname;
	}
	
	public String getNachname()
	{
		return nachname;
	}
	
	public String getVorname()
	{
		return vorname;
	}
	
	@Override
	public String toString()
	{
		return vorname+" "+nachname;
	}
}

PersonenComparator.java

package person;

import java.util.Comparator;

public class PersonComparator
	implements Comparator<Person>
{
	@Override
	public int compare(Person o1, Person o2)
	{
		return o1.getNachname().compareTo(o2.getNachname());
	}
}

PersonenTest.java

package person;

import java.util.Arrays;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

public class PersonenTest
{
	public static void main(String[] args)
	{
		Person p1 = new Person("Hans", "Meier");
		Person p2 = new Person("Hans", "Müller");
		Person p3 = new Person("Erna", "Müller");
		
		List<Person> personenList = Arrays.asList(p1,p2,p3);
		
		PersonComparator personenComperator = new PersonComparator();
		Set<Person> personenSet = new TreeSet<Person>(personenComperator);
		personenSet.addAll(personenList);
		
		for (Person person : personenSet)
		{
			System.out.println(person);
		}		
	}
}

 

[Marco13]

Ja, das ist die einfache Lösung, aber ... nicht die sicherste. Ein Comparator für eine SortedSet sollte "consistent with equals" sein, wie hier beschrieben: Comparator (Java Platform SE 6) - Der dort beschriebene Fall leuchtet ein, trifft aber auf dieses Beispiel nicht zu - und zugegeben: Ich habe gerade mal versucht, diese TreeMap "richtig kaputt" zu machen, aber es nicht geschafft. Trotzdem kann durch sowas ein Verhalten entstehen, das von der Spezifikation abweicht und viel Verwirrung stiftet: In deinem Fall würde für
personenSet.contains(p3)
noch 'true' zurückgegeben, aber der Eintrag ist gar nicht vorhanden... Es könnte "immer" funktionieren, aber letztendlich hängt es wohl von der Implementierung von TreeSet ab...

 

[jfkoernjf]

Ahh- jetzt geht die Diskussion in die richtige Richtung 🙂

Ist schon blöd, dass man für solche einfache Dinge redundanten Code schreiben muss.
Oder sich umständlich was bauen soll.

@Marco: Danke für den Link- habe von Functional Java noch nichts gehört- werde ich mir mal anschauen.
Auch wenn ich wahrscheinlich bei meiner for-Schleife bleiben werde 🙂

@ButAlive: Die Idee mit dem Comparator war gut- leider hat sie mir Marco madig geredet :-D

 

[...ButAlive]

Natürlich hat Marco13 recht wenn er mich auf die Java-API verweißt, aber sein Vorschlag verstößt genauso gegen den Vertrag von Set, denn da steht:

More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element.

java.util.Set

Aber so eng würde ich dass nicht sehen. Bei meinem Vorschlag du bist halt dann auf TreeSet festgelegt, kannst nicht einfach gegen Set programmieren und beliebig die Implementierung austauschen. Bei Marco13 gilt das gleiche nur für FunctionalHashSet.

Ich würde das wahrscheinlich so verpacken:

public List<Person> filter(List<Person> personen)
{
        PersonComparator personenComperator = new PersonComparator();
        TreeSet<Person> personenSet = new TreeSet<Person>(personenComperator);
        personenSet.addAll(personen);
        List<Person> result = new ArrayList<Person>(personenSet);
        return result.
}

Dann hätte man dieses Problem zentriert und würde außerhalb mit einer List<Person> arbeiten.

Wenn man sich streng an die API halten will, gefällt mir Marco13s Vorschlag mit der Map am besten.

 

[...ButAlive]

Natürlich hat Marco13 recht wenn er mich auf die Java-API verweißt, aber sein Vorschlag verstößt genauso gegen den Vertrag von Set, denn da steht:

More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element.

java.util.Set

Aber so eng würde ich dass nicht sehen. Bei meinem Vorschlag du bist halt dann auf TreeSet festgelegt, kannst nicht einfach gegen Set programmieren und beliebig die Implementierung austauschen. Bei Marco13 gilt das gleiche nur für FunctionalHashSet.

Ich würde das wahrscheinlich so verpacken:

public List<Person> filter(List<Person> personen)
{
        PersonComparator personenComperator = new PersonComparator();
        TreeSet<Person> personenSet = new TreeSet<Person>(personenComperator);
        personenSet.addAll(personen);
        List<Person> result = new ArrayList<Person>(personenSet);
        return result.
}

Dann hätte man dieses Problem zentriert und würde außerhalb mit einer List<Person> arbeiten.

Wenn man sich streng an die API halten will, gefällt mir Marco13s Vorschlag mit der Map am besten.

 

[Marco13]

Bei meinem Vorschlagt könnte man das "implements Set<T>" einfach weglassen 😀

Ich stimme dem, was du zuletzt gesagt hast, bedingt zu: Wenn man das NUR als kleine "Hilfsfunktion" verwendet

private /* !!! */ List<T> compute(List<T> input)
{
    List<T> output = doSomethingThatViolatesContracts();
    return output;
}

ist so eine Verletzung vielleicht nicht so schlimm. Das "kritische" daran ist, dass in der nächsten Java-Version vielleicht jemand eine Optimierung von TreeSet baut, die garantiert funktioniert, wenn man sich an die API-Spec hält - aber in diesem Fall würde es das mit dem Comparator vielleicht raushauen, mit Fehlern die man vielleicht erst zu spät bemerkt, und vor allem SEHR schwer aufspüren kann... Es ist einfach heikel... :bahnhof: