Schnelle, dynamische, geordnete Datenstruktur?

[Abstrakt]

Hallo zusammen,

ich bastel mir gerade eine kleine graphische Anwendung, und suche dazu eine relativ spezielle Datenstruktur..

Am besten beschreibe ich einfach mal schnell das Szenario:

Grundlage ist die (natürliche) Gitter-Ebene N^2. Per Mausklick/-drag erstellt der Benutzer Rechtecke in N^2 (Wer es jetzt schon vermutet hat: Genau, es geht um Pixel, .awt , .swing - aber das ist nur nebensächlich für meine gleich folgende Frage), oder - falls er auf ein schon existierendes Rechteck geklickt hat - verschiebt das gewählte Rechteck.


die Rechtecke sind simpel strukturiert, z.B.

class Rect(){
	int X_UpperLeft;
	int Y_UpperLeft;
	int height;
	int width;
}

Nun mein Problem: Alle erstellten Rechtecke müssen gespeichert werden, und zwar sortiert nach x-Koordinate (X_UpperLeft). Ich brauche also eine dynamische, Integer-geordnete Datenstruktur, die relativ schnell ist, wenn es darum geht

(i) ein neues Element an einer beliebigen Stelle der Ordnung einzufügen (wenn man ein neues Rechteck erstellt) ...löschen sollte am besten auch gleich dabei sein.
(ii) zwei in der Ordnung nebeneinander stehende Elemente zu vertauschen (wenn man ein Rechteck verschiebt)
(iii) die gesamte Anzahl der momentan gespeicherten Elemente zu nennen

Anmerkung zu (i): Es muss nicht unbedingt ein O(log n) - Einfügen/Löschen sein, die Anzahl der Rechtecke sollte (anwendungsbedingt) nie über 40 liegen.



In C würde ich mir einfach schnell etwas auf Pointer-Listen-Basis basteln, aber das geht in Java ja nicht. Ich tendiere schon in Richtung Arraylist oder LinkedList, habe mir dazu aber noch nicht genug durchgelesen und bin nicht sicher, ob die Strukturen schnell genug sind (die Datenstruktur muss letztlich bei jedem MouseEvent aktualisiert werden, und dann kommen noch einige weitere Rechnungen hinzu), oder ob es in Java nicht vielleicht eine bessere Struktur für die genannten Anforderungen gibt.

Und das ist meine Frage.. auch wenn da jetzt kein Fragezeichen drin vorkam.



mfg und danke im voraus.

 

[Ark]

Pack deine Rechtecke in ein TreeSet<Rechteck> und implementiere Comparable<Rechteck> in Rechteck geeignet.

Ark

 

[Abstrakt]

So, ich habe das Fehlen weiterer Antworten dann mal als stille Zustimmung gewertet, und den Tipp "TreeSet" verfolgt. Also schonmal noch ein Danke an Ark.

Mittlerweile bin ich durch Recherche und Probieren (Set-Interface war Neuland für mich..) zu einer hoffentlich relativ passenden Umsetzung gekommen. ..Und an dem Satz merkt man es schon: So richtig laufen tut es noch nicht.


Also hier noch ein paar Nachfragen:

Basierend wieder auf meinem Datentyp

class Rect(){
    int X_UpperLeft;
    int Y_UpperLeft;
    int height;
    int width;
}

1. Nur zur Sicherheit.. Mein TreeSet soll dynamisch bzgl. der Ordnung der Elemente sein, das ist ein einfaches TreeSet

java.util.Set RectsSortByX = new java.util.TreeSet<Rect>();

nicht. Aber mit

java.util.SortedSet<Rect> RectsSortByX = java.util.Collections.synchronizedSortedSet(new java.util.TreeSet<Rect>(SortByX));

krieg ich genau das, was ich brauche. Richtig soweit? (SortByX ist mein selbstgebauter Comparator)


2. Ich habe vor allem ein Problem mit der Zugriffssteuerung bzgl. der Elemente im Tree.. bis jetzt sieht mein Einfügen per Listener so aus:

public class NewJFrame extends javax.swing.JFrame {
    private Rect CurrentRect = new Rect();
.
.
.
    private void canvas1MousePressed(java.awt.event.MouseEvent evt) {
        CurrentRect.X_UpperLeft = evt.getX();
        CurrentRect.Y_UpperLeft = evt.getY();
    }

    private void canvas1MouseReleased(java.awt.event.MouseEvent evt) {
        CurrentRect.height = evt.getY() - CurrentRect.Y_UpperLeft;
        CurrentRect.width = evt.getX() - CurrentRect.X_UpperLeft;
        Data.RectsSortByX.add(CurrentRect);
    }
.
.
.
}

