SortedCollection für Java gesucht

[HellHorse]

Ich suche folgendes:
Eine Collection (braucht nicht zwangläufig das Collection Interface zu implementieren) die

schnellen den Zugriff auf das nach einem Comparator kleinste Element bietet (alternativ geht auch compareTo()).
das erste Element sich entfernen lässt (gehört eigentlich mit obigen zusammen, kleistes ausgeben und entfernen)
mehere Elemente aufnehmen kann, die laut einem Comparator gleich sind (daher scheidet TreeSet aus)
man Elemente hinzufügen kann
immer sortiert ist, oder sich per Methodenaufruf sortieren lasst (möglichst schnell, natürlich)

Im Moment arbeite ich mit einer ArrayList, möchte aber andere Implementationen zum Vergleich.

[Xmas]

Ich würde mal vorschlagen, eine LinkedList zu kapseln, so dass add() immer sortiert einfügt. addFirst() und addLast() machen dann aber keinen Sinn mehr. Oder eine TreeMap mit Zähler, das ist dann aber etwas mehr Arbeit und vielleicht den Aufwand nicht wert.

[HellHorse]

Original geschrieben von Xmas
Ich würde mal vorschlagen, eine LinkedList zu kapseln, so dass add() immer sortiert einfügt. addFirst() und addLast() machen dann aber keinen Sinn mehr. Oder eine TreeMap mit Zähler, das ist dann aber etwas mehr Arbeit und vielleicht den Aufwand nicht wert.
Also im Moment habe ich ja eine Liste, und der Input ist sortiert (binary search abgewandelt).

Wie hast du dir das mit der TreeMap vorgestellt?
Das Problem ist, das ich die Grösse eines Elementes nicht als absolute Zahl habe. Ich kann bloss sagen, ob es grösser, kleiner oder gleich gross, als ein anderes Element ist.

[Xmas]

Original geschrieben von HellHorse
Also im Moment habe ich ja eine Liste, und der Input ist sortiert (binary search abgewandelt).

Wie hast du dir das mit der TreeMap vorgestellt?
Das Problem ist, das ich die Grösse eines Elementes nicht als absolute Zahl habe. Ich kann bloss sagen, ob es grösser, kleiner oder gleich gross, als ein anderes Element ist.
Ich glaube da habe ich dich falsch verstanden. Ich bin davon ausgegangen, dass Objekte die der Comparator als gleich angibt auch wirklich identisch sind.

LinkedList mit modifiziertem add() sollte wesentlich besser abschneiden als ArrayList, weil einfügen und entfernen wesentlich weniger Aufwand bedeuten, selbst wenn du die Einfügeposition nicht mehr per Binary Search bestimmen kannst. Sollte die Liste sehr lang werden, kannst du die Suche immer noch beschleunigen, indem du zusätzlich zu Anfang und Ende auch die Listenmitte speicherst.

[HellHorse]

Original geschrieben von Xmas
Ich glaube da habe ich dich falsch verstanden. Ich bin davon ausgegangen, dass Objekte die der Comparator als gleich angibt auch wirklich identisch sind.

Das ist das Problem, warum SortedSet nicht läuft.

Original geschrieben von Xmas
LinkedList mit modifiziertem add() sollte wesentlich besser abschneiden als ArrayList, weil einfügen und entfernen wesentlich weniger Aufwand bedeuten, selbst wenn du die Einfügeposition nicht mehr per Binary Search bestimmen kannst. Sollte die Liste sehr lang werden, kannst du die Suche immer noch beschleunigen, indem du zusätzlich zu Anfang und Ende auch die Listenmitte speicherst.
Stimmt, daran hatte ich nicht gedacht. Wird Zeit, dass ich es teste.

[HellHorse]

LinkedList:
5500 ms

ArrayList:
344 ms

Allerdings muss gesagt werden, dass alle Inserts im Testszenario am Ende vorkommen.

