sortieren einer Liste in Java (schwerer als es klingt!)

[registrierter Gast]

Hallo,

ich versuche in Java eine ArrayList zu sortieren. Dies allein ist mit der Collections.sort()-Methode kein Problem. Man muss lediglich einen geeigneten Comparator für z.B. Integer-Werte definieren.
Collections.sort(liste, new Comparator() {
public int compare(Object o1, Object o2) {
Object obj1 = ((ArrayList) o1).get(0);
Object obj2 = ((ArrayList) o2).get(0);
return -((Integer) obj2).compareTo((Integer) obj1);
}
}


Mein Problem hierbei ist, daß in der Liste eine weitere Liste steckt und nicht nur ein Integer.
Die Liste soll nun nach dem x-ten Element der inneren Liste sortiert werden. Mein Glück dabei ist, daß jedes x-te Element garantiert immer vom gleichen Objekt sein wird.
Allerdings verlangt die .compareTo-Methode einen Cast, der leider erst bei Ausführung des Programmes feststeht.
Hatte an folgenden Weg gedacht:
Man bestimme zuerst die Klasse des x-ten Elements. 'Erstelle' daraus ein Klasse und instanziere die zwei zu vergleichenden Objekte mit dieser Klasse, um diese dann miteinander zu vergleichen.
Leider verlangt er noch immer einen Cast. :(
Collections.sort(liste, new Comparator() {
public int compare(Object o1, Object o2) {
Integer x = 2;
String str = ((ArrayList) o1).get(x).getClass().getSimpleName();
Class cls = null;
try { cls = Class.forName(str); } catch (Exception e) {}
Object obj1, obj2;
try { obj1 = cls.newInstance(); obj2 = cls.newInstance(); } catch (Exception e) {}
obj1 = ((ArrayList) o1).get(x);
obj2 = ((ArrayList) o2).get(x);
return -(obj2).compareTo(obj1);
}
}

Wie könnte man das hinbekommen?

gruß,
gereggter Gast

[Monger]

Kleiner Tipp: nur Objekte mit einer natürlichen Ordnung lassen sich sortieren.

Soll heißen: momentan hast du ganz offensichtlich eine Datenstruktur, die sich nicht linear sortieren lässt. Also musst du daraus eine Struktur machen, die sortierbar ist.

Mach eine neue Klasse (je nach Gebrauch auch eine innere), implementier das "iterable" Interface, und sorge intern von dem Ding dafür, dass beim iterieren von A nach B du dich im richtigen Eintrag in der richtigen Liste befindest. Danach kannst du deine Liste ganz bequem mit "Collections.sort(liste)" sortieren. Als Vorbild kannst du dir ja die bereits existierenden Listen wie z.B. Arraylist nutzen. Die machen es ja auch nicht anders. Alternativ kannst du dir auch irgendwas schreiben, was ein Arraylist in der richtigen Reihenfolge mit deinen Elementen füllt, das kannst du dann auch sortieren.

Wenn deine Datenstruktur aus Elementen besteht die nicht vergleichbar sind, musst du für die auch noch das Comparable Interface erfüllen, aber wenn das nur Integer Objekte sind, sollte das kein Problem sein.
Und wenn du Java 5.0 nutzst, dann mach es doch mit den Generics noch gleich ein bißchen typsicherer.

[registrierter Gast]

Die Objekte in der inneren Liste werden lediglich vom Typ String, Integer und Double sein, also alles Objekte die bereits eine natürliche Ordnung haben.
Nun weiß ich nicht, was mir die neue Klasse mit dem 'iterable'-Interface bringen soll. Iterieren kann er doch bereits zwischen den einzelnen inneren Listen. :redface: ;(
z.B. sortiert er die Liste (bestehend aus einer Liste, wo das erste Element ein Integer ist und das zweite Element ein String) nach dem ersten Element der inneren Liste bereits so wie es sein soll. Bei diesem Test wußte ich ja, daß das erste Element ein Integer ist und konnte den Cast entsprechend setzen.

Alternativ kannst du dir auch irgendwas schreiben, was ein Arraylist in der richtigen Reihenfolge mit deinen Elementen füllt, das kannst du dann auch sortieren.Danach fehlt doch ebenso der Cast im Comparator. Nur weil denn alle String-Elemente in der inneren Liste hintereinander stehen, weiß die sort-Methode doch immernoch nicht, wonach man sortieren muss.



edit:
Mal folgendes Beispiel zur näheren Erläuterung.
äußere Liste: {innere Liste 1, innere Liste 2, innere Liste 3};

innere Liste 1: {3, "Hans"}
innere Liste 2: {7, "Dirk"}
innere Liste 3: {1, "Theodor"}


Sortiere ich nun nach dem ersten Wert der inneren Liste (Cast auf Integer gesetzt), kommt heraus:
{1, "Theodor"}, {3, "Hans"}, {7, "Dirk"}


Sortiere ich nun nach dem zweiten Wert der inneren Liste (Cast auf String gesetzt), kommt heraus:
{7, "Dirk"}, {3, "Hans"}, {1, "Theodor"}



Nun kann es während der Laufzeit aber geschehen, daß die inneren Listen folgenden Aufbau haben:
{String, Double, Double}

edit2:
Es hat sich ein weiteres Problem aufgetan. Er weiß nicht, wie er Null-Werte zu sortieren hat. :frown:

[Monger]

Verstehe ich das jetzt richtig, dass deine Listen aus lauter unterschiedlichen Datentypen bestehen? Als erst z:b. ein String, dann ein Double, dann wieder ein String, dann ein Integer...

Hmm... sehr ungewöhnlich. Ich weiß noch nicht ob das in deine Richtung geht, aber wie wäre folgender Ansatz:


class Thingy implements Comparable<Thingy>{

String name;
Integer value;
Double anotherValue;

public int compareTo(Thingy object){
return this.name.compareTo(object.name);
}
}
}

Das ist jetzt ein ganz normales, vergleichbares Objekt. Und jedes mal wenn du einen anderen Comparator brauchst, überlädst du ihn mit einer neuen compareTo Methode:


Thingy thing = new Thingy(){
public int compareTo(Thingy object){
return this.value - object.value;
}


Wenn du jetzt Objekte mit verschiedenen Überladungen mischst, kann das natürlich ganz fürchterlich in die Hose gehen.

Allgemein würde ich sagen: wenn du mehrere Objekte in einer Liste hast, die wirklich rein gar nichts miteinander zu tun haben, stellt sich die Frage warum du sie in der selben Liste verwalten willst.

[registrierter Gast]

Verstehe ich das jetzt richtig, dass deine Listen aus lauter unterschiedlichen Datentypen bestehen? Als erst z:b. ein String, dann ein Double, dann wieder ein String, dann ein Integer...Exakt :), es handelt sich dabei um die Ergebnisse verschiedener Datenbankabfragen (je nach Klick des Nutzers).

Allgemein würde ich sagen: wenn du mehrere Objekte in einer Liste hast, die wirklich rein gar nichts miteinander zu tun haben, stellt sich die Frage warum du sie in der selben Liste verwalten willst.Sie haben ja etwas miteinander zu tun. Es ist wie in einem Telefonbuch. Die Person 'Hans' hat die Durchwahl '3', der 'Theodor' aber die Durchwahl '1'.
Nun möchte ich es ermöglichen, daß sowohl nach Personennamen (String), als auch Durchwahl (Integer) sortiert wird, ohne jetzt für jede eventuell mal mögliche Datenbankabfrage einen eigenen Comparator zu schreiben, wenn doch einfach nur entsprechend gecastet werden müßte. :)

[Der_Donnervogel]

Wie wärs mit Introspektion?

Was in der Art:

String test = "lalala";
//Integer test = 1;
Object obj = test;

if ((obj.getClass().getName()).compareTo("java.lang.String") == 0) {
String temp = (String)obj;
System.out.println("String: " + temp);
} else if ((obj.getClass().getName()).compareTo("java.lang.Integer") == 0) {
Integer temp = (Integer)obj;
System.out.println("Integer: " + temp);
}
System.out.println(obj.getClass().getName());


Ist zwar nicht ganz sauber gemacht, da so nur schon bekannte Typen verarbeitet werden, aber ich hoffe die Idee ist rübergekommen.

edit:

Irgendwie kann man das auch noch dynamisch gestalten, ich glaube mit .cast(), müßte ich erst nachschalgen. Die java-Doku hilft sicher weiter.

[Xmas]

Warum nicht mit Generics? Dann prüfst du eben nach welcher Typ in der gesuchten Spalte vorliegt, und wenn es beispielsweise ein String in der dritten Spalte ist:
Collections.sort(liste, new MyComparator<String>(2));

Ungetestet (und wahrscheinlich falsch):

public class MyComparator<T extends Comparable> implements Comparator {
protected int column;

public MyComparator(int col) {
column = col;
}
public int compare(Object o1, Object o2) {
T obj1 = (T)((ArrayList) o1).get(column);
T obj2 = (T)((ArrayList) o2).get(column);
return obj1.compareTo(obj2);
}
}

[registrierter Gast]

Wie wärs mit Introspektion?

Ist zwar nicht ganz sauber gemacht, da so nur schon bekannte Typen verarbeitet werden, aber ich hoffe die Idee ist rübergekommen.

edit:

Irgendwie kann man das auch noch dynamisch gestalten, ich glaube mit .cast(), müßte ich erst nachschalgen. Die java-Doku hilft sicher weiter.Genau diesen Weg habe ich ja versucht zu gehen. Man kann den Objekttyp ohne weiteres feststellen (=> man erhält einen String mit dem Namen des Objekttyps) und wollte diesen dann bei der Compare-Methode als Cast angeben. Nur akzeptiert dieser keine Strings. Habe es denn umständlich mit Instanzierung und Reflexion versucht, was ebenfalls nicht funktionierte.


Aber...
Warum nicht mit Generics? Dann prüfst du eben nach welcher Typ in der gesuchten Spalte vorliegt, und wenn es beispielsweise ein String in der dritten Spalte ist:
Collections.sort(liste, new MyComparator<String>(2));

Ungetestet (und wahrscheinlich falsch):

public class MyComparator<T extends Comparable> implements Comparator {
protected int column;

public MyComparator(int col) {
column = col;
}
public int compare(Object o1, Object o2) {
T obj1 = (T)((ArrayList) o1).get(column);
T obj2 = (T)((ArrayList) o2).get(column);
return obj1.compareTo(obj2);
}
}
...dies hat hervorragend funktioniert. :smile: :smile: :smile:
Habe noch nie Generics (selbst) benutzt (kenne nur ein paar Leute, die dies getan haben) und ist ja wirklich simpel.
Ein ganz großes Danke an Xmas und sein Gehirn. :rolleyes:


Allerdings muss ich noch etwas an dem 'Null'-Problem basteln.
edit:
Auch solved, kann closed werden. :smile:

[HellHorse]

Ungetestet (und wahrscheinlich falsch):
Mehr als suboptimal, ist ja praktisch 1.4. Besonders hässlich ist der cast nach ArrayList!
Keine Ahnung ob ich es besser hinbekomme, aber gib mir mal einen Moment.

[registrierter Gast]

Mehr als suboptimal, ist ja praktisch 1.4. Besonders hässlich ist der cast nach ArrayList!
Keine Ahnung ob ich es besser hinbekomme, aber gib mir mal einen Moment.Ohh, bitte noch net schliessen. Vielleicht hat HellHorse ein größeres Gehirn. :biggrin:
Allerdings hatte 1.4 noch keine Generics. :uponder: Was könnte man statt dem Cast auf ArrayList verwenden?

[HellHorse]

Mein Vorschlag:
public class IndexComparator implements Comparator <List<? extends Comparable>> {
private int column;

public IndexComparator(int col) {
this.column = col;
}

public int compare(List<? extends Comparable> firstList, List<? extends Comparable> secondList) {
Comparable firstItem = firstList.get(this.column);
Comparable secondItem = secondList.get(this.column);
return firstItem.compareTo(secondItem);
}
}
Noch nicht perfekt, aber ich arbeite noch daran. ;)

[Xmas]

Aua, darauf gleich Comparable zu nehmen hätte ich auch kommen können :redface:
Ich weiß allerdings nicht ob die generische List<> hier auch erwünscht ist.

[registrierter Gast]

HellHorses Vorschlag verstehe ich nicht ganz. Es funktioniert (wenn ich List zu ArrayList umändere, anders ließ es sich nicht kompilieren), aber es übersteigt doch etwas mein Wissen. :|
Letztendlich wird doch nur im Methoden-Kopf schon auf die Liste gecastet? :confused:

[HellHorse]

Ich weiß allerdings nicht ob die generische List<> hier auch erwünscht ist.
Wieso, man hat sowieso nie einen statischen Typ ArrayList und verwendet ja nur #get(int)?
HellHorses Vorschlag verstehe ich nicht ganz. Es funktioniert (wenn ich List zu ArrayList umändere, anders ließ es sich nicht kompilieren), aber es übersteigt doch etwas mein Wissen. :|
Letztendlich wird doch nur im Methoden-Kopf schon auf die Liste gecastet? :confused:
Eigentlich ist meine Lösung auch recht scheisse, denn sie wirft immer noch eine unchecked cast Warnug. Habs nicht besser hinbekommen, sorry :redface:
Frag einfach den Nächsten der Generics cool findet oder eröffne einen Programmierwettbewerb ;)
Gecastet wird eigentlich nur im Hintergrund. Was gemacht wird, ist dass dem Compiler sehr viel mehr statische Typinformation mitgegeben wird. Und zwar sagen wir dem Compiler, dass wir nur Listen von Items vergleichen, die sich vergleichen lassen :ugly:. Wenn ich mehr darauf hätte, hätte ich es geschafft, dem Compiler mitzuteilen, dass wir nur Listen von Items vergleichen, die sich miteinander vergleichen lassen.

