嗨，我编写了一个简单的生命代码游戏，它使用 2 个数组，一个保持当前状态，另一个保持下一个状态。任何人都可以建议如何优化这个程序的内存消耗。理想情况下，我希望它的空间复杂度低于 RC。
问问题
2017 次
5 回答
4
这取决于你的比赛场地有多稀疏。如果你的竞争环境很密集，那么任何存储算法的空间复杂度都会趋向于 RC。（特别是 RC/2，因为一旦您获得的活动单元比非活动单元多，如果您真的非常关心最佳空间使用，则可以只存储非活动单元。）
如果比赛场地很稀疏，您可以通过简单地存储每个活动单元格的坐标对或其他一些稀疏矩阵结构来获得与活动单元格数量成比例的东西。
于 2010-08-24T08:12:09.337 回答
2
我对 GOL 了解不多，但假设有很多空的“正方形”，你看过Sparse Matrixes吗？
于 2010-08-24T08:11:55.547 回答
1
迟到的答案，但仍然。
查看 golly 的源代码：http: //golly.sourceforge.net/
但在您这样做之前，请访问：http
://www.ibiblio.org/lifepatterns/lifeapplet.html
并查看那里的代码。它是用 Java 编写的，但速度非常快。
Alan Hensel 网站上的这句话应该可以回答您的问题：
你是怎么让它跑得这么快的？好吧，不经意的观察者可能不会注意到我的小程序非常快。您可能没有找到“Warp Speed”按钮，或者您可能没有使用它，或者您可能对它没有印象。您可以跳到下一部分。
然而，你们中的一些人已经问了，你怎么搞得这么快？！对于好奇的人，或者那些想编写自己的超快速元胞自动机程序的人，我会解释一下。
我倾向于认为元胞自动机优化与数据压缩有关。这也是一个简单的概念，没有简单的解决方案，什么解决方案最好取决于正在处理的数据类型。在康威的生活中，模式往往是斑点状的。
对于斑点宇宙，人们可能应该考虑将宇宙分成大约与斑点大小相同的块。对于 Life，4x4 到 8x8 似乎是合理的。为方便起见，我选择了上限 8x8：一个字节恰好有 8 位。我强烈考虑过 4x4，但效果并不好....
您应该将块放在某种列表中，这样您就可以在宇宙的空白部分浪费零时间。
已经注意到一个复杂的问题：如果模式超出块的边界，则必须在列表中引入新元素，但我们必须知道块的邻居是否已经存在。您可以对列表进行简单的线性搜索，也可以进行二分搜索，或者保留某种地图。我选择制作一个哈希表。这仅用于查找新块的邻居；每个现有块都已经保存了指向其邻居的指针，因为它们将经常被引用。
块内还必须有一个有效的算法。我选择主要是直接穿过每个街区。在处理块中的所有单元之前没有内部循环。此外，还使用了快速查找表。我查找 4x4 块以确定内部 2x2。
注意：CA 程序通常由 2 个主循环（加上一个显示循环）组成，因为 CA 规则在单元上并行运行，而微处理器在概念上是串行的。这意味着必须有两个有效的宇宙副本，以便在创建下一代的过程中不会破坏任何重要信息。通常这两个副本不是对称的。这对我来说是一场巨大的斗争，因为几乎每次我从一个循环中取出一些东西以使其更快时，我都必须在另一个循环中添加其他东西！几乎每次，就是；该规则的例外导致最佳优化。特别是，在位操作中需要考虑良好的权衡：移位、屏蔽、重新组合以在查找表中形成地址......
也可以认为，有时块的内容可能会稳定，不需要进一步处理。您可以将块从列表中取出，使其处于“休眠”状态，只有在相邻块有一些活动溢出时才会重新激活。这些块将需要零处理时间，就像宇宙的空白区域一样。
周期 2 振荡器也可能不是很难检测到，并且从处理时间中移除。这在生活中可能是值得的，因为闪光灯是最常见的随机碎片。更高周期的振荡器更为罕见。也有可能检测和模拟滑翔机。您将从这种优化中获得递减的回报，除非您将其发挥到极致（参见 HashLife）。
此外，一个完全空的单元格块可能暂时不值得从哈希表中释放和删除。这需要一些处理时间，这在振荡器反复进出其空间的情况下可能很重要。只有当内存不足时，才应回收“停尸房”中最旧的块。
当程序足够快时，应该考虑到显示几代的速度超过肉眼可见的速度，或者至少不比显示器的刷新率快多少。尤其是在窗口环境中，显示时间可能是一个真正的瓶颈。
然后阅读这段源代码：http
://www.ibiblio.org/lifepatterns/src.41d/LifeCell.java
它包含保存艾伦生命宇宙的数据结构。
忘记 hashlife，它太复杂了，会让你头晕目眩。
于 2011-05-28T23:00:48.257 回答
0
其他回答者在为您的州寻找其他数据结构方面有很好的意义。但不管怎样，一个简单的优化可能会使用两个指向状态的指针（您可能已经这样做了）。所以不是做两个数组副本，而是做一个副本和三个指针分配：
state curr, next;
[...]
for (;;) {
next = advance(curr);
curr = copy(next);
}
对此：
state s1, s2;
state *curr, *next;
[...]
for (;;) {
*next = advance(*curr);
/* swap pointers */
state *tmp = curr;
curr = next;
next = tmp;
}
于 2010-08-24T08:26:50.517 回答
0
我推荐稀疏矩阵，正如 nonnb 和 Amber 推荐的那样。如果您有可烧毁的处理器能力或想要序列化到磁盘，您也可以研究编码。RLE 或基于令牌的压缩可能会让您有所收获。
于 2010-08-24T08:28:40.337 回答