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 时使用coordList 填充点并检查每个元素有多少邻居。当列表大小达到大约 10000 点时，每个周期大约需要 1 秒，而 20000 点则需要 7 秒。

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

Answer 1

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

除了声明之外，您的代码应该大部分保持不变，因为两者都实现了 Collection接口(interface)，除非您调用 List 特定的方法，例如 get(i)例如。