獲取矩形的交點不是O（n²）和OutOfMemory

-1

我試圖獲得兩個矩形的交點。我有一個方法，但是當我用40000矩形的算法測試它時，我得到一個OutOfMemory錯誤。我檢查交叉點的次數完全是O（n²），但所花費的時間不是。我認爲內存不足是因爲有太多的對象，但它所需要的時間不是O（n²）（用雙倍測試測試）對我來說沒有意義，我不明白爲什麼它是這樣做的。獲取矩形的交點不是O（n²）和OutOfMemory

這是我得到的交集

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()); 
    } 
}

我試圖使這是內存和CPU高效的代碼，但它仍然無法正常工作，因爲它應該。任何幫助，不勝感激。

編輯：調用該函數的算法：

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()); 
     } 
    } 
}

輔助功能：

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(); 
}

對於交叉口的集合，我使用：

this.intersections = new ArrayDeque<>();

的OutOfMemory例外總是當它試圖放大ArrayDeque時發生>（），它只將交點存儲在double [2]中。所以看起來40000個矩形之間的交叉點太多了。另一個問題似乎是內存耗盡之前的迭代，它真的放慢速度，這是因爲交換或其他內存管理？

來源

2016-04-23 Midasso

你看過性能下降的動態（1000,5000,10000矩形）嗎？你也應該提供調用這個方法的代碼，因爲問題可能在那裏。你的方法也適用於副作用，這被認爲是不好的做法。通常你想返回一個新的交集對象，而不是操縱輸入和全局變量。 – user3707125

你能否提供這裏使用的所有方法的實現？這意味着所有的'getLowerRight'，'getUpperLeft'等方法和'contains'方法。另外請包括'inter'數組的聲明 –

我添加了更多信息，以便您可以看到我在做什麼。 – Midasso

-1

好吧，這裏是：您的算法是或多或少的二次方。如果您在每次運行中進行多次運行（與前一次運行相同）的多次運行並計算後續運行對的持續時間的商數，則會發現它在3.5到4.5之間或多或少地下降（丟棄運行時幾乎沒有元素，需要幾千個才能使其足夠穩定）。

問題是20K很好，但乘以2得到40K會改變一些東西。

改變的是JVM將所有結果保存在堆中的能力。就像user3707125所說的那樣。我用51200個矩形運行了你的算法。

您可以在這裏結果：

後堆是滿的垃圾收集器進入狂熱設法釋放一些內存，但沒有什麼被釋放 - 所有對象都是可到達。一段時間後，您會收到一條信息OutOfMemoryException，並提示「GC overhead limit exceeded」。這意味着GC使用了太多時間，但回收的內存太少（我認爲默認值爲CPU時間的98％和堆的2％）。

你可以看到堆在這裏的結構：

正如你所看到的，包含座標雙[]對象佔用大部分堆，接着對象[] - 這將是內部ArrayDeque數組。

你能做什麼？在運行應用程序時，您必須增加JVM的堆大小，就像user3707125所說的那樣。你通過傳遞例如-Xmx8g標誌作爲VM選項。這裏的8g表示8千兆字節。

你可以看到一個奔跑與這裏的選項：

我把它之後的過程中順利完成。

你可以做的另一件事是考慮如何減少內存佔用。也許使用花車而不是雙打？您可以爲doubles（但不是（但不是Doubles！請使用這裏的基元）並且保持一個扁平的結構，即不是每個點都作爲兩個雙打的單獨數組）的一個自定義解決方案，而是將所有點並排保存在動態雙數組（兩個點佔用4個時隙）。這將消除需要一層指針（每個指針需要8個字節）（假設爲64位體系結構）和數組長度（4個字節），這會增加大量內存。不過，無論你如何調整算法的空間使用率，增加矩形的數量都會非常快地佔用內存。 Meier說，40000個矩形並不多，但我認爲你的測試數據有很多交點 - 這意味着你需要存儲的數據量是O（n2），而不僅僅是計算它的時間。

來源

2016-04-26 11:18:30

我已經通過將數據寫入輸出文件來解決問題，而不是將其保存在數據結構中。現在內存異常不再發生，因爲應用程序只計算交叉點並且不再跟蹤它們。 – Midasso

獲取矩形的交點不是O（n²）和OutOfMemory

回答

相關問題