游戏生活内存优化

Question

嗨，我写了一个简单的生命游戏代码，使用2个数组，一个维护当前状态，另一个维护下一个状态。有谁可以建议如何优化这个程序的内存消耗。理想情况下，我希望它的空间复杂度低于RC。

Answer 1

这取决于你的竞技场有多稀疏。如果你的游戏场是密集的，那么任何存储算法的空间复杂度都将趋向于RC。(具体地说，RC/2，因为一旦您获得了比非活动单元更多的活动单元，如果您真的非常关心最佳空间使用情况，则可以只存储非活动单元。)

如果游戏场是稀疏的，您可以通过简单地存储每个活动单元格或某些其他sparse matrix structure的坐标对来获得随活动单元格数量而缩放的内容。

Answer 2

我对GOL了解不多，但是假设有很多空的‘正方形’，你看过Sparse Matrixes吗

Answer 3

回答晚了，但还是。

请查看golly的源代码：http://golly.sourceforge.net/

但在此之前，请转到：http://www.ibiblio.org/lifepatterns/lifeapplet.html

然后看一下那里的代码。它是用Java编写的，但它非常非常快。

艾伦·亨塞尔网站上的这段话应该可以回答你的问题：

你是怎么让它跑得这么快的？好吧，普通的观察者可能没有注意到我的applet速度非常快。你可能没有找到“翘曲速度”按钮，或者你可能没有用过它，或者你可能对它没有印象。您可以跳到下一节。

然而，你们中的一些人会问，你们是怎么让它跑得这么快的？！对于好奇的人，或者那些想要编写自己的超快细胞自动机程序的人，我会解释一下。

我倾向于认为元胞自动机优化与数据压缩有关。这也是一个简单的概念，没有简单的解决方案，什么解决方案最好取决于正在处理的数据类型。在康威的生活中，模式往往是花花公子。

对于斑点宇宙，人们可能应该考虑将宇宙划分为大约与斑点大小相同的块。对于生活来说，4x4到8x8似乎是合理的。出于方便的原因，我选择了上限8x8 :一个字节恰好有8位。我强烈地考虑过4x4，但它的效果并不是很好...

你应该把这些块放在某种列表中，这样你就不会在宇宙的空虚部分浪费时间。

已经注意到一个复杂性:如果模式超出了块的边界，则必须在列表中引入新元素，但我们必须知道块的邻居是否已经存在。您可以对列表进行简单的线性搜索，也可以进行二进制搜索，或者保留某种映射。我选择做一个哈希表。这只用于查找新块的邻居；每个现有块都已经保留了一个指向其邻居的指针，因为它们将经常被引用。

在块中还必须有一个有效的算法。我选择直接直接通过每个区块。在处理完一个块中的所有单元格之前，没有内部循环。此外，还采用了快速查找表。我查找4x4块以确定内部的2x2。

注意: CA程序通常由两个主循环(外加一个显示循环)组成，因为CA规则在单元上并行操作，而微处理器在概念上是串行的。这意味着宇宙必须有两个副本，有效地，这样在创造下一代的过程中不会破坏任何重要的信息。通常这两个副本是不对称的。这对我来说是一个巨大的挣扎，因为几乎每次我从一个循环中删除一些东西来使它更快时，我必须在另一个循环中添加一些其他的东西！几乎每一次，也就是说，该规则的例外都会导致最佳优化。特别是，在位操作中需要考虑一些好的权衡:移位、掩码、重新组合以形成查找表中的地址……

还可以认为，有时块的内容可以稳定下来，不需要进一步的处理。您可以将该块从列表中删除，将其置于“休眠”状态，只有在相邻的块中有一些活动溢出时才会重新激活。这些块的处理时间为零，就像宇宙中的空白区域一样。

周期-2振荡器也可能不是很难检测到，并从处理时间中删除。这在生活中可能是值得的，因为眨眼是最常见的随机碎片。更高周期的振荡器要罕见得多。滑翔机也有可能被检测和模拟。您将从这种优化中获得递减的回报，除非您将其发挥到极致(参见。HashLife)。

此外，一个完全为空的单元格块可能在一段时间内不值得从散列表中释放和删除。这需要一些处理时间，在振荡器反复进出其空间的情况下，这可能是重要的。只有当内存不足时，才应该回收“停尸房”中最旧的块。

当程序足够快时，应该考虑到它不值得显示任何比肉眼所能看到的更快的世代，或者至少不比监视器的刷新率快太多。特别是在窗口环境中，显示时间可能是一个真正的瓶颈。

然后阅读这段源码：http://www.ibiblio.org/lifepatterns/src.41d/LifeCell.java

它包含保存Alan的生活世界的数据结构。

忘掉hashlife吧，它太复杂了，会让你头晕目眩。