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

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

我的问题是，什么是更有效的方法？我知道还有其他几种类似的程序，它们的源代码也都有，但是我不能自己做很多，因为这个项目的目的是让我学习Java。另外，由于限制，我不想使用常规数组

Answer 1

就性能而言，我认为最好的选择是使用一个表示网格的纯数字（实际上是布尔）数组。由于这是一个学习练习，我将从一个简单的每个单元一个元素数组开始，然后可能会将八个相邻单元打包到一个字节中

你所说的“限制”是什么意思还不完全清楚

下面有一些有趣的提示：Optimizing Conway's 'Game of Life'

Answer 2

当前代码以二次方式扩展O(n^2)。你只提供了部分课程。如果你看一下你的整个程序，会有一个循环调用neighbors()，你会看到neighbors()被调用了n次。此外，操作contains（）在n中是线性的，因此时间与它们的乘积n*n成正比

二次缩放是一个常见问题，但通常可以通过使用HashSet等索引数据结构简化为线性

Answer 3

如果你的点是唯一的，你可以将它们存储在a ^{}而不是ArrayList中。在当前设置中，contains方法将变成一个O（1）操作，而不是O（n）。这将大大加快这一部分的速度

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