关于算法：优化Conway的“生命游戏”

Optimizing Conway's 'Game of Life'

为了进行试验，我(很久以前)实现了Conway的《人生游戏》(而且我知道这个相关问题！)。

我的实现通过保留2个布尔数组来表示"最后状态"和"状态正在更新"(每次迭代都交换2个数组)而工作。尽管这相当快，但我经常想知道如何优化它。

例如，一种想法是在迭代N处预先计算可以在迭代(N + 1)时修改的区域(这样，如果一个单元格不属于该区域，则甚至不考虑在该区域进行修改) 迭代(N + 1))。我知道这很模糊，而且我从来没有花时间去研究细节……

您对如何优化(速度)生命游戏迭代有任何想法(或经验！)？

我要引用另一个问题的答案，因为我提到的章节有一些非常有趣且经过微调的解决方案。是的，一些实现细节是用c和/或汇编语言编写的，是的，但是在大多数情况下，算法可以在任何语言下工作：

Chapters 17 and 18 of
Michael Abrash's Graphics
Programmer's Black Book are one of
the most interesting reads I have ever
had. It is a lesson in thinking
outside the box. The whole book is
great really, but the final optimized
solutions to the Game of Life are
incredible bits of programming.

有一些超快速的实现(从内存中)将8个或更多相邻正方形的单元表示为位模式，并使用它作为一大批预先计算的值的索引，以在单个机器指令中确定单元是活的还是死的。

在这里查看：

http://dotat.at/prog/life/life.html

还有XLife：

http://linux.maruhn.com/sec/xlife.html

您应该研究Hashlife，这是最终的优化。它使用了skinp提到的四叉树方法。

最有效的算法主要取决于初始状态。

如果大多数单元格已耗尽，则可以跳过空白部分而不用逐个单元地计算填充物，从而节省大量CPU时间。

我认为，当您的初始状态是"随机的，但生命机会低于5％"时，首先检查完全死的空间是有意义的。

我只是将矩阵分为两半，然后首先开始检查较大的矩阵。

因此，如果您的字段为10,000 * 10,000，则首先要累加左上四分之一状态5,000 * 5,000。

如果第一季度的状态总和为零，则您现在可以完全忽略第一季度的状态，然后检查右上角5,000 * 5,000的下一个生命。

如果其状态总和> 0，则现在将第二个四分之一再次分成4个部分-并对每个子空间重复此检查寿命。

您现在可以查看8 * 8或10 * 10的子帧(不确定在这里最有意义的子帧)。

只要找到生命，就将这些子空间标记为"具有生命"。

仅将"拥有生命"的空间划分为较小的子空间-可以跳过空的子空间。

当您为所有可能的子空间分配完"具有生命"属性后，最终将得到一个子空间列表，您现在只需将其向每个方向加+1即可扩展(带有空单元格)并执行常规(或修改后的)游戏他们的生活规则。

您可能会认为将10,000 * 10,000的空间划分为8 * 8的子空间是很多任务-但是累加它们的状态值实际上要比对每个单元格及其8个邻居执行GoL算法要少得多比较数字并将网络迭代的新状态存储在某处...

但是就像我上面说的，对于人口为30％的随机初始化状态，这没有多大意义，因为将找不到很多完全死掉的8 * 8子空间(仅留下死掉的256 * 256个子空间)

当然，完美优化的方式将持续但并非最不依赖于您的语言。

-110

该算法本身具有固有的可并行性。在未经优化的CUDA内核中使用相同的双缓冲方法，在4096x4096封装的世界中，我每代的时间大约为25ms。

两个想法：

(1)许多配置大多是空白空间。保留活动单元的链接列表(不一定要按顺序进行，这会花费更多时间)，并且在更新期间，仅在活动单元周围进行更新(这与您含糊的建议OysterD相似)

(2)保留一个额外的数组，该数组在3个位置(左-中-右)的每一行中存储活细胞数。现在，当您计算一个单元格的新的失效/有效值时，您仅需要4个读操作(顶部/底部行和中心位置)和4个写入操作(更新3个受影响的行摘要值，以及Dead /新单元格的实时价值)。假设写入速度不慢于读取速度，则与8次读取和1次写入相比，这是一个轻微的改进。我猜您可能会更聪明地使用此类配置，并在这些方面实现更好的改进。

正如Arbash的《黑皮书》中提到的那样，获得巨大加速的最简单直接的方法之一就是保留更改列表。

不必每次都遍历整个单元格网格，而保留所有更改单元格的副本。

这样可以缩小每次迭代中要做的工作。

我在C＃中实现了这一点：

所有单元格都有一个位置，一个邻居计数，一个状态以及对规则的访问。

将所有活细胞放入阵列A中的阵列B中。

让数组A中的所有单元格的邻居计数加1
邻居。

让数组A中的所有单元格将自己及其邻居放置在数组B中。

阵列B中的所有单元均根据规则及其状态进行更新。

数组B中的所有单元都将其邻居设置为0。

优点：

忽略不需要更新的单元格

缺点：

4个数组：用于网格的2d数组，用于活细胞的数组和一个数组
对于活跃的细胞。

无法处理规则B0。

一一处理单元格。

细胞不只是布尔值

可能的改进：

单元格也具有"已更新"值，仅当它们尚未更新时才更新
在当前报价中更新，从而消除了对数组B的需求，如上所述

数组B可以是
单元格没有，那些检查规则B0。

有表驱动的解决方案，可以解决每个表查找中的多个单元格。谷歌查询应该给你一些例子。

这是一个二维自动机，因此您可能可以查找优化技术。您的想法似乎与压缩每个步骤需要检查的单元格数量有关。由于您只需要检查被占用的单元格或与之相邻的单元格，也许您可??以保留所有此类单元格的缓冲区，并在处理每个单元格时在每个步骤进行更新。

如果您的字段最初为空，则速度会更快。您可能会发现一些平衡点，在这个平衡点上，维护缓冲区要比处理所有单元格花费更多。

不完全知道该怎么做，但是我记得我的一些朋友不得不用四叉树来代表游戏的网格。我猜这对于优化网格的空间确实很有用，因为您基本上只代表占用的单元格。我不知道执行速度。

Javascript中最短的实现之一：)

126字节的生活游戏引擎演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

/* The Game of Life function */
// @param s: current state of the grid
// @param d: size of the grid (d*d)
// @param n: placeholder
// @param k: placeholder
// @param m: placeholder
// @param i: placeholder
// @param j: placeholder
function(s, d, n, k, m, i, j){
for(
n = [], // Initialize next state
m = [d + 1, d, d - 1, 1], // Initialize the upper half of the neighbours indexes
i = d * d; // For each cell
i--;
n[i] = k == 3 || s[i] && k == 2, // Set next state (live if it has 3 neighbours or lives and has 2 neighbours)
k = 0 // Reset the count of living neighbours
)
for(j in m) // for each neighbour position
k += s[i + m[j]] + s[i - m[j]] // count the living neighbours
return(n) // return the next state
}