在 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 对象和新列表。但同样，目前尚不清楚这是否会节省大量成本，因此需要基准测试来确定是否值得以这种方式进行重构。