...und nach mehreren kleinen Tests hatte ich die Vermutung, dass ich nie mehr als ein einziges Element im Tree hatte, bei einer neuen MouseDrag-Aktion also nur die inneren Werte des einen Elements verändert werden.

Frage hierzu: Wie kann ich (in NetBeans) meinen Tree am besten debug-überwachen, so dass ich eine Auflistung aller Elemente sehe?

Und wie ist das mit Iterator/Zugriffsstreuerung? sagen wir, ich habe zwei Elemente im Tree und möchte von einem gezielt einen inneren Wert ändern. Wie weise ich einem Element im Tree eine lokale Variable zu, so dass die beiden über längere Zeit linked sind? und wie hebe ich die Verknüpfung wieder auf?



Nochmal schon ein Danke im voraus, dann bin ich mal gespannt was als Antwort kommt.

 

[Abstrakt]

hm, keiner? Ich hätte eigentlich gedacht, wer sich schonmal mit TreeSet etc. beschäftigt hat, kann das quasi im Vorbeigehen beantworten.

Naja, ich hab die Antworten auf meine Fragen mittlerweile selbst zusammengesucht (ob das jetzt optimale Lösungen sind, frag ich mich immernoch..), und bin wieder etwas weiter, habe aber wieder eine Frage zum Thema:



Ein Problem mit der Notation in java...


Ich nutze also die

Class TreeSet<E>,

und die hat Implemented Interfaces:

NavigableSet<E>, Set<E>, SortedSet<E>


Ich kann eine Instanz der Klasse TreeSet erschaffen mit

java.util.SortedSet<Rect> RectsSortByX = java.util.Collections.synchronizedSortedSet(new java.util.TreeSet<Rect>());

aber ich brauche auch Methoden, die sich in NavigableSet<E> befinden. NavigableSet<E> ist SubInterface von SortedSet<E>.



wie muss ich das Konstruieren ändern, damit ich die Methoden vom SuperInterface (also SortedSet) UND vom SubInterface ansprechen kann?

mit

java.util.NavigableSet<Rect> RectsSortByX = ...;

geht es mal nicht.



?

 

[Marco13]

Nicht so ungeduldig

Das mit dem NavigableSet geht erstmal nicht direkt - das einzige, was mir da einfallen würde, wäre, die Collections.synchronizedSortedSet zu kopieren, und zu einer eigenen Methode synchronizedNavigableSet zu erweitern - das wäre glaub' ich ziemlich trivial.

Aber noch ein ganz anderer Punkt: Wenn du das einmal in ein TreeSet packst, dann bleibt die Sortierung so, wie sie beim Einfügen war. D.h. wenn du nach dem Einfügen einen x-Wert änderst, ändert sich dadurch an der Reihenfolge im TreeSet nichts (genaugenommen kommt dann sogar ganz großer Murks raus :autsch: ).

Eine Möglichkeit wäre nach einer "Heap" datenstruktur zu suchen: Die haben meistens solche Methoden wie "restoreHeapProperty" o.ä., die es erlauben, die Sortierung nach Änderungen relativ schnell zu aktualisieren...

 

[Ark]

Eine Möglichkeit wäre nach einer "Heap" datenstruktur zu suchen: Die haben meistens solche Methoden wie "restoreHeapProperty" o.ä., die es erlauben, die Sortierung nach Änderungen relativ schnell zu aktualisieren...

Mit einem Baum geht das aber auch ähnlich: Element rausnehmen, Wert ändern, Element wieder einfügen.

Ark

 

[Marco13]

Wenn man an einer Stelle den Baum hat, und jemand anderes ganz woanders etwas an einem Element ändert (und dort ggf. nicht mal weiß, DASS das Element irgendwo in einem Baum liegt) schaut man mit dem Ofenrohr ins Gebirge. Bei einem Heap könnte man diese restoreHeapProperty-Methode gelegentlich "pauschal" aufrufen, ohne wissen zu müssen, was sich geändert hat... Inwieweit das dann ein Performancenachteil wäre, müßte man sich überlegen.
Wenn derjenige, der das Element verändert aber den Baum kennt, und weiß, dass er jedes Element nach jeder Änderung entfernen und wieder Hinzufügen muss, kann man das natürlich machen. Um die Fehleranfälligkeit zu reduzieren könnte man sich da vielleicht auch was Listener-Artiges überlegen, was dieses Entfernen/Einfügen bei jeder Änderung automatisch macht...

 

[Abstrakt]

Mit einem Baum geht das aber auch ähnlich: Element rausnehmen, Wert ändern, Element wieder einfügen.

