Избегайте выделения памяти при получении соседей в алгоритме 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 ... 
} 

Мой вопрос заключается в том, что я чувствую этот процесс кажется расточительным, чтобы создать новый список соседей каждый время обработки ячейки, тем более, что список соседей используется один раз. Любые предложения о том, как переписать, чтобы избежать создания нового списка каждый раз - в основном, чтобы воспользоваться тем фактом, что мне нужно только перебирать соседей один раз за звонок?

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, и новый списка, в то время как итерация соседей. Но опять же, неясно, что это обеспечило бы значительную экономию, поэтому для определения того, стоит ли рефакторировать таким образом, потребуется бенчмаркинг.