長方形の交点を取得するO（n²）とOutOfMemory以外

Question

私は2つの長方形の交差点を取得しようとしています。私は動作するメソッドがありますが、40000四角形のアルゴリズムでテストすると、OutOfMemoryエラーが発生します。交差点をチェックする時間は完全にO（n²）ですが、時間はかかりません。 私はメモリが足りないのは、オブジェクトが多すぎるからだと思うが、時間がかかるのはO（n²）（倍増テストでテストされていない）が私には意味がなく、なぜそれはそうしています。

は、これは私がメモリとCPUの効率的としてこれを作ってみました

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

交差点を取得するための私のコードですが、まだそれはそれが必要として動作しません。 何か助けていただければ幸いです。

EDIT：この関数を呼び出す アルゴリズム：

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の四角形の間にあまりにも多くの交差点があるようです。 もう一つの問題は、スワッピングや他のメモリ管理のために、メモリが使い果たされる前の繰り返し、本当に遅くなることです。

Answer 1

あなたのアルゴリズムは多かれ少なかれ2次です。以前の実行と各実行で2倍の要素を持つ複数の実行を実行し、その後の実行の実行時間の商を計算すると、3.5から4.5の間の範囲に収まることがわかります。それを十分に安定させるために数千人が必要です）。

問題は、20Kはちょうどいいですが、2倍して40Kになると何か変わります。

変更されたことは、JVMがすべての結果をヒープに保持できるかどうかです。ちょうどuser3707125が言ったように。私はあなたのアルゴリズムを51200の長方形で走らせました。

あなたはここになります：ヒープの後

は、ガベージコレクタは、いくつかのメモリを解放しようとして逆上に入るいっぱいですが、解放されることは何もありません - すべてのオブジェクトが到達可能です。しばらくすると、 "GCオーバーヘッドの上限を超えました"というメッセージのあるOutOfMemoryExceptionが表示されます。つまり、GCは時間がかかっていましたが、メモリが少なすぎました（デフォルトではCPU時間の98％、ヒープの2％と思います）。

あなたはここで、ヒープの構造見ることができます：あなたが見ることができるように、座標を含むダブル[]オブジェクトが[]オブジェクトに続いて、ヒープのほとんどを取る

を - 内部であろうとArrayDequeの配列

あなたは何ができますか？ user3707125と同じように、アプリケーションの実行時にJVMのヒープサイズを大きくする必要があります。たとえば、 VMオプションとして-Xmx8gフラグ。8gは8ギガバイトを意味します。

あなたはここでそのオプションを指定して実行を見ることができます：プロセスが正常に終了した後

が、私はそれを取りました。

もう1つのことは、どのようにメモリフットプリントを減らすことができるかを考えることです。多分ダブルスの代わりに浮動小数点数を使うのでしょうか？ doublesの動的配列（ただし、Doublesではありません！ここではプリミティブを使用してください）のカスタム配列を作成し、フラットな構造を保つことができます。つまり、各点を2つのダブルの別々の配列にする代わりに、動的二重配列（2つの点は4つのスロットを占める）。これは、ポインターあたり8バイト（64ビットアーキテクチャーと仮定）と配列長（4バイト）を取る1層のポインターが不要になり、多くのメモリーを追加します。それでもアルゴリズムの空間使用量をどのように調整しても、長方形の数を増やすとメモリが非常に高速になります。 Meier氏によると、40000の四角形はあまりありませんが、テストデータには多くの交差点があると想定しています。つまり、保存する必要があるデータ量は、計算にかかる時間だけでなく、O（n²）です。