Wegen dem compilieren, also bei mir funktionier das:
public static void typeTest() {
ArrayList<ArrayList<Date>> list = null;
Collections.sort(list, new IndexComparator(5));
}

Edit:
Ich könnte eigentlich mal im Java Forum bei Sun nachfragen .... :D

[Xmas]

Wieso, man hat sowieso nie einen statischen Typ ArrayList und verwendet ja nur #get(int)?
Der registrierte Gast hat, soweit ich das sehe, nicht angegeben wo genau die Listen herkommen. Und ein Objekt das List<Object> implementiert kann doch nicht einfach als List<? extends Comparable> übergeben werden, oder irre ich da?

[HellHorse]

Update: Ich habs :uhippie:
public class IndexComparator<T extends Comparable<? super T>>
implements Comparator<List<T>> {

private int column;

public IndexComparator(int col) {
this.column = col;
}

public int compare(List<T> firstList, List<T> secondList) {
T firstItem = firstList.get(this.column);
T secondItem = secondList.get(this.column);
return firstItem.compareTo(secondItem);
}

public static void typeTest() {
ArrayList<ArrayList<Date>> list = null;
Comparator<List<Date>> comp = new IndexComparator<Date>(5);
Collections.sort(list, comp);
}
}
kompiliert ohne Warnungen!!!!1111eiself :ubigboy:

