摘要：如果多核的機器如何優化因為是多核，我們可以用線程來實現并行計算。如果線程變多分塊變多，邊緣信息也會變多，開銷會增大。所以選取線程的數量是這個開銷和并行計算能力的折衷。

According to the Wikipedia"s article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970."
Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):
Any live cell with fewer than two live neighbors dies, as if caused by under-population. Any live cell with two or three live neighbors lives on to the next generation. Any live cell with more than three live neighbors dies, as if by over-population.. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction. Write a function to compute the next state (after one update) of the board given its current state.
Follow up:  Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells. In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?

時間 O(NN) 空間 O(1)

最簡單的方法是再建一個矩陣保存，不過當inplace解時，如果我們直接根據每個點周圍的存活數量來修改當前值，由于矩陣是順序遍歷的，這樣會影響到下一個點的計算。如何在修改值的同時又保證下一個點的計算不會被影響呢？實際上我們只要將值稍作編碼就行了，因為題目給出的是一個int矩陣，大有空間可以利用。這里我們假設對于某個點，值的含義為

0 : 上一輪是0，這一輪過后還是0
1 : 上一輪是1，這一輪過后還是1
2 : 上一輪是1，這一輪過后變為0
3 : 上一輪是0，這一輪過后變為1

這樣，對于一個節點來說，如果它周邊的點是1或者2，就說明那個點上一輪是活的。最后，在遍歷一遍數組，把我們編碼再解回去，即0和2都變回0，1和3都變回1，就行了。

注意編碼方式，1和3都是這一輪過后為1，這樣就可以用一個模2操作來直接解碼了

我實現的時候并沒有預先建立一個對應周圍8個點的數組，因為實際復雜度是一樣，多加幾個數組反而程序可讀性下降

public class Solution {
    public void gameOfLife(int[][] board) {
        int m = board.length, n = board[0].length;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                int lives = 0;
                // 判斷上邊
                if(i > 0){
                    lives += board[i - 1][j] == 1 || board[i - 1][j] == 2 ? 1 : 0;
                }
                // 判斷左邊
                if(j > 0){
                    lives += board[i][j - 1] == 1 || board[i][j - 1] == 2 ? 1 : 0;
                }
                // 判斷下邊
                if(i < m - 1){
                    lives += board[i + 1][j] == 1 || board[i + 1][j] == 2 ? 1 : 0;
                }
                // 判斷右邊
                if(j < n - 1){
                    lives += board[i][j + 1] == 1 || board[i][j + 1] == 2 ? 1 : 0;
                }
                // 判斷左上角
                if(i > 0 && j > 0){
                    lives += board[i - 1][j - 1] == 1 || board[i - 1][j - 1] == 2 ? 1 : 0;
                }
                //判斷右下角
                if(i < m - 1 && j < n - 1){
                    lives += board[i + 1][j + 1] == 1 || board[i + 1][j + 1] == 2 ? 1 : 0;
                }
                // 判斷右上角
                if(i > 0 && j < n - 1){
                    lives += board[i - 1][j + 1] == 1 || board[i - 1][j + 1] == 2 ? 1 : 0;
                }
                // 判斷左下角
                if(i < m - 1 && j > 0){
                    lives += board[i + 1][j - 1] == 1 || board[i + 1][j - 1] == 2 ? 1 : 0;
                }
                // 根據周邊存活數量更新當前點，結果是0和1的情況不用更新
                if(board[i][j] == 0 && lives == 3){
                    board[i][j] = 3;
                } else if(board[i][j] == 1){
                    if(lives < 2 || lives > 3) board[i][j] = 2;
                }
            }
        }
        // 解碼
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                board[i][j] = board[i][j] % 2;
            }
        }
    }
}

另一種編碼方式是位操作，將下輪該cell要變的值存入bit2中，然后還原的時候右移就行了。

public void solveInplaceBit(int[][] board){
        int m = board.length, n = board[0].length;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                int lives = 0;
                // 累加上下左右及四個角還有自身的值
                for(int y = Math.max(i - 1, 0); y <= Math.min(i + 1, m - 1); y++){
                    for(int x = Math.max(j - 1, 0); x <= Math.min(j + 1, n - 1); x++){
                        // 累加bit1的值
                        lives += board[y][x] & 1;
                    }
                }
                // 如果自己是活的，周邊有兩個活的，lives是3
                // 如果自己是死的，周邊有三個活的，lives是3
                // 如果自己是活的，周邊有三個活的，lives減自己是3
                if(lives == 3 || lives - board[i][j] == 3){
                    board[i][j] |= 2;
                }
            }
        }
        // 右移就是新的值
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                board[i][j] >>>= 1;
            }
        }
}