[El Fantastico]

Vielleicht kannst Du eine TreeMap (implementiert SortedMap) benutzen, in die Du die Objekte mit sich selbst als Schlüssel einfügst?

[HellHorse]

Original geschrieben von El Fantastico
Vielleicht kannst Du eine TreeMap (implementiert SortedMap) benutzen, in die Du die Objekte mit sich selbst als Schlüssel einfügst?
Dann müsste ja, das ValueSet sortiert sein. So wie ich das sehe ist beim Treemap nur jedoch nur das KeySet sortiert.
Sag mir, wenn ich falsch liege.

[El Fantastico]

Original geschrieben von HellHorse
Dann müsste ja, das ValueSet sortiert sein. So wie ich das sehe ist beim Treemap nur jedoch nur das KeySet sortiert.
Sag mir, wenn ich falsch liege.
Ja aber Du fügst ja Value == Key ein, weil Du ja gar keinen richtigen Key hast, oder? Und mit keySet() kommst Du dann an die sortierten Keys, ausserdem werden die Values über iterator() auch in der Reihenfolge der Keys (also Deiner eigentlichen Objekte) aufgezählt.

[HellHorse]

Original geschrieben von El Fantastico
Ja aber Du fügst ja Value == Key ein, weil Du ja gar keinen richtigen Key hast, oder? Und mit keySet() kommst Du dann an die sortierten Keys, ausserdem werden die Values über iterator() auch in der Reihenfolge der Keys (also Deiner eigentlichen Objekte) aufgezählt.
Dann könnte ich ja auch gleich ein TreeSet nehmen, da Value sowieso egal ist.
Wenn ich es so machen würde, müsste ich ja das KeySet sortieren. Kann das aber nicht mit dem Comparator machen, da der für manche Objekte 0 zurückliefert die nicht gleich, sondern bloss gleich gross sind. Würde ich ihn nehmen, würde ein Teil der Elemente nicht hinzugefügt.
Deshalb SortedCollection und nicht SortedSet

