Game of Life问题研究 (Snapchat)

分析

暴力法，我们可以直接用另外一个矩阵来保存新的状态。

这样空间复杂度有点高，如何in-place来做呢？ 可以用编码法，因为是一个array的数组，可以自定义两个新的状态表示变化。 2 - 表示之前是1 现在变成了0，这样 %2 可以直接获得新状态。 3 - 表示之前是0 现在变成了1

public void gameOfLife(int[][] board) {
    if(board == null || board.length == 0 || board[0].length == 0) {
        return;
    }
    // 0: 0 -> 0 
    // 1: 1 -> 1
    // 2: 1 -> 0
    // 3: 0 -> 1

    // 一个元素的八个方向 
    int[] dx = {0,1,-1,0,-1,1,1,-1};
    int[] dy = {1,0,0,-1,-1,1,-1,1};

    for(int i = 0; i < board.length; i++) {
        for(int j = 0; j < board[0].length; j++) {
            int lives = 0;
            for(int k = 0; k < 8; k++) {
                int x = i + dx[k];
                int y = j + dy[k];

                if(x < 0 || y < 0 || x >= board.length || y >= board[0].length) {
                    continue;
                }
                lives += board[x][y] == 1 || board[x][y] == 2 ? 1 : 0;
            }

            if(lives < 2 || lives > 3) {
                board[i][j] = board[i][j] == 1 ? 2 : 0;
            } else if(board[i][j] == 0 && lives == 3) {
                board[i][j] = 3;
            }
        }
    }

    for(int i = 0; i < board.length; i++) {
        for(int j = 0; j < board[0].length; j++) {
            board[i][j] %= 2;
        }
    }

}

如果矩阵很大如何优化？

我们可以只记录存活节点的信息，存入一个live的list中，这里active代表着存活节点，或者存活节点的邻居。每次只计算这个list中节点和其邻居的情况。进一步优化的话，我们可以用一个active的list，只记录上次更新的节点，或者该节点的邻居。等计算完这个列表后，将产生更新的节点和它的邻居们存入一个新列表中，再用这个新列表里节点的值来更新矩阵。下一轮时，就计算这个新列表，再产生一个新列表。

如果多核的机器如何优化？

因为是多核，我们可以用线程来实现并行计算。如图，将矩阵分块后，每个线程只负责其所在的分块的计算，不过主线程每一轮都要更新一下这些分块的 边缘，并提供给相邻分块。所以这里的开销就是主线程和子线程通信这个边缘信息的开销。如果线程变多分块变多，边缘信息也会变多，开销会增大。所以选取线程的数量是这个开销和并行计算能力的折衷。

如果是多台机器如何优化？

同样的，我们可以用一个主机器负责处理边缘信息，而多个子机器处理每个分块的信息，因为是分布式的，我们的矩阵可以分块的存储在不同机器的内存中，这样矩阵就可以很大。而主机在每一轮开始时，将边缘信息通过网络发送给哥哥分块机器，然后分块机器计算好自己的分块后，把新自己内边缘信息反馈给主机器。下一轮，等主机器收集齐所有边缘后，就可以继续重复。

不过多台机器时还有一个更好的方法，就是使用Map Reduce。Map Reduce的简单版本是这样的，首先我们的Mapper读入一个file，这个file中每一行代表一个存活的节点的坐标，然后Mapper做出9个Key-Value对，对这个存活节点的邻居cell，分发出一个1。而对于节点自身，也要分发出一个1。这里Reducer是对应每个cell的，每个reducer累加自己cell得到了多少个1，就知道自己的cell周围有多少存活cell，就能知道该cell下一轮是否可以存活，如果可以存活则分发回mapper的文件中，等待下次读取，如果不能则舍弃。

如果要进一步优化Map Reduce，那我们主要优化的地方则是mapper和reducer通信的开销，因为对于每个存活节点，mapper都要向9个reducer发一次信息。我们可以在mapper中用一个哈希表，当mapper读取文件的某一行时，先不向9个reducer发送信息，而是以这9个cell作为key，将1累加入哈希表中。这样等mapper读完文件后，再把哈希表中的cell和该cell对应的累加1次数，分发给相应cell的reducer，这样就可以减少一些通信开销。相当于是现在mapper内做了一次累加。这种优化在只有一个mapper是无效的，因为这就等于直接在mapper中统计完了，但是如果多个mapper同时执行时，相当于在每个mapper里先统计一会，再交给reducer一起统计每个mapper的统计结果。