[HellHorse]

Der registrierte Gast hat, soweit ich das sehe, nicht angegeben wo genau die Listen herkommen. Und ein Objekt das List<Object> implementiert kann doch nicht einfach als List<? extends Comparable> übergeben werden, oder irre ich da?
Ja das stimmt aber, das hat erstens nichts mit List <-> ArrayList zu tun und zweitens können wir in diesem Fall unseren Comparator sowieso nicht verwenden. List<MySuperTypeThatImplementsComparable> ginge hingegen schon.

[Xmas]

Ja das stimmt aber, das hat erstens nichts mit List <-> ArrayList zu tun und zweitens können wir in diesem Fall unseren Comparator sowieso nicht verwenden. List<MySuperTypeThatImplementsComparable> ginge hingegen schon.
Erstens habe ich auch gar nicht von ArrayList geschrieben und zweitens ist das doch genau das was ich sage, dass man deinen Comparator nicht verwenden kann wenn die Liste eben nicht List<? extends Comparable> implementiert. Das könnte eben ein Problem sein weil wir nicht wissen wo die Listen herkommen.

[Monger]

Erstens habe ich auch gar nicht von ArrayList geschrieben und zweitens ist das doch genau das was ich sage, dass man deinen Comparator nicht verwenden kann wenn die Liste eben nicht List<? extends Comparable> implementiert. Das könnte eben ein Problem sein weil wir nicht wissen wo die Listen herkommen.

