Wie sortieren?

[jf]

Hallo, ich habe eine Klasse, welche die Klasse Vector<AbstractObj> erweitert.
Ich lege nun in dieser Klasse verschiedene Objekte ab (grob chronologisch), welche alle von AbstractObj erben. Alle diese verschiedenen Objekte besitzen einen Zeitstempel.
Nun möchte ich diesen Vector sortieren, damit eine streng chronologische Ordnung entsteht.

Dazu habe ich nun folgende Fragen:
- Welcher Sortieralgorithmus ist am geeignetsten (schnellsten) - es herrscht in der Regel eine gute Vorsortierung
- Ich würde gerne comparable implementieren. Kann ich dies in der abstrakten Klasse tun, oder muss diese in jeder Klasse, welche davon erbt einzeln erfolgen (wäre Mist, da x-mal der gleiche Code).
- Wäre es evtl. geschickter, anstatt eines Vectors eine andere sortierbare Klasse zu verwenden? (liege ich richtig, wenn ich sage, dass Vector threadsicher ist, aber List und ArrayList nicht?)

Besten Dank für eure Tipps!

 

[Landei]

Wenn nur der Zeitstempel für die Sortierung relevant ist, würde ich das Comparable-Interface in der abstrakten Klasse implementieren. Allerdings wäre ich da vorsichtig, bei gleichem Zeitstempel wäre die Reihenfolge undefiniert (eventuell könnte man noch Klassennamen und hashCode mit einbeziehen, um das zu vermeiden). equals und hashCode solltest du auch implementieren, und zwar "regelkonform".

Statt Vector würde ich eine ArrayList nehmen. Wenn du diese wirklich einmal threadsicher brauchst, kannst du immer noch einen synchronisierten Wrapper mit java.util.Collections erzeugen.

Natürlich sollte man generell eine Collection-Klasse nur erweitern, wenn man ihr Funktionalität aus "Collection-Sicht" hinzufügt (z.B. dass man einen PropertyChangeListener registrieren kann wenn sich etwas ändert), aber nicht, um "modellspezifische" Probleme zu lösen - dann ist Komposition die bessere Wahl.

Ich denke kaum, dass irgendeine eigene Implementierung den Sortieralgorithmus in Collection.sort schlagen kann, das ist ein wirklich ausgefeiltes Timsort (es sei denn, man hat zusätzliches Wissen über die Daten, z.B. dass es sehr wenige mögliche Werte gibt, wo Bucketsort und Konsorten besser abschneiden würden).

 

[tfa]

Vector ist veraltet. Ich benutze lieber ArrayList bzw. eine andere List-implementierende Klasse.
Ist es nötig, eine Unterklasse von Vector (oder was auch immer) zu bilden? Lass deine Klasse doch nur eine List<AbstractObj> benutzen, also Komposition statt Vererbung. Normalerweise fährt man damit besser.

- Welcher Sortieralgorithmus ist am geeignetsten (schnellsten) - es herrscht in der Regel eine gute Vorsortierung

Benutze einfach den in Collections.sort() implementierten. Das ist ein Merge-Sort und sollte schnell genug sein.

- Ich würde gerne comparable implementieren. Kann ich dies in der abstrakten Klasse tun, oder muss diese in jeder Klasse, welche davon erbt einzeln erfolgen (wäre Mist, da x-mal der gleiche Code).

Dann musst du es wohl in der abstrakten Klasse implementieren.
Du kannst auch selbst Comparatoren schreiben, falls du die selben Objekte nach verschiedenen Kriterien sortieren willst.

- Wäre es evtl. geschickter, anstatt eines Vectors eine andere sortierbare Klasse zu verwenden? (liege ich richtig, wenn ich sage, dass Vector threadsicher ist, aber List und ArrayList nicht?)

Ja, siehe oben. List ist ein Interface. Oft ist es sinnvoll, gegen Interfaces statt gegen konkrete Implementierungen zu programmieren.

 

[jf]

Allerdings wäre ich da vorsichtig, bei gleichem Zeitstempel wäre die Reihenfolge undefiniert

Welche Nachteile können daraus entstehen? Sind dadurch nur unterschiedliche Sortierungen für eine bestimmte Auswahl von Elementen möglich, oder funktioniert dadurch die ganze Sortierung nicht korrekt?

equals und hashCode solltest du auch implementieren, und zwar "regelkonform".

Ok, könntest du mir hierzu bitte noch etwas Hintergrundwissen geben?
Und was gibt es zu beachten, um regelkonform zu bleiben? Was sind die Nachteile, wenn man dies nicht einhält?

