Vermeiden Sie Speicherzuordnungen, während Sie Nachbarn in einem DFS/BFS-Algorithmus erhalten?

Question

Ich schreibe einen Code, der ein DFS einer Rasterkarte macht. Eine Funktion, die ich eine Menge nennen, ist die getNeighbors (...), die alle Nachbarn einer bestimmten Zelle bekommt:

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 ... 
} 

Meine Frage ist, dass ich das Gefühl, dieser Prozess verschwenderisch scheint eine neue Liste von Nachbarn zu erstellen alle Zeit wird eine Zelle verarbeitet, zumal die Liste der Nachbarn nur einmal verwendet wird. Irgendwelche Vorschläge zum Umschreiben, um zu vermeiden, dass jedes Mal eine neue Liste erstellt wird - hauptsächlich, um die Tatsache auszunutzen, dass ich nur einmal pro Aufruf über die Nachbarn iterieren muss?

Answer 1

Irgendwelche Vorschläge, wie eine neue Liste zu vermeiden, neu zu schreiben, jedes Mal zu schaffen

Sie können die result Liste als Instanzvariable deklarieren. Auf diese Weise können Sie es löschen, jedes Mal beenden Sie über die Nachbarn Iterieren:

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

vor allem den Vorteil der Tatsache zu nehmen, dass ich nur über laufen die Nachbarn einmal pro Anruf?

Sie sollten Ihren Code vergleichen, um zu sehen, ob dies wirklich einen Leistungsvorteil gegenüber dem vorherigen Ansatz hat.

Answer 2

Ein funktioneller Ansatz könnte auch hier funktionieren; Ich bin nicht mit der tieferen Semantik von Java vertraut, aber so etwas wie:

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

Dies würde vermeiden neue Point-Objekte und eine neue Liste erstellen, während sie über die Nachbarn laufen. Aber auch hier ist nicht klar, dass dies zu erheblichen Einsparungen führen würde. Daher müsste ein Benchmarking durchgeführt werden, um festzustellen, ob es sich lohnt, auf diese Weise zu refaktorieren.