時間 O(NN) 空間 O(512)

上面的方法實測都比較慢，對于5000*5000的矩陣計算時間都在600-1000ms，甚至比簡單的用buffer的方法慢，我們再介紹一個能將速度提高一倍的方法。一般來說，優化程序有這么幾個思路：

盡量減少嵌套的循環

減少對內存的讀寫操作

上個解法中，使用多個for循環的就比較慢，如果我們能夠直接計算出該點的值而不用for循環就好了。這里我們可以用一個“環境”變量，表示該點所處的環境，這樣我們根據它以及它周圍八個點的值就可以直接算出它的環境值，而不需要用for循環來檢查周圍8個點。有人說，這不就只是把讀取操作放到循環外面來了嗎？其實這只是用了優化了第一點，減少循環，對于第二點我們也有優化，我們計算環境值這樣計算，對于以n4為中心的點，其環境為

n8  n5  n2
n7  n4  n1
n6  n3  n0

則環境值environment = n8 * 256 + n7 * 128 + n6 * 64 + n5 * 32 + n4 * 16 + n3 * 8 + n2 * 4 + n1 * 2 + n0 * 1，這么做的好處是把每一個格子的死活信息都用一個bit來表示，更巧妙地是當我們計算以n1為中心的環境時，是可以復用這些信息的，我們不用再讀取一遍n5, n4, n3, n2, n1, n0的值，直接將上一次的環境值模上64后再乘以8，就是可以將他們都向左平移一格，這時候再讀取三個新的值a, b, c就行了。

n8  n5  n2  a
n7  n4  n1  b
n6  n3  n0  c

通過這種方法，我們將內存的讀取次數從每個點九次，變成了每個點三次。另外我們還要預先制作一個表，來映射環境值和結果的關系。比如環境值為7時，說明n2, n1, n0都是活的，結果應該為1（下一輪活過來）。這里制作表的程序可以這么寫：

int[] table = new int[512];
for(int i = 0; i < 512; i++){
    int lives = Integer.bitCount(i);
    if(lives == 3 || (lives - ((i & 16) > 0 ? 1 : 0) == 3)){
        table[i] = 1;
    }
}

public void solveWithTable(int rounds, int[][] board){
    // 映射表
    int[] lookupTable = {0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
            0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0,
            0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1,
            0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0,
            0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0,
            0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0,
            0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1,
            1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0,
            0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0,
            0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
            0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,
            1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0,
            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
    int m = board.length, n = board[0].length;
    if(n == 0) return;
    int[][] buffer = new int[m][n];
    for(int i = 0; i < m; i++){
          // 每一行開始時，先計算初始的環境值（左邊兩列）
        int environment = (i - 1 >= 0 && board[i - 1][0] == 1? 4 : 0) + (board[i][0] == 1 ? 2 : 0) + (i + 1 < m && board[i + 1][0] == 1 ? 1 : 0);
            // 對該行的每一列，通過加入右邊新的一列，來計算該點的環境值
        for(int j = 0; j < n; j++){
                // 將之前的環境值模64再乘以8，然后加上右邊新的三列
            environment = (environment % 64) * 8 + (i - 1 >= 0 && j + 1 < n && board[i - 1][j + 1] == 1 ? 4 : 0) + (j + 1 < n && board[i][j + 1] == 1 ? 2 : 0) + (i + 1 < m && j + 1 < n && board[i + 1][j + 1] == 1 ? 1 : 0);
            buffer[i][j] = lookupTable[environment];
        }
    }
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            board[i][j] = buffer[i][j];
        }
    }
}

如果循環矩陣如何解決？循環的意思是假設一個3x3的矩陣,則a[0][0]的左邊是a[0][1]，其左上是a[2][2]
這樣我們的坐標要多加一個數組長度，使用坐標時還要取模

   public void solveInplaceCircular(int rounds, int[][] board){
       for(int round = 0; round < rounds; round++){
           int m = board.length, n = board[0].length;
           for(int i = 0; i < m; i++){
               for(int j = 0; j < n; j++){
                   int lives = 0;
                   // 多加一個數組長度
                   for(int y = i + m - 1; y <= i + m + 1; y++){
                       for(int x = j + n - 1; x <= j + n + 1; x++){
                           // 使用的時候要取模
                           lives += board[y % m][x % n] & 1;
                       }
                   }
                   if(lives == 3 || lives - board[i][j] == 3){
                       board[i][j] |= 2;
                   }
               }
           }
           for(int i = 0; i < m; i++){
               for(int j = 0; j < n; j++){
                   board[i][j] >>>= 1;
               }
           }
       }
   }

