Eigenen Comparator schreiben ?

[redbomber]

Hi zusammen:

Ich habe eine Frage, bzw. vielmehr ein Problem.

Ich besitze eine LinkedList<Object> in sich Objekte befinden.
Diese Objekte besitzen eine Eigenschaft (-> z.B.: Alter), nachdem ich diese Objekte sortieren möchte.
Diser Vorgang findet nur 1 mal ganz zu Beginn statt.

Bisher erstelle ich einfach eine neue LinkedList<Object> und führe im grunde einen insertionsort aus.
Also füge ich Object für Object in die neue Liste an der passenden Stelle ein, indem ich das Alter des neu einzufügenden Objekts mit dem Alter der schon eingefügten Objekte vergleiche.
Sobald ich ein älteres Objekt finde habe ich meine Einfügeposition gefunden.

Dies klappt auch alles soweit ganz gut, die Laufzeit ist jedoch sehr schlecht (im schlechtesten Fall O(n^2)).
Dies merke ich wenn ich größere Daten einlese, dann braucht der wirklich viel zu lange um die Objekte zu sortieren.


Jetzt habe ich gehört, dass man seinen eigenen Comparator programmieren kann, welcher die Sortierung schneller durchführt. Wisst ihr wie so etwas funktioniert? Macht so etwas sinn?

Oder habt ihr mir vielleicht einen anderen Tip wie ich das Sortieren schneller gestalten kann?[/quote]

 

[Der Müde Joe]

es gibt 2 möglichkeiten zu sortieren:

Collections.sort mit dem entsprechenden Comparator.

oder eine bereits sortierende Collection und das zu sortierenden
Objekt Comparable implementieren lassen.

bei einmal würd ich den comparator wählen:

		List<Person> list = new ArrayList<Person>();
		Collections.sort(list, new Comparator<Person>() {

			@Override
			public int compare(Person o1, Person o2) {
				// oder was auch immer
				return o1.getAge() - o2.getAge();
			}
		});

	class Person {

		int getAge() {
			return 0;
		}
	}

 

[redbomber]

super vielen Dank!

Die Methode

Collections.sort(list, new Comparator<Person>() {

         @Override
         public int compare(Person o1, Person o2) {
            // oder was auch immer
            return o1.getAge() - o2.getAge();
         }
      });

Wo muss diese genau implementiert werden?
Wie bei dir in dem Beispiel an der Stelle wo ich meine sortierte Liste erzeugen möchte?

Also ich frage daher, da ich mir gerade versuche vorzustellen, woher der compiler weiss, dass diese compare Methode verwendet werden soll.

 

[Ark]

Das muss nicht der Compiler wissen, sondern die Sortiermethode, und die wiederum ist so gebaut, dass sie einen ganz konkreten Comparator erwartet und auch benutzt. Deswegen musst du einen solchen angeben (hast du ja schon getan).

Was die Implementierung betrifft: Es ist völlig egal, wo sie steht oder wo sie herkommt; Hauptsache, sie erfüllt die Schnittstellenspezifikation:

a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

Und das dürfte bei dir wohl auch der Fall sein.

Ark

 

[Murray]

Die Methode

Collections.sort(list, new Comparator<Person>() {

         @Override
         public int compare(Person o1, Person o2) {
            // oder was auch immer
            return o1.getAge() - o2.getAge();
         }
      });

Wo muss diese genau implementiert werden?

Das ist eigentlich keine Methode, sondern ein Methodenaufruf, bei dem allerdings ein Parameter eine anonymous inner class ist, in der wiederum eine Methode (nämlich compareTo) implementiert ist.

Vielleicht wird es deutlicher, wenn man für den Comparator eine lokale Variable einsetzt:

Comparator<Person> persComp = new Comparator<Person>() {

         @Override
         public int compare(Person o1, Person o2) {
            // oder was auch immer
            return o1.getAge() - o2.getAge();
         }
      };
Collections.sort(list, persComp);

 

[Der Müde Joe]

>Wo muss diese genau implementiert werden?

Der Comparator kann eine eigene Klasse sein und muss nicht eine innerer Klasse sein. Er muss lediglich die Methode compare überschreiben.

zB:

import java.util.Comparator;

public class AgeComparator implements Comparator<Person> {
	
	@Override
	public int compare(Person o1, Person o2) {
		return o1.getAge() - o2.getAge();
	}
}

>Wie bei dir in dem Beispiel an der Stelle wo ich meine sortierte Liste erzeugen möchte?

Der Aufruf von Collections.sort sortiert dann auch die Liste. Wenn du dann was addedst ist sie wieder unsortiert.

		//vergleicht Personen nach alter
		AgeComparator comp = new AgeComparator();
		
		List<Person> persons = new ArrayList<Person>();
		
		//adde ein paar Personen
		persons.add(...);
		persons.add(...);
		persons.add(...);
		
		//sortiere unsortierte List nach alter
		Collections.sort(persons, comp);
		
		// hier sind alle Personen dem Alter nach sortiert
		
		//diese Person wird wieder irgendwo in der Liste geadded (am Schluss)
		persons.add(...);

		// die Liste ist wieder unsortiert

 

[redbomber]

noch eine letzte Frage, sorry.

Angenommen bei der Eigenschaft welche ich überprüfe, handelt es sich um keine integer-Werte sondern um Werte vom Typ long.
Wie kann ich dies dann beheben?

 

[redbomber]

Habs einfach gecasted und jetzt geht alles!

Vielen Dank euch allen!
Jetzt bin ich mal gespannt ob dieser Comparator schneller sortiert als mein langsamer insertion sort

 

[0x7F800000]

Habs einfach gecasted und jetzt geht alles!

Bist du dir da so sicher? Dann schau dir bitte die ausgabe von

System.out.println((int)Long.MAX_VALUE);

an, und überlege dir, ob das nicht evtl doch schief gehen könnte

(wenn du es einfach mit

return (int)(firstLong-secondLong);

machst, wird es definitiv schief gehen)

Ferner solltest du dir im klaren sein, was die compare-methode ausgibt:

Returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

d.h. du musst da keine differenzen oder sonstigen Kram ausgeben. -1, 0, 1 als ausgabe reichen schon vollkommen.

 

[redbomber]

uiuiui :?

Habs gleich behoben.

Die Reihenfolge war zwar korrekt, aber hatte auch keine so große Werte die nicht auch als integer hätten dargestellt werden können. Daher hat es korrekt sortiert.

Jetzt mache ich aber davor die Abfrage und gebe dann entsprechend -1/0/+1 zurück.
Vielen Dank nochmal!

 

[0x7F800000]

deine alte comparator-methode kannst du nach einer kleinen modifikation immer noch zum pseudo-zufälligen durchmischen der Liste verwenden, wenn du willst