DFS/BFSアルゴリズムでネイバーを取得する際にメモリ割り当てを避けますか？

Question

私はグリッドマップのDFSを行うコードを書いています。私は多くのことを呼んで一つの機能は、指定したセルのすべてのネイバーを取得しますgetNeighbors（...）である：

public ArrayList<Point> getNeighbors(int i, int j) { 
    ArrayList<Point> result = new ArrayList<>(); 
    for (Point n : upDownLeftRightDirections) { 
     int dx = i + n.x; 
     int dy = j + n.y; 
     result.add(new Point(dx, dy)); 
    } 
    return result; 
} 

... Later in the code ... 

for (Point neighbor : getNeighbors(i, j)) { 
    ... Do stuff ... 
} 

私の質問は、私は、このプロセスは、すべての隣人の新しいリストを作成するために無駄なようだと感じていることです隣接セルのリストが1回だけ使用されるので、セルが処理される時間。毎回新しいリストを作成しないように書き直す方法の提案 - 主にコールごとに一度ネイバーを繰り返し処理するだけで済むという事実を利用するか？

Answer 1

たびにあなたはインスタンス変数としてresultリストを宣言することができ、新しいリストを作成しないように書き換える方法については任意の提案。

for (Point neighbor : results) { 
    ... Do stuff ... 
} 
results.clear(); 

を主に、私は一度だけコールあたり 以上の隣人を反復処理する必要があるという事実を利用するには：この方法では、あなたは隣人を反復処理を終了毎回それをクリアすることができますか？

コードをベンチマークして、以前のアプローチよりもパフォーマンス上の利点があるかどうかを確認する必要があります。

Answer 2

ここでも機能的なアプローチが可能です。私は、Javaの深い意味論に慣れていないけど、何かのように：

public void consumeNeighbors(Function f) { 
    for (Point n : upDownLeftRightDirections) { 
     int dx = i + n.x; 
     int dy = j + n.y; 
     f(dx, dy); 
    } 
} 

これは隣人を反復しながら、新しいPointオブジェクトと新しいリストを作成しないでしょう。しかし、これは大幅な節約をもたらすことは明らかではないので、このようにリファクタリングする価値があるかどうかを判断するためのベンチマークが必要になります。