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.

udalmik
  • 7,838
  • 26
  • 40
fredrol
  • 109
  • 3
  • 7

3 Answers3

1

If your points are unique, you could store them in a HashSet instead of an ArrayList. The contains method will then become an O(1) operation vs. O(n) in your current setup. That should speed up that section significantly.

Apart from the declaration, your code should remain mostly unchanged as both implement the Collection interface, unless you call List-specific method such as get(i) for example.

assylias
  • 321,522
  • 82
  • 660
  • 783
  • I will try it out, thanks! One questions about HashSet; does the index of the elements in it remain constant? I was planning to expand on the program in the future by having another list of objects which is linked by index. But perhaps that's not the proper way to do things like that? – fredrol Nov 22 '12 at 11:21
  • The points must be uniqe otherwise the code `coordList.contains(p)` would not give the correct number of neighbours. – Peter Nov 22 '12 at 11:29
  • 1
    The hashset uses indexes internally but the index changes when the hashset is resized and the indexes are not exposed by the api. – Peter Nov 22 '12 at 11:34
  • @fredrol No the index might (and will probably) change and you can't access an element by its index anyway. You could use a LinkedHashSet to preserve insertion order when iterating over the set. – assylias Nov 22 '12 at 12:06
1

Performance-wise, I think your best bet is to have a plain numeric (effectively Boolean) array representing the grid. Since this is a learning exercise, I'd start with a simple one-element-per-cell array, and then perhaps progress to packing eight adjacent cells into a single byte.

It is not entirely clear what you mean by "the limitations".

The following has some interesting pointers: Optimizing Conway's 'Game of Life'

Community
  • 1
  • 1
NPE
  • 486,780
  • 108
  • 951
  • 1,012
  • Thanks for your reply! With limitations I meant the scalability of arrays. If I'm not mistaken the size of the array is fixed and I want the numbers and coordinates of the cells to be able to grow without limitations. – fredrol Nov 22 '12 at 11:27
1

Your current code scales in a quadratic manner O(n^2). You have only given part of the program. If you look at your whole program there will be a loop that calls neighbors() and you will see that neighbors() is called n times. Also the operation contains() is linear in n, so the time is proportional to their product n*n.

Quadratic scaling is a common problem but can often be reduced to linear by using indexed data structures such as HashSet.

peter.murray.rust
  • 37,407
  • 44
  • 153
  • 217