Statt Vector würde ich eine ArrayList nehmen. Wenn du diese wirklich einmal threadsicher brauchst, kannst du immer noch einen synchronisierten Wrapper mit java.util.Collections erzeugen.

Wie meinst du das genau?

Natürlich sollte man generell eine Collection-Klasse nur erweitern, wenn man ihr Funktionalität aus "Collection-Sicht" hinzufügt (z.B. dass man einen PropertyChangeListener registrieren kann wenn sich etwas ändert), aber nicht, um "modellspezifische" Probleme zu lösen - dann ist Komposition die bessere Wahl.

Ok, ich dachte mir, da meine Klasse ja ein Art von Container ist, dass ich gleich vererbe, um so möglichst viele Collections-Methoden ohne zusätzlichen eignen Kode erhalte.
Ich habe nun aber auch gemerkt, dass man über intellisens eine oft sehr umfangreiche Liste erhält, welche Eclipse auch schon mal eine Weile einfrieren lässt (Warum ist das überhaupt so? Kann man da etwas machen?)... Ist dies der einzige Nachteil?

 

[jf]

Vector ist veraltet.

Ok, was sind die konkreten Nachteile von Vector?

Ich benutze lieber ArrayList bzw. eine andere List-implementierende Klasse.

Ist das eine subjektive Entscheidung, oder gibt es dafür auch objektive Gründe?

Ist es nötig, eine Unterklasse von Vector (oder was auch immer) zu bilden? Lass deine Klasse doch nur eine List<AbstractObj> benutzen, also Komposition statt Vererbung. Normalerweise fährt man damit besser.

Ok. Habe ja hierzu schon auf Landeis gleiche Empfehlung etwas geschrieben.

Benutze einfach den in Collections.sort() implementierten. Das ist ein Merge-Sort und sollte schnell genug sein.

Mit Java 7 sollte es sogar ein Timsort sein.

Du kannst auch selbst Comparatoren schreiben, falls du die selben Objekte nach verschiedenen Kriterien sortieren willst.

Ok, aber eigentlich ist nur die Zeit wichtig.

Ja, siehe oben. List ist ein Interface. Oft ist es sinnvoll, gegen Interfaces statt gegen konkrete Implementierungen zu programmieren.

Wie meinst du das? - Ich will doch nicht gegen etwas programmieren...

 

[ARadauer]

Ok, was sind die konkreten Nachteile von Vector?

er ist langsamer

Ist das eine subjektive Entscheidung, oder gibt es dafür auch objektive Gründe?

nicht subjektiv, vector ist veraltelt und langsamer

Wie meinst du das? - Ich will doch nicht gegen etwas programmieren...

Das ist für einen Anfänger nicht so leicht zu verstehen. Es gibt eine Beschreibung der Schnittstelle (Interface) und konkrete Implementierungen.
List ist das Interface, ArrayList ist eine Implementierung davon.
In seinem Programm arbeitet man haupsächlich mit List, man programmiert also auf/mit/gegen (ka) die Schnittstelle.
Irgendwo in seinem Programm hat man natürlich dan die Instanzierung (new ArrayList()) der Liste. Da benutzt man schon die Konkrete Implementierung (List kann man ja nicht instazieren)
Dadurch wird man flexibler, wenn man an der Stelle an der man die ArrayList instanziert, dann eine andere Implementierung von List nimmt, muss man nicht sein gesamte Programm umschreiben, da ja eh die anderen Methoden nur List erwarten... verstanden? Nein... kann daran liegen, dass du einfach noch zu wenig Erfahrung mit dem Thema hast oder ich schlecht erklären kann

Was wären so implementierungen von List?
List (Java Platform SE 6)

 

[Landei]

Selbst im täglichen Leben "programmieren wir gegen Interfaces". Z.B gibt es keine Flachrundkopfschraube 5x20 (das "Interface"). Was es gibt, sind konkrete Schrauben eines bestimmten Herstellers, die dieser Norm entsprechen (die "Implementierung"). Gehen wir in den Laden, verlangen wir meistens nur "Flachrundkopfschraube 5x20", weil uns völlig egal ist, ob die von Schraubensepp oder Eisengustl hergestellt sind, ob sie gedreht, gegossen oder von fleißigen indischen Kinderhänden aus dem Stück gefeilt worden sind - Hauptsache sie entsprechen der Norm. Mit Listen ist es genauso: Benötigen wir keine ganz speziellen Eigenschaften einer ganz speziellen Implementierung, nehmen wir einfach "List": Damit ist klar, was das Ding können muss, aber nicht, wie es intern aufgebaut ist. Damit sichern wir uns ein Stück Unabhängigkeit: Geht Eisengustl ein, können wir ohne Probleme zu Schraubensepp wechseln, ist Vector zu langsam, können wir ArrayList nehmen.

 

