在纯 numpy 中矢量化康威的生命游戏？

Question

我想知道是否有一种方法可以实现康威的生命游戏，而无需求助于 for 循环、if 语句和其他编程典型的控制结构。对循环进行矢量化应该很容易，但是如何将对邻域的检查转换为矩阵运算？

基本逻辑是这样的：

def neighbors(cell, distance=1):
    """Return the neighbors of cell."""
    x, y = cell
    r = xrange(0 - distance, 1 + distance)
    return ((x + i, y + j) # new cell offset from center
            for i in r for j in r # iterate over range in 2d
            if not i == j == 0) # exclude the center cell

我希望模组不会认为这是偏离主题的，我真的很好奇，而且我刚刚开始使用 CA。

干杯

Answer 1

您的问题的答案是“是的，这是可能的”（特别是板从板 n 更新到板 n+1）。

\n\n

I describe the process in detail here. The main technique to generate the neighborhood around a central cell involves using "strides" (the way that numpy and other array computation systems know how to walk across rows and columns of elements when they are really stored in memory in flat 1D thing) in a custom fashion to generate neighborhoods around cells. I describe that process here.

\n\n

One last comment: since Game of Life iterates from state n to state n+1, while you could literally remove all imperative looping, it doesn\'t really make sense to take out that top-level control loop. So, has a loop: for round in range(num_rounds): board.update() where board.update doesn\'t use loops (except to do some side calculations ... again, you could remove those but it would make the program longer and less elegant).

\n\n

To give you a concrete example (and be more compatible with StackOverflow\'s answer requirements), here\'s some select cutting and pasting from my posts to generate the central neighborhoods from a simple 4x4 board [apologies, this is python 2 code, you\'ll have to modify the prints a bit]:

\n\n

board = np.arange(16).reshape((4,4))\nprint board\nprint board.shape\n

\n\n

We want to pick out the four "complete" neighborhoods centered around 5, 6, 7, and 8. Let\xe2\x80\x99s look at the neighborhood for 5. What is the shape of the result? 3\xc3\x973. What are the strides? Well, to walk across a row is still just walking one element at a time and to get to the next row is still 4 elements at a time. These are the same as the strides in the original. The difference is we don\xe2\x80\x99t take "everything", we just take a selection. Let\xe2\x80\x99s see if that actually works:

\n\n

from numpy.lib.stride_tricks import as_strided\nneighbors = as_strided(board, shape=(3,3), strides=board.strides)\nprint neighbors\n

\n\n

Ok, nice. Now, if we want all four neighborhoods, what is the output shape? We have several 3\xc3\x973 results. How many? In this case, we have 2\xc3\x972 of them (for each of the "center" cells). This gives a shape of (2,2,3,3) \xe2\x80\x93 the neighborhoods are the inner dimensions and the organization of the neighborhoods is the outer dimensions.

\n\n

\n\n

So, our strides (in terms of elements) end up being (4,0) within one neighborhood and (4,0) for progressing neighborhood to neighborhood. The total stride (element wise) is: (4,0,4,0). But, the component strides (our outer two dimensions) are the same as the strides of the board. This means that our neighborhood strides are board.strides + board.strides.

\n\n

print board.strides + board.strides\n\nneighborhoods = as_strided(board, \n                           shape=(2,2,3,3), \n                           strides=board.strides+board.strides)\n\nprint neighborhoods[0,0]\nprint neighborhoods[-1, -1]\n

\n