Jetzt komme ich nicht mehr mit...
Meinst du eine Liste die Comparable implementiert, oder die Einträge einer Liste die Comparable implementieren ?!?

Im letzteren Fall geht es ja ohnehin nicht. Wenn du Elemente hast die sich in keine natürliche Reihenfolge bringen lassen, kannst du sie auch nicht sortieren - egal in welcher Art von Liste.

[Xmas]

Wenn du eine List<Object> hast dann weißt du nicht ob die Objekte in der Liste Comparable implementieren oder nicht. Und weil im Eingangsposting ArrayList verwendet wurde, ist es wohl möglich dass die vorliegenden Listen nicht kompatibel zu List<? extends Comparable> sind.

[Monger]

Wenn du eine List<Object> hast dann weißt du nicht ob die Objekte in der Liste Comparable implementieren oder nicht. Und weil im Eingangsposting ArrayList verwendet wurde, ist es wohl möglich dass die vorliegenden Listen nicht kompatibel zu List<? extends Comparable> sind.
Klar, aber wo ist das Problem? Objekte die sich nicht sortieren lassen, lassen sich nunmal nicht sortieren - egal in welcher Liste und egal mit welchem Algorithmus. Sobald die Liste über ein Objekt iteriert was sich nicht vergleichen lässt, wirft sie eine Exception.

