首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >在低内存使用情况下,Conway's Game of Life的有效实现是什么?

问在低内存使用情况下,Conway's Game of Life的有效实现是什么?
EN

Stack Overflow用户
提问于 2011-02-21 04:32:21
回答 6查看 5.4K关注 0票数 13

我正在寻找一种快速和内存高效的方法来实现Conway的生活游戏。

限制: 96x128电路板,大约2kB内存和52 the处理器(请参阅此处的技术规格:http://www.getinpulse.com/features)。

我目前的简单解决方案将每个单元表示为矩阵中的单个位(96*128/8=1,536字节),虽然有效,但速度太慢。可以使用哪些技巧来提高性能?

存储活动单元格的坐标(例如,在此实现中为http://dotat.at/prog/life/life.html)将占用太多内存。

EN

回答 6

Stack Overflow用户

回答已采纳

发布于 2011-02-21 14:40:06

看起来像是一个有趣的硬件。96×128像素显示器的每像素存储1位可得到12,288位。这已经超过了你所说的16,384位中“可用”位的一半。如果你甚至不能在每个单元中存储2位,那么就没有多少空间可以做很多事情了。

以下是一些想法:

  • 你有一个32位的处理器。在这样的processor.
  • It's上并行地获取位图并计算几个单元的邻居数有几个花招,通常可以更快地存储邻居计数,在出生时递增所有8个邻居,在死亡时递减所有8个邻居,而不是每代从头开始重新计算邻居数--但是对于这个approach.
  • Perhaps,您看起来没有足够的内存,您可以使用每个单元2x2像素(因此只有3,072个单元可见)或3x3像素(因此只有1,376个单元可见),因此您的软件做的工作更少,因此给人一种运行更快的错觉。
  • 因为许多生命模式有很大的死区,所以可能有一个很小的“活动区域”位图--比方说,12x16位数组,其中如果相应的8x8单元区域完全死了,则每个位都是"0“,如果相应区域中的任何单元都是活的,则每个位都是"1”。下一代更新只需要查看活动区域和死区的1个单元宽的边界;您可以跳过检查死区的6x6单元核心。此外,如果最近的4个8x8单元区域也是死的,则可以完全跳过整个8x8单元区域。
  • 由于许多生命模式具有大量静态不变的“静止”模式,因此可能有一个小的“动态区域”位图--比方说,12x16位数组,其中如果相应的8x8单元区域在上一代更新中没有变化,则每一位为"0“,如果相应区域中的任何单元在上一次更新中发生变化,则为"1”。下一代更新只需要查看动态区域和静态区域的1个单元宽的边界;您可以跳过检查静态区域的6x6单元核心,因为它将在下一个generation.
  • If中相同。如果一个模式“足够大”,基于Gosper的Hashlife的表示可能能够将其存储在比直接存储位图更少的内存中。唉,我怀疑你远远低于“足够大”的门槛。--
票数 9
EN

Stack Overflow用户

发布于 2011-02-21 20:20:10

对于小的生命宇宙来说,让它们在所有的边都被包裹起来(形成一个环形的宇宙)是很常见的,但这需要双重缓冲。在您的情况下,这需要3KB的RAM,但您只有2KB。

如果你不包装,那么你就不需要对整个宇宙进行双缓冲。您只需避免在将单元格用作计算输入之前覆盖这些单元格。

假设你的宇宙是以传统的位图布局的。我们将其视为在内存中按顺序排列的一系列行。假设宇宙有四行,编号为0到3。

代码语言:javascript
复制
  0
  1
  2
  3
  4
  ...

计算下一代时,将使用第2、3和4行(为空)计算第3行的新版本。您可以在第4行的顶部写入新版本的第3行。同样,从第1、2、3行计算新行2并将其写入第3行,因为在计算第2行后不再需要该数据。新行1是从第0、1、2行计算出来的,并覆盖第2行。

这意味着您只需要为额外的一行存储空间。97*128位是1552字节。

缺点是你的世界在内存中滚动,你必须有一些机制来处理这一点。或者在每次计算后将其复制回其原始位置(这很慢),或者安排为能够从内存中的任何位置显示它,并确保您的计算和显示系统可以从高地址到低地址回绕。

票数 2
EN

Stack Overflow用户

发布于 2011-02-22 04:12:12

看看Michael Abrash在"The Zen of Code Optimization"中关于生活的游戏的章节。有一种实现将3个单元的当前和先前状态编码到单个字中,并使用查找表和进位位的技巧来生成下一状态。它的速度非常快。

票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/5059817

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档