java - 查找 ArrayList 中点的邻居

Question

我最近开始学习 Java，不过从做一个“Conway's Game of Life”风格的程序开始是一件好事。一切工作正常，但我在这部分遇到了一些严重的性能问题:

static List<Point> coordList = new ArrayList<Point>();

public int neighbors(int x, int y){

    int n = 0;

    Point[] tempArray = { new Point(x-1, y-1), new Point(x, y-1), new Point(x+1, y-1), 
                          new Point(x-1, y  ),                    new Point(x+1, y  ),
                          new Point(x-1, y+1), new Point(x, y+1), new Point(x+1, y+1)};
    for (Point p : tempArray) {
        if (coordList.contains(p))
            n++;
        }

    return n;
}

当迭代填充有点的ArrayListcoordList并检查每个元素有多少个邻居时，使用该方法。当列表大小达到大约 10000 点时，每个周期大约需要 1 秒，而对于 20000 点则需要 7 秒。

我的问题是，更有效的方法是什么？我知道还有其他几个此类程序也提供源代码，但我不想自己做尽可能多的事情，因为该项目的重点是我学习 Java。另外，由于限制，我不想使用常规数组。

Answer 1

如果您的积分是唯一的，您可以将它们存储在a HashSet中而不是ArrayList。然后，contains 方法将变成 O(1) 操作，而当前设置中的操作则为 O(n)。这应该会显着加快该部分的速度。

除了声明之外，您的代码应该保持基本不变，因为它们都实现了 Collection 接口(interface)，除非您调用特定于 List 的方法，例如 get(i) .