如果矩陣很大如何優化？
我們可以只記錄存活節點的信息，存入一個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的統計結果。

   1: class Mapper:
   2: method Map ():
   3: hash = ?
   4: for line ∈ stdin:
   5:     cell, state = Parse (line)
   6:     hash[cell] += state
   7:     for neighbor in Neighborhood (cell):
   8:         hash[neighbor] += 2*state
   9: for cell in hash:
   10:     strip-number = cell.row / strip-length
   11: Emit (cell, strip-number, hash[cell])
   
   1: class Reducer:
   2: method Reduce ():
   3: H = 0; last-cell = None
   4: for line ∈ stdin:
   5:     strip-number, current-cell, in-value = Parse (line);
   6:     if current-cell ≠ last-cell :
   7:         if last-cell ≠ None:
   8:             Emit (last-cell, state=F(E(H))
   9:         H = 0; last-cell = current-cell
   10:     H += in_value
   11: Emit (last-cell, state=F(E(xi))

如果整個圖都會變，有沒有更快的方法？
參見Hashlife，大意是用哈希記錄一下會重復循環的pattern

In Conway"s Game of Life, cells in a grid are used to simulate biological cells. Each cell is considered to be either alive or dead. At each step of the simulation each cell"s current status and number of living neighbors is used to determine the status of the cell during the following step of the simulation. 
In this one-dimensional version, there are N cells numbered 0 through N-1. The number of cells does not change at any point in the simulation. Each cell i is adjacent to cells i-1 and i+1. Here, the indices are taken modulo N meaning cells 0 and N-1 are also adjacent to eachother. At each step of the simulation, cells with exactly one living neighbor change their status (alive cells become dead, dead cells become alive). 
For example, if we represent dead cells with a "0" and living cells with a "1", consider the state with 8 cells: 01100101 Cells 0 and 6 have two living neighbors. Cells 1, 2, 3, and 4 have one living neighbor. Cells 5 and 7 have no living neighbors. Thus, at the next step of the simulation, the state would be: 00011101

時間 O(N) 空間 O()

一維數組需要考慮的情況更少，要注意的是這里頭和尾是相連的，所以在判斷其左右兩邊時要取模。

public void solveOneD(int[] board){
    int n = board.length;
    int[] buffer = new int[n];
    // 根據每個點左右鄰居更新該節點情況。
    for(int i = 0; i < n; i++){
        int lives = board[(i + n + 1) % n] + board[(i + n - 1) % n];
        if(lives == 1){
            buffer[i] = (board[i] + 1) % 2;
        } else {
            buffer[i] = board[i];
        }
    }
    for(int i = 0; i < n; i++){
        board[i] = buffer[i];
    }
}

In Place 一維解法

public void solveOneD(int rounds, int[] board){
    int n = board.length;
    for(int i = 0; i < n; i++){
        int lives = board[(i + n + 1) % n] % 2 + board[(i + n - 1) % n] % 2;
        if(lives == 1){
            board[i] = board[i] % 2 + 2;
        } else {
            board[i] = board[i];
        }
    }
    for(int i = 0; i < n; i++){
        board[i] = board[i] >= 2 ? (board[i] + 1) % 2 : board[i] % 2;
    }
}

時間 O(N) 空間 O()

和上題的表優化一個意思，不過這里用到了循環數組，并且規則不太一樣。

public void solveOneDWithTable(int[] board){
    int n = board.length;
    int[] lookupTable = {0, 1, 0, 1, 1, 0, 1, 0};
    int[] buffer = new int[n];
    int env = board[n - 1] * 2 + board[0] * 1;
    for(int i = 0; i < n; i++){
        env = (env % 4) * 2 + board[(i + n + 1) % n] * 1;
        buffer[i] = (lookupTable[env] + board[i]) % 2;
        System.out.println(env);
    }
    for(int i = 0; i < n; i++){
        board[i] = buffer[i];
    }
}