[jf]

Ok, danke ihr beiden. Das war zwar mehr scherzhaft gemeint, weil ich die Formulierung "gegen" nicht kannte, aber sinnvoll waren eure Erklärungen allemal.

ist Vector zu langsam, können wir ArrayList nehmen.

Ok, dann müsste aber Vector eine Implementierung des Interfaces List sein. - Ist es das, wenn es veraltet ist?
Ich habe mal gelesen, dass Vector gar nicht so viel langsamer ist. Könntet ihr den Unterschied in einer Zahl beziffern?
Gibt es threadsichere und moderne Implementierung von List? Wie würde das mit der Wrapper-Klasse laufen, welche du erwähnt hattest Landei?

 

[Gast2]

Ok, dann müsste aber Vector eine Implementierung des Interfaces List sein. - Ist es das, wenn es veraltet ist?

Ein Blick in die API sagt:

public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, Serializable

Man kann mit Sicherheit messen wie groß der Unterschied ist - aber wie gesagt: Wenn du einfach mit dem List Interface arbeitest kannst du die konkrete Implementierung einfach austauschen. Dann kannst du es in deinem Use Case selber messen - oder einfach glauben das ArayList schneller ist

 

[tfa]

Ok, dann müsste aber Vector eine Implementierung des Interfaces List sein. - Ist es das, wenn es veraltet ist?

Vector ist älter als das List-Interface, bzw. das Collection-Framework.
In der API-Doku zu Vector steht "this class was retrofitted to implement the List interface, making it a member of the Java Collections Framework." Er wurde also nachträglich in das Framework reingefrickelt. Das sieht man heute noch, denn es gibt zwei Methoden, um an die Vector-Elemente zu kommen. Einmal das alte "elementAt()" und dann aus List das neue "get()". Zwei unterschiedliche Methoden die exakt das gleiche machen sind nunmal unschön. Aber Vector gleich als Deprecated zu markieren hat man sich dann doch nicht getraut.

 

[jf]

Super, vielen Dank an alle!

Bleiben nur noch meine letzten Fragen:
* Gibt es einen modernen Ersatz für Vector, welcher threadsicher ist?
* Wie ist das mit dem Wrapper gemeint?
* Könntet ihr bitte noch einen Kommentar zu equals und hashCode abgeben? Und was bedeutet hier "regelkonform"?

 

[Landei]

* Gibt es einen modernen Ersatz für Vector, welcher threadsicher ist?

CopyOnWriteArrayList (Java 2 Platform SE 5.0)

* Wie ist das mit dem Wrapper gemeint?

java.utils.Collections hat verschiedene statische Methoden, die Collections "einpacken", um ihnen zusätzliche Eigenschaften mitzugeben, etwa unmodifiableList (macht eine Liste "read-only") oder synchronizedList (macht eine Liste threadsafe).

Generell ist ein Wrapper eine Klasse, die im Inneren eine Referenz auf ein "Original" besitzt, sich selbst ähnlich wie das Original verhält und die Aufrufe auch an dieses weiterleitet (dabei aber selbt verschiedene Operationen ausführen kann). Andere Sprachen unterstützen solche Konstruktionen direkt ("Delegation"). Ein Beispiel, wo zu einer vorhandenen Klasse Logging-Funktionalität hinzugefügt wird:

public interface Person {
   public String getName();
   public int getAge();
}

//das "Original"
public class PersonImpl implements Person {
   private final String name;
   private final int age;
   public Person(String name, int age) {
      this.name = name;
      this.age = age;
   }
   public String getName() { return name; }
   public int getAge() { return age; }
}

class PersonLogWrapper implements Person {
   private Person original;
   public PersonLogWrapper(Person original) {
       this.original = original;
   }
   public String getName() { 
      Logger.getLogger().log("Jemand will den Namen wissen");
      return original.getName(); 
   }
   public int getAge() { 
      Logger.getLogger().log("Jemand will das Alter wissen");
      return original.getAge(); 
   }
}

* Könntet ihr bitte noch einen Kommentar zu equals und hashCode abgeben? Und was bedeutet hier "regelkonform"?

"Regelkonform" bedeutet hier: Sich an die Javadoc der beiden Methoden halten.
Equals and Hash Code in Java
Galileo Computing :: Java ist auch eine Insel (8. Auflage) – 3.7 Identität und Gleichheit
Galileo Computing :: Java ist auch eine Insel (8. Auflage) – 10.2 Object ist die Mutter aller Klassen