Collections Fragen zu gleichen Elementen in TreeSet

[Xyz1]

Kann ein(e) TreeSet gleiche Elemente gestatten UND die Reihenfolge gleicher Elemente beibehalten, wenn man einen Comparator angibt ODER andere Kanonen herzunehmen?

 

[mihe7]

Ganz allgemein, direkt unter der Verwendung von java.util.TreeSet denke ich nicht. Grund: die Reihenfolge der Prüfungen ist nicht definiert. Es wäre also abhängig von der konkreten TreeSet-Implementierung, ob und in welcher Weise eine Reihenfolge eingehalten wird.

Mit einem Element-Wrapper muss es funktionieren (der bekommt halt eine ID, die eine Ordnung auf gleichen Elementen definiert). Mit einer Subklasse von TreeSet mit integriertem Wrapper sollte das transparent möglich sein.

 

[VfL_Freak]

Moin,
BTW: was soll hier die blöde Umfrage ???
VG Klaus

 

[Xyz1]

der bekommt halt eine ID

Danke, so habe ich mir das auch gedacht, bis jetzt war es so dass bei Comparator-Gleichheit und bei Nicht-equals-Gleichheit genau das zuletzt eingefüte Elem eingeführt wurde (Set guarantee). Nach Comparator-Gleichheit gleiche Elems standen nach Mehrfacheingefügt also nicht mehr im Set. Ich muss da noch etwas bei fummeln.

 

[mihe7]

bis jetzt war es so dass bei Comparator-Gleichheit und bei Nicht-equals-Gleichheit genau das zuletzt eingefüte Elem eingeführt wurde (Set guarantee).

Wenn, dann müsstest Du es ja umgekehrt machen: Comparator-Ungleichheit bei equals-Gleichheit. Das Problem ist, dass man nicht weiß, welches Element bei compare(a, b) für a verwendet wird und es sein könnte, dass im Code ja einmal compare(a,b) und einmal compare(b, a) vorkommt.

 

[Xyz1]

was soll hier die blöde Umfrage ?

Nur weil Du die Umfrage nicht verstehst.

 

[Xyz1]

Wenn, dann müsstest Du es ja umgekehrt machen

Ja ich weiß aber gerade nicht wie so ein Beispiel-Code aussehen würde? Hättest du einen Denkanstoß?

 

[Xyz1]

@VfL_Freak
Nagut, die Umfrage ist unsinnig
Ich kann sie jetzt nicht mehr bearbeiten, könnte jemand die Umfrage entfernen?

 

[mihe7]

int compare(Object o1, Object o2) {
    if (o1.equals(o2)) { return -1; }
    return ...
}

 

[mrBrown]

int compare(Object o1, Object o2) {
    if (o1.equals(o2)) { return -1; }
    return ...
}

Das bricht aber den compare-Contract, da compare(o1,o2) == compare(o2,o1)? (oder war das mit Absicht ein sehr unvollständiges Beispiel?)

 

[mihe7]

Das bricht aber den compare-Contract

Ja, das ist das oben angesprochene Problem, dass diese "Lösung" von der Implementierung des TreeSet abhängig ist.

 

[Xyz1]

Contract

Kontrakt? Ich dachte das hieße Konvention.

@mihe7 So geht es:

        TreeSet<E[]> tsl = new TreeSet<>((o1, o2) -> {
            int p1 = 0;
            int p2 = 0;
            for (int i = 0; i < o1.length; i += 2) {
                p1 += (o1[i + 1].sell_price - o1[i].buy_price);
                p2 += (o2[i + 1].sell_price - o2[i].buy_price);
            }
            if (p1 != p2) {
                return Integer.compare(p2, p1);
            }
            return Integer.compare(o1.hashCode(), o2.hashCode());
        });

Netbeans meckert mich an .hashCode() auf einem Array aufzurufen.

 

[Xyz1]

Problem, die Einfüge-Reihenfolge wird wird nicht beibehalten.

 

[mihe7]

Tja, dann Wrapper

 

[Xyz1]

dann Wrapper

Oder Schnaps? (Obwohl der heutige Tag auf -tag endet!!!! )

Ne mal ernsthaft, ich bin noch nicht sicher ob das funktionieren kann. Du schriebst die Einfügeoperation wäre ein Implementierungsdetail.... Bei meiner Maschine ist es so dass zum Bleistift beim Einfügen equals() gar nicht mehr zum Zuge kommt. Denn wenn doch dann müsste bei Comparator-Gleichheit Hashcode-equals()-Gleichheit falsch sein, wonach eingefügt werden SOLLTE.... tuts aber nicht.