Ark

So, nach ein paar anderen Versuchen hab ich diesen Weg dann auch gewählt. Das switchen via .remove + .add läuft per listener, allerdings habe ich noch ein Problem dabei: Ich dachte zuerst, die Objekt-Speicher-Adresse sei relevant beim .remove(Objekt), aber leider bewirkt dieses .remove(Objekt) nur, dass mittels benutzem Comparator ein Objekt im Set ausfindig gemacht wird, das laut diesem Comparator gleich dem gesuchten Objekt ist.
In meinem konkreten Fall heisst das, dass öfters mal das falsche Objekt rausfliegt, einfach nur weil mehrere gespeicherte Objekte die gleiche Breite haben, und mein Comparator eben nach Breite ordnet.


Um es etwas einfacher zu machen: Wenn man als Objekte 2D-Punkte (java.awt.Point) hätte, und man wollte sie ordnen:
(P1 < P2) gdw. ( (P1.x < P2.x) oder ((P1.x = P2.x) und (P1.y < P2.y)) )

Wie sähe dann der Comparator aus?


Ich habe da schon ein paar Sachen probiert, aber ohne eine Antwort von jemandem der das weiss, oder einem ausführichen Artikel über die inneren/unsichtbaren Abläufe eines SortedSet, komm ich so blad nicht weiter.



Wär toll, wenn mir da jemand helfen könnte, mfg.

 

[Marco13]

Um es etwas einfacher zu machen: Wenn man als Objekte 2D-Punkte (java.awt.Point) hätte, und man wollte sie ordnen:
(P1 < P2) gdw. ( (P1.x < P2.x) oder ((P1.x = P2.x) und (P1.y < P2.y)) )

Wie sähe dann der Comparator aus?

public int compare(Point p1, Point p2)
{
    if (p1.x < p2.x) return -1;
    if (p1.x > p2.x) return 1;
    if (p1.y < p2.y) return -1;
    if (p1.y > p2.y) return 1;
    return 0;
}

Man kann sich zwar den Quellcode und die Doku von TreeSet etc. ansehen, aber ich GLAUBE zwei Elemente gelten als gleich, wenn der Comparator 0 zurückgibt - ich GLAUBE, die "equals"-Methode wird nicht verwendet... Aber allgemein: Wenn dort mehrere Objekte vorkommen, bei denen der Comparator 0 liefert, die aber trotzdem noch mehrfach auftreten sollen, müßte man sich vielleicht eine Alternative zum TreeSet überlegen...

 

[Abstrakt]

Okay, ich habe fertig.

Danke an alle Tippgeber.

Wahrscheinlich meine letzte Frage zum Thema: Ich würde die Geschwindigkeit der Datenstruktur gerne prüfen. (genau genommen habe ich nun mehrere Möglichkeiten implementiert und möchte vergleichen)
Dazu dachte ich mir, rund um einen etwas größeren Prozess ermittle ich einfach die benötigte Zeit in entsprechend kleiner Einheit. Frage: Wie geht das am einfachsten? Gibt es da spezielle Klassen/Methoden schon in der Java-Lib? Ich vermute es, aber ich habe nichts wirklich passendes gefunden..

also sowas wie..

{
...
Stopwatch.start(ns)
...
Stopwatch.stop
...
}


Wer hat sowas schonmal gemacht, wer kennt eine gute Methode, in java kleine Zeiten zu messen?


mfg

 

[Schumi]

long now = System.currentTimeMillis();
...
long result = System.currentTimeMillis() - now;

oder mit System.nanoTime() falls es Nano-Genauigkeit sein soll.

 

[Marco13]

Solche "Microbenchmarks" sind immer ein bißchen heikel. Ein grobes "Muster", mit dem sie wenigstens einen Hauch von Aussagekraft haben, ist sowas wie

void timingFürMethodeA(int eingabegröße)
{
    long before = System.nanoTime();
    int ergebnis = 0;
    for (int i=0; i<eingabegröße; i++) ergebnis += methodeA();
    long after = System.nanoTime();
    System.out.println("MethodeA "+ergebnis+" Zeit "+(after-before));
}
// Das gleiche für MethodeB
...

void vergleiche()
{
    for (int i=10000; i<=100000; i+=10000)
    {
        timingFürMethodeA(i);
        timingFürMethodeB(i);
    }
}

Also die Methoden abwechselnd mit wachsender Eingabegröße laufen lassen, wobei die Laufzeit jeweils mindestens im Sekundenbereich liegen sollte.

Aber wie viel das ganze wirklich bringt, kann dir nur ein Profiler sagen...