2

I've recently started learning Java and though doing a "Conway's Game of Life" style program would be a good thing to start out with. Everything works fine but I'm having some serious performance issues with this part:

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

The method is used when iterating the ArrayList coordList filled with Points and checking every element how many neighbors they have. When the list size gets to about 10000 Points every cycle takes about 1 seconds and for 20000 Points it takes 7 seconds.

My question is, what would be a more effective way to do this? I know there are several other programs of this kind with source code available too look at, but I wan't do do as much as I can by my self since the point of the project is me learning Java. Also, I don't want to use a regular array because of the limitations.

4

3 回答 3

1

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

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

于 2012-11-22T11:13:59.370 回答
1

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

尚不完全清楚您所说的“限制”是什么意思。

下面有一些有趣的指点：优化康威的“生命游戏”

于 2012-11-22T11:16:36.693 回答
1

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

二次缩放是一个常见问题，但通常可以通过使用索引数据结构（例如HashSet.

于 2012-11-22T11:24:35.273 回答