Wärs nicht doch besser alles nicht sortiert in einer listenartigen Struktur anzusammeln und zum Schluss einmal zu sortieren?

 

[mihe7]

Wärs nicht doch besser alles nicht sortiert in einer listenartigen Struktur anzusammeln und zum Schluss einmal zu sortieren?

Vermutlich schon. Kommt halt darauf an, was Du letztlich vorhast; Deine Frage zielte aber explizit auf TreeSet ab.

Bei meiner Maschine ist es so dass zum Bleistift beim Einfügen equals() gar nicht mehr zum Zuge kommt.

Nicht nur bei Deiner Maschine und nicht nur beim Einfügen: für das TreeSet ist dokumentiert, dass ausschließlich ein Comparator zum Einsatz kommt.

Genau deswegen kann man ja zwei Objekte, die equals-gleich sind, in ein TreeSet überhaupt erst einfügen. Dazu muss man aber dafür sorgen, dass compareTo bzw. der Comparator Ungleichheit liefert, wenn equals-Gleichheit vorliegt.

Das Problem dabei ist, dass man die Implementierung nicht kennt, d. h. man weiß nicht, ob z. B. das eingefügte mit dem vorhandenen oder das vorhandene mit dem eingefügten Element verglichen wird. Man weiß auch nicht, ob diese Vergleiche an allen Stellen im TreeSet gleichermaßen erfolgt. Daher ist das eine sehr fragile Angelegenheit, die nur mit Glück funktioniert.

Wenn man das stabil mit einem TreeSet machen will, benötigt man einen Wrapper, der im Endeffekt einen Knoten - bestehend aus Nutzdaten und einer ID - im Baum darstellt. Die ID muss in Deinem Fall die Einfügereihenfolge darstellen.

Dann kann man für zwei Wrapper-Objekte w1 und w2 definieren:
w1 gleich w2 <=> w1.id == w2.id
w1 kleiner w2, falls w1.daten kleiner w2.daten oder (w1.daten gleich w2.daten UND w1.id < w2.id)

 

[Xyz1]

Mal anders an die Frage heran.... Müssen die in einer TreeSet zu sortierenden E[]s nicht die Eigenschaft einer totalen Quasiordnung (reflexiv ,transitiv und total) inne haben? - Oder anders: Besitzen die E[]s diese nicht bereits?

 

[mrBrown]

Kontrakt? Ich dachte das hieße Konvention.

Vertrag ist was anderes als Konvention...

Vertrag ist in dem Fall, dass deine compare-Methode entsprechend der Vorgabe des Interfaces funktioniert.

 

[Xyz1]

Ich bin mir ganz sicher das das nicht Kontrakt heißt sondern Konvention.... Aber Du wirst ganz bestimmt mehr Rechtsvorlesungen gehört haben als ich, Dich bestens damit auskennen und niemals Lügen verbreiten? Wenn ich etwas nicht weiß dann antworte ich idR nicht (um andere nicht zu stören) Bei Dir scheinbar nicht so.

 

[mrBrown]

Ich bin mir ganz sicher das das nicht Kontrakt heißt sondern Konvention.... Aber Du wirst ganz bestimmt mehr Rechtsvorlesungen gehört haben als ich, Dich bestens damit auskennen und niemals Lügen verbreiten? Wenn ich etwas nicht weiß dann antworte ich idR nicht (um andere nicht zu stören) Bei Dir scheinbar nicht so.

Durchsuch einfach mal das Javadoc von Comparator nach "contract" und nach "convention"

Was zur Hölle soll das mit Rechtsvorlesungen zu tun haben? Wie viel Stuss kann man noch in einem Beitrag unterbringen?

 

[Xyz1]

Netbeans meckert mich an .hashCode() auf einem Array aufzurufen.

@mihe7 hoffe ich wecke Dich nich....
Ich weiß wieso Netbeans da meckert, weils da Hashcollisionen geben könnte und zwar werden da ca 0,0001% der Elem NICHT gespeichert.

ALSO: Doch ein Wrapper.

(Quelle)

 

[mihe7]

ALSO: Doch ein Wrapper.

Wobei das eher ein Whopper ist

 

[mrBrown]

Warum willst du überhaupt ein TreeSet nutzen? Ein Set ist ja offensichtlich nicht das, was du willst...

