获取矩形的交点不是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

回答

相关问题