Ich fand irgendwo ein Vorlage einer SkipList, die ich mühsam an Collection Framework anpasse, aber im Moment ist sie noch mehr als 10mal langsamer als die LinkedList :-(

[ethrandil]

Wie wäre es denn, wenn du die compareto-Methode so überlädst, dass NIE 0 zurückgegeben wird?
Kommt es dann zu einem endlosloop? Wenn nicht dann sollte das funktionieren!.

[HellHorse]

Original geschrieben von ethrandil
Wie wäre es denn, wenn du die compareto-Methode so überlädst, dass NIE 0 zurückgegeben wird?
Kommt es dann zu einem endlosloop? Wenn nicht dann sollte das funktionieren!.
Ja es kommt zu einem endlosloop. Zumindest bei TreeSet, dass ja bloss ein TreeMap ist.

[El Fantastico]

Stimmt... Denkfehler meinerseits. Sorry!

[Xmas]

Original geschrieben von HellHorse
LinkedList:
5500 ms

ArrayList:
344 ms

Allerdings muss gesagt werden, dass alle Inserts im Testszenario am Ende vorkommen.
Für die Effizienz ist natürlich entscheidend, wie die Elemente zum Einfügen tatsächlich auftreten. Welche Art Objekte sortierst du da, wie ist die Verteilung der "Größe", steckt da ein Muster dahinter?

Wenn alle Inserts am Ende vorkommen, weil du immer größere Elemente anhängst, dann ist ja klar dass ArrayList LinkedList schlägt, weil Binary Search schneller ist und das anhängen an letzter Postition bei ArrayList kein Verschieben der restlichen Elemente erfordert.

Wenn du weißt dass die Inserts eher am Ende als am Anfang sind, kannst du die LinkedList insert() Methode auch rumdrehen, dass sie von hinten anfängt.

[HellHorse]

Original geschrieben von Xmas
Für die Effizienz ist natürlich entscheidend, wie die Elemente zum Einfügen tatsächlich auftreten. Welche Art Objekte sortierst du da, wie ist die Verteilung der "Größe", steckt da ein Muster dahinter?

Wenn alle Inserts am Ende vorkommen, weil du immer größere Elemente anhängst, dann ist ja klar dass ArrayList LinkedList schlägt, weil Binary Search schneller ist und das anhängen an letzter Postition bei ArrayList kein Verschieben der restlichen Elemente erfordert.

Wenn du weißt dass die Inserts eher am Ende als am Anfang sind, kannst du die LinkedList insert() Methode auch rumdrehen, dass sie von hinten anfängt.
Das Problem dahinter ist die Verwaltung von OPEN in GRAPHSEARCH.
Ich sortiere also die Knoten im Suchbaum.
Sind die Kanten ungewichtet (alle 1), dann kommen die Inserts nur am Ende auf. Denn ich prüfe vor dem BinaySearch ob das letzte Element kleiner gleich dem Einzufügenden ist. Falls ja, füge ich es einfach am Ende ein. Wie weiter unten erklärt ist, ist das auch für die LinkedList kein Problem.
In meinem Testszenario sind alle Kanten ungewichtet, könnte aber noch eines mit gewichteten machen.

Habe mal versucht eine LinkedList so zu schreiben, dass zusätlich eine Referenz auf das letzte Element gespeichert wird, für den Fall eines Inserts am Ende. War aber dann zu meinem Erstaunen doppelt bis dreimal so langsam wie eine java.util.List. Habe mir selbige angeschaut und festgestellt, dass das Ding doppelt verkettet ist. header.previous zeigt also schon auf das letzte Element. Bei add(int) (add() in AbstractList ruft add(size()) auf) wird auch überprüft ob size == index ist, falls ja wird vor dem header eingefügt. Daher denke ich, dass die LinkedList bei gewichteten Kanten eher schlechter abschneiden wird.

[HellHorse]

So, ich habe jetzt noch getestet, wenn die Inserts zufällig vorkommen.
Die LinkedList es nur noch etwa 3 mal langsamer als die ArrayList.

[ethrandil]

edit: quatsch

Frage: Mit welcher Methode bekommt man einen einmaligen, einzigartigen wert eines Objektes?

Angenommen man will zwei objekte Vergleichen, die folgendes Interface implementieren:

interface Unique{
public long getId();
}

Dann kann man auch ein (sehr schnelles) TreeSet verwenden, indem man die Comparatoren so verwendet:

final Comparator c = null; //Wieauchimmer dein Comparator aussieht

Comparator ctree = new Comparator(){
public int compare(Object arg0, Object arg1) {
int comparison = c.compare(arg0, arg1);
if(comparison == 0)
return new Long(((Unique)arg0).getId()).compareTo(
new Long(((Unique)arg1).getId()));
else
return comparison;
}
};


Ich hoffe das hilft. Möglich wäre es einen Timestamp zu verwenden. Dabei müsste allerdings garantiert sein, dass kein TimeStamp doppelt verwendet wird. Vielleicht Timestamp + Counter, wobei eine 'Factory-Klasse' das leitet ...

naja, vielleicht könnt ihr mit dem Ansatz was anfangen.

Eth

[HellHorse]

Danke für den Denkanstoss, werde mal ein bisschen rumpröblen.

[HellHorse]

Ja, hat hingehaut:

Ungewichtete Kanten, dh Inserts nur am Ende von Listen. Sorted insert für Listen:
ArrayList: 329 ms
TreeSet: 969 ms
LinkedList: 5343 ms

Gewichtete Kanten, dh zufällige Inserts, aber auch ein bisschen weniger selects. Sorted insert für Listen:

ArrayList: 438 ms
TreeSet: 875 ms
LinkedList: 1172 ms

So jetzt wird noch der Suchbaum optimiert.