Nimm einfach ne geeignete Datenstruktur (am besten als Ersatz für das Set und für deine Datenstruktur...), dann kannst du auf merkwürdige Hacks verzichten.

 

[mihe7]

Ich finde es gar nicht so merkwürdig, wenn man gleichen Elementen ein zusätzliches Merkmal spendiert, um sie untereinander unterscheidbar zu machen und ggf. auch noch eine Ordnung darüber zu definieren. Das machen die Päpste schon lange

 

[Xyz1]

@mrBrown Eine TreeSet heißt zwar Set.... aber ist keine ( im eigentlichen Sinne ). Das hast Du bestimmt schon gemerkt.

Was ist denn so schlecht daran sich vorhandener Strukturen zu bedienen?

Ein Jack wär eher eine Zweckentfremdung. ( Das ist es natürlich nicht, es vermittelt eher ein falsches Bild *grübel - und hier ein paar fiese Phraologismen einsetzen.... * ) : ein falscher Hase zB

 

[Xyz1]

Das machen die Päpste schon lange

Schlechtes Beispiel (ganz böse Du heute bist....), es kann immer nur ein Papst gleichzeitig sein.

 

[mrBrown]

Ich finde es gar nicht so merkwürdig, wenn man gleichen Elementen ein zusätzliches Merkmal spendiert, um sie untereinander unterscheidbar zu machen und ggf. auch noch eine Ordnung darüber zu definieren. Das machen die Päpste schon lange

Generell ist das auch nicht merkwürdig
nur, wenn man das machen will, damit man gleiche Element in eine Collection zwängen kann, die für das Problem ungeeignet ist, ist etwas merkwürdig...

@mrBrown Eine TreeSet heißt zwar Set.... aber ist keine ( im eigentlichen Sinne ). Das hast Du bestimmt schon gemerkt.

Nö, hab ich bisher noch nicht gemerkt. (...außer du meinst equals vs compare)

Was ist denn so schlecht daran sich vorhandener Strukturen zu bedienen?

Nichts, das ist genau richtig. Die Frage ist nur, was die richtige vorhandene Struktur ist, und dafür müsste man wissen, was deine Anforderung ist ("gleiche Elemente in ein TreeSet würde ich jetzt nicht als solche bezeichnen...)

 

[mihe7]

es kann immer nur ein Papst gleichzeitig sein.

Sonst würde ja auch eine ConcurrentPopeException geworfen.

die für das Problem ungeeignet ist

Nachdem wir sein Problem nicht kennen...

 

[mrBrown]

Nachdem wir sein Problem nicht kennen...

Ja gut, aber zumindest klingt hier nichts danach, als wäre ein TreeSet die sinnvollste Lösung

 

[mihe7]

Mir schwebt etwas wie in einer DB vor: ein non-unique Index auf Basis eines Baums unter Beibehaltung der Einfügereihenfolge. Welche Standardklasse gäbe es hierfür außer dem TreeSet noch?

 

[mrBrown]

z.B. Wrapper um Map<E,List<E>>, dürfe vom Aufwand her ähnlich sein wie eine vernünftige Umsetzung mit TreeSet und Wrapper um die Elemente

Edit: Als Map Implementierung dann TreeMap, wenn man das als Baum braucht

 

[mihe7]

Die Standardlösung. OMG, wie sich das Hirn schnell auf etwas einschießen kann; das ist ja echt unfassbar.

 

[mrBrown]

Oder sogar, wie in zB den Apache-Commons-Bags, ein Wrapper um Map<E, Integer>, wenn die Elemente das hergeben

 

[Xyz1]

ein non-unique Index auf Basis eines Baums unter Beibehaltung der Einfügereihenfolge

@mihe7 Bitte keine Esoterik.

Welche Standardklasse gäbe es hierfür außer dem TreeSet noch

vielleicht keine. Viell alternativlos. (Spaß...)

@mrBrown Wenn die Anforderungsdefinition man ändern würde, dass diese Collection nicht jederzeit sortiert sein müsste, dann langte auch eine ArrayList.

 

[mrBrown]

@mrBrown Wenn die Anforderungsdefinition man ändern würde, dass diese Collection nicht jederzeit sortiert sein müsste, dann langte auch eine ArrayList.

Und wenn man die Anforderungen kennen würde, könnte man uU noch eine bessere Alternative vorschlagen

 

[mihe7]

Bitte keine Esoterik.

Jeden Tag, direkt nach dem Aufstehen, spreche ich erstmal mit meinen B-Trees.