Get Schnittpunkte von Rechtecken Nicht O (n²) und OutOfMemory

Question

Ich versuche, die Schnittpunkte von zwei Rechtecken zu erhalten. Ich habe eine Methode, die funktioniert, aber wenn ich es mit einem Algorithmus für 40000 Rechtecke teste, erhalte ich einen OutOfMemory-Fehler. Die Anzahl der Male, die ich auf Kreuzungen überprüfe, ist perfekt O (n²), aber die Zeit, die es braucht, ist nicht. Ich denke, der nicht genügend Speicher ist nur, weil es zu viele Objekte gibt, aber die Zeit, die es braucht, ist nicht O (n²) (getestet mit einem Verdoppelungstest) macht keinen Sinn für mich, und ich kann nicht herausfinden, warum Es macht das.

Dies ist mein Code für die Kreuzung immer

public void getIntersections(Rectangle r, Collection<double[]> c) { 

    x1 = Math.max(this.getLowerLeftX(), r.getLowerLeftX()); 
    y1 = Math.max(this.getLowerLeftY(), r.getLowerLeftY()); 

    x2 = Math.min(this.getUpperRightX(), r.getUpperRightX()); 
    y2 = Math.min(this.getUpperRightY(), r.getUpperRightY()); 


    if(this.contains(x1,y1) && r.contains(x1,y1)) { 
     inter[0] = x1; 
     inter[1] = y1; 
     c.add(inter.clone()); 
    } 

    if(this.contains(x1,y2) && r.contains(x1,y2)){ 
     inter[0] = x1; 
     inter[1] = y2; 
     c.add(inter.clone()); 
    } 

    if(this.contains(x2,y1) && r.contains(x2,y1)){ 
     inter[0] = x2; 
     inter[1] = y1; 
     c.add(inter.clone()); 
    } 

    if(this.contains(x2,y2) && r.contains(x2,y2)){ 
     inter[0] = x2; 
     inter[1] = y2; 
     c.add(inter.clone()); 
    } 
} 

Ich habe versucht, dies als Speicher und CPU effizienter zu machen, aber immer noch ist es nicht funktioniert wie es sollte. Jede Hilfe wird sehr geschätzt.

EDIT: Der Algorithmus, der diese Funktion aufruft:

public void execute() { 
    List<Rectangle> rectangles = this.getRectangles(); 
    Queue<Rectangle> q = new LinkedList<Rectangle>(); 
    q.addAll(rectangles); 
    System.out.println(q.size()); 
    while(!q.isEmpty()){ 
     Rectangle check_rect = q.poll(); 
     for (Rectangle rect: q) { 
      check_rect.getIntersections(rect, this.getIntersections()); 
     } 
    } 
} 

Hilfsfunktionen:

public boolean contains(double x, double y){ 
    return ((x == this.getLowerLeftX() || x == this.getUpperRightX()) || 
      (y == this.getLowerLeftY() || y == this.getUpperRightY())) && 
      x >= this.getLowerLeftX() && x <= this.getUpperRightX() && 
      y >= this.getLowerLeftY() && y <= this.getUpperRightY(); 
} 

Für die Sammlung von Kreuzungen i verwenden:

this.intersections = new ArrayDeque<>(); 

Die outOfMemory Ausnahme immer passiert, wenn es versucht, das ArrayDequezu vergrößern>(), speichert nur die Schnittpunkte in double [2]. Es scheint also, dass es zu viele Schnittpunkte zwischen den 40000 Rechtecken gibt. Ein weiteres Problem scheint zu sein, dass die Iteration, bevor es nicht genügend Arbeitsspeicher hat, es wirklich verlangsamt, ist dies wegen des Swappings oder anderer Speicherverwaltung?

Answer 1

Ok, hier ist es: Ihr Algorithmus ist mehr oder weniger quadratisch. Wenn Sie in jedem Durchlauf mehrere Runs mit doppelt so vielen Elementen wie beim vorherigen Durchlauf durchführen und die Quotienten der Dauer von Paaren aufeinanderfolgender Läufe berechnen, werden Sie feststellen, dass sie mehr oder weniger zwischen 3,5 und 4,5 liegt (Verwerfen von Läufen mit wenigen Elementen) brauche ein paar Tausend, um es stabil genug zu machen).

Das Problem ist, dass 20K ist in Ordnung, aber es mit 2 zu multiplizieren, um 40K Änderungen etwas zu bekommen.

Die Sache, die geändert wird, ist die Fähigkeit der JVM, alle Ergebnisse in ihrem Haufen zu halten. Genau wie user3707125 sagte. Ich habe Ihren Algorithmus mit 51200 Rechtecken ausgeführt.

Sie können das Ergebnis hier:

Nach dem Haufen voll ist der Garbage Collector in Raserei geht etwas Speicher frei versuchen, aber es gibt nichts befreit werden - alle Objekte erreichbar sind. Nach einer Weile erhalten Sie eine OutOfMemoryException mit der Meldung "GC Overhead Limit überschritten". Das bedeutet, dass GC zu viel Zeit verbraucht hat, aber zu wenig Speicher beansprucht hat (ich denke, dass die Standardwerte 98% der CPU-Zeit und 2% des Heaps betragen).

Sie können die Struktur des Haufens sehen hier:

Wie Sie sehen können, die Doppel [] Objekte die Koordinaten nehmen den größten Teil der Halde, gefolgt von Object [] enthält -, dass die interne wäre Array von ArrayDeque.

Was können Sie tun? Sie müssen die Heap-Größe der JVM erhöhen, wenn Sie die App ausführen, genau wie user3707125 sagte. Sie tun das, indem Sie z. -Xmx8g Flag als VM-Option.8g bedeutet hier 8 Gigabyte.

Sie können einen Lauf mit dieser Option siehe hier:

nahm ich es, nachdem der Prozess erfolgreich beendet.

Die andere Sache, die Sie tun könnten, ist darüber nachzudenken, wie Sie den Speicherbedarf reduzieren könnten. Vielleicht Float statt Double? Sie könnten eine benutzerdefinierte Lösung für ein dynamisches Array von doubles schreiben (aber nicht Doubles! Verwenden Sie die Primitiven hier) und behalten Sie eine flache Struktur bei, dh anstatt jeden Punkt als eine separate Anordnung von zwei Doubles zu haben, halten Sie sie alle nebeneinander das dynamische Doppel-Array (zwei Punkte würden 4 Slots belegen). Das würde die Notwendigkeit für eine Schicht von Zeigern eliminieren, die 8 Bytes pro Zeiger (unter der Annahme einer 64-Bit-Architektur) und Array-Längen (4 Bytes) benötigen, was zu einer Menge Speicher führt. Trotzdem, egal wie Sie den Speicherplatzverbrauch Ihres Algorithmus optimieren würden, die Erhöhung der Anzahl der Rechtecke wird den Speicher sehr schnell verzehren. Meier sagte, dass 40000 Rechtecke nicht viel sind, aber ich nehme an, dass Ihre Testdaten viele Schnittpunkte haben - das bedeutet, dass die Menge an Daten, die Sie speichern müssen, O (n²) ist, nicht nur die Zeit, die für die Berechnung benötigt wird.