java在DFS/BFS算法中获取邻居时避免内存分配？

Question

我正在写一些代码，可以对网格映射进行DFS。我经常调用的一个函数是getNeights（…）它获取指定单元格的所有邻居：

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

功能性方法也可以在这里发挥作用；我不熟悉Java更深层次的语义，但类似于：

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

这将避免在迭代相邻对象时创建新的点对象和新列表。但同样，这是否会带来显著的节约还不清楚，因此需要进行基准测试，以确定是否值得以这种方式进行重构

Answer 2

Any suggestions for how to rewrite to avoid creating a new list each time

您可以将result列表声明为实例变量。这样，您可以在每次完成对邻居的迭代时清除它：

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

mainly to take advantage of the fact that I only need to iterate over the neighbors once per call?

您应该对您的代码进行基准测试，以查看与前面的方法相比，这是否真的具有性能优势