Schneller Zugriff auf Liste mit sortierten Flaechen..?

[sirbender]

Hi,

ich habe eine Liste mit Rechtecken die nach ihrer Flaeche sortiert sind. Wenn ich jetzt z.B. ein Rechteck der Flaeche 20 will muesste ich eigentlich gar nicht ueber alle Elemente der Liste iterieren sondern nur ueber die letzte Haelfte weil alle Rechtecke davor groesser sind.

Gibt es Listen die die Sortierung irgendwie clever ausnutzen koennen und intern eine schnellere Suche verwenden als ueber alle Elemente zu iterieren?

 

[Gast2]

Dafür gibts Bäume/Maps (z.b. die TreeMap).

        Map<Double, Rectangle> map = new TreeMap<Double, Rectangle>();

        Rectangle r1 = new Rectangle(10, 10);
        Rectangle r2 = new Rectangle(10, 5);
        Rectangle r3 = new Rectangle(10, 3);

        map.put(r1.getWidth() * r1.getHeight(), r1);
        map.put(r2.getWidth() * r2.getHeight(), r2);
        map.put(r3.getWidth() * r3.getHeight(), r3);


        /** Rechteck mit der Fläche 50 rausholen */
        Rectangle area50 = map.get(Double.valueOf(50)); // gibt r2 zurück

 

[Ruzmanz]

TreeMap bietet sich auf jeden Fall an, wenn du nur über die Fläche auf die einzelnen Rechtecke zugreifen willst. Denn die musst du schließlich wissen. Ansonsten wäre hier eine sotierte Liste besser, immerhin möchtest du doch folgenes machen?:

gibAlleGrößer10()
10
11
14
16

 

[sirbender]

Ist dieser Ansatz sehr viel schneller als ueber die Liste zu iterieren? Kann bei der Map direkt das richtige Element angesprungen werden? Wie funktioniert das?

Kann ich mehrere Elemente der Groesse 50 in der Liste haben? Welches wird zurueckgeliefert?

Hmmm...kann ich mit diesem Ansatz auch z.B. eine Liste von Rechtecken erhalten die alle > 20 sind bzw. eine Liste von Rechtecken mit einer Flaeche zwischen > 10; < 25 ?

 

[Gast2]

Die genaue Implementierung der TreeMap habe ich mir nicht angeschaut, aber ich vermute dass die ähnlich wie nen binärer Baum arbeitet. Also ne Laufzeit von O(log n) hat (im vergleich die Liste: O(n)).

Bei sehr vielen Einträgen (ich schätze mal so ab ein paar hundert tausend einträgen) wirst du da dann schon nen performanceunterschied feststellen.

Hmmm...kann ich mit diesem Ansatz auch z.B. eine Liste von Rechtecken erhalten die alle > 20 sind bzw. eine Liste von Rechtecken mit einer Flaeche zwischen > 10; < 25 ?

Nein, diese Funktionalität bietet die TreeMap nicht an. Aber so ein binärer suchbaum mit ner bereichssuche lässt sich relativ leicht implementieren 🙂

 

[madboy]

Dafür gibts Bäume/Maps (z.b. die TreeMap).

        Map<Double, Rectangle> map = new TreeMap<Double, Rectangle>();

        Rectangle r1 = new Rectangle(10, 10);
        Rectangle r2 = new Rectangle(10, 5);
        Rectangle r3 = new Rectangle(10, 3);

        map.put(r1.getWidth() * r1.getHeight(), r1);
        map.put(r2.getWidth() * r2.getHeight(), r2);
        map.put(r3.getWidth() * r3.getHeight(), r3);


        /** Rechteck mit der Fläche 50 rausholen */
        Rectangle area50 = map.get(Double.valueOf(50)); // gibt r2 zurück

Vorsicht, das kann (und wird) in die Hose gehen. Beispiel:

double d1 = 0.1*0.1;
double d2 = 0.01;
System.out.println(Double.valueOf(d1).equals(Double.valueOf(d2))); //false

 

[Ruzmanz]

Die Map arbeitet mit Keys, somit würden sich Duplikate doch überschreiben? Zudem glaube ich nicht, dass der Tree wesentlich schneller ist. Bei einer Filterrung wäre die sotierte Liste vorteilhafter (zumindest bei einen großen Wertebereich). Sicher bin ich mir aber nicht, das muss man selbst überprüfen 🙂

 

[Marco13]

Es kann für jeden Key nur ein Wert enthalten sein. Wenn das nicht stört: Für Bereiche, die zwischen zwei Keys liegen, gibt es extra diese Methode ...