[Xmas]

Klar, aber wo ist das Problem? Objekte die sich nicht sortieren lassen, lassen sich nunmal nicht sortieren - egal in welcher Liste und egal mit welchem Algorithmus. Sobald die Liste über ein Objekt iteriert was sich nicht vergleichen lässt, wirft sie eine Exception.
Das Problem, zumindest wie ich es sehe, und ich bin kein Java-Experte, ist dass HellHorses Code keine List<Object> akzeptiert, selbst dann nicht wenn diese Liste in der Tat nur Objekte beinhaltet die Comparable implementieren.

[HellHorse]

Das Problem, zumindest wie ich es sehe, und ich bin kein Java-Experte, ist dass HellHorses Code keine List<Object> akzeptiert, selbst dann nicht wenn diese Liste in der Tat nur Objekte beinhaltet die Comparable implementieren.
Das stimmt, das ist halt statische Typsierung. Genauso wie ich einer Methode mit einem Parameter vom Typ Comparable nichts vom statischen Typ Object übergeben kann auch wenn der dynamische Typ Comparable ist.
Aber:
Glaube ich nicht, dass irgend jemand mit List<Object> arbeitet. Die sinnvollen Anwendungen dafür sind aus meiner Sicht sehr limitiert. Solange man mit einem konkreten Typ arbeitet, muss man halt schauen, dass der Comparable implementiert. Das sollte ja kein grosses Problem sein, schliesslich müssen die dynamischen Typen es ja sowieso implementieren. Falls der variert (man will ihn für List<Integer> und List<String> verwenden, kann man den Code ja auch mit generics schreiben und so immer weiter delegieren.
Selbst exterm heterogene Listen (Integer, Float, String, Date) gehen in der Praxis nur, an einem bestimmten Index bloss Instanzen der gleichen Klasse sind. Auch stellt sich hier die Frage, ob man nicht gleich eine Klasse statt einer Liste nehmen will.

[registrierter Gast]

Update: Ich habs :uhippie:
public class IndexComparator<T extends Comparable<? super T>>
implements Comparator<List<T>> {

private int column;

public IndexComparator(int col) {
this.column = col;
}

public int compare(List<T> firstList, List<T> secondList) {
T firstItem = firstList.get(this.column);
T secondItem = secondList.get(this.column);
return firstItem.compareTo(secondItem);
}

public static void typeTest() {
ArrayList<ArrayList<Date>> list = null;
Comparator<List<Date>> comp = new IndexComparator<Date>(5);
Collections.sort(list, comp);
}
}
kompiliert ohne Warnungen!!!!1111eiself :ubigboy:Danke, sortiert super. :smile:

Allerdings gibt es bei mir diese generics Parameter-Warnungen in Eclipse, wenn ich es in mein Programm einbinde. Aber nicht weiter wild. :)