康维生活的低成本使用效果是什么？ [英] What's an efficient implementation of Conway's Game of Life for low memory uses?
问题描述
限制：一个96x128的电路板，大约2kB的RAM可用和52MHz的处理器（请参阅这里的技术规格： http://www.getinpulse.com/features ）。
我目前的将每个单元格表示为矩阵中单个位的天真解决方案（96 * 128/8 = 1,536字节）有效，但速度太慢。可以使用什么技巧来提高性能？
存储活细胞的坐标（例如在这个实现中 http://dotat.at/prog/life/life.html ）会使用太多的内存。
看起来像一个有趣的硬件。
存储96×128像素显示器的每像素1位，提供12,288位。
这个已经超过16,384位的一半，你说是可用。
如果你甚至不能每个单元格存储2位，那么没有太多的空间。
几个想法：
-
您有一个32位处理器。在这样一个处理器上并行计算几个单元格的邻居数量有几个比特的技巧。
-
存储速度通常更快邻居计数，在出生时增加所有8个邻居，并在死亡时递减所有8个邻居，而不是每一代从头开始重新计算邻居的数量 - 但是它似乎没有足够的内存用于此方法。
-
也许您可以在每个单元格中使用2x2像素（因此只有3,072个单元格可见）或每个单元格3x3像素（因此只有1376个单元格可见），因此您的软件工作量较少给出运行更快的错觉。 （这也释放了足够的RAM，你可以做上面提到的邻居计数）。
-
由于许多生活模式都有大面积的死空间， 活地区的小位图 - 比如说，一个12x16位数组，如果对应的8x8单元区域完全死了，其中每个位都为0，如果相应区域中的任何一个单元格都存在，则为1。下一代更新只需要看活地区和死亡地区的1个小区的边界;您可以跳过检查死区的6x6单元核心。此外，如果4个最近邻区也已经死亡，那么可以完全跳过整个8x8单元格区域。
-
由于许多生命模式具有大面积的静态不变静态生活模式，也许有一个动态区域的小位图 - 比如说，一个12x16位数组，如果相应的8x8单元格区域在上一代更新中没有变化，那么每个位为0，而1 如果上一次更新中相应区域中的任何单元格发生更改。下一代更新只需要查看动态区域和静态区域的1单元格范围的边界;您可以跳过检查静态区域的6x6单元格核心，因为下一代将是相同的。
-
如果模式足够大基于Gosper's Hashlife的表示可以将其存储在比直接存储位图更少的RAM中。唉，我怀疑你远远低于足够大的门槛。
I'm looking for a fast and memory efficient approach for implementing Conway's Game of Life.
Constraints: a 96x128 board, approximately 2kB RAM available and 52MHz processor (see the tech specs here: http://www.getinpulse.com/features).
My current naive solution that represents each cell as a single bit in a matrix (96*128/8=1,536 bytes) works but is too slow. What tricks can be used to improve performance?
Storing the coordinates of live cells (for example in this implementation http://dotat.at/prog/life/life.html) would use too much memory.
Looks like a fun piece of hardware. Storing 1 bit per pixel of a 96x128 pixel display gives 12,288 bits. That's already over half of the 16,384 bits you say are "available". If you can't even store 2 bits per cell, there's not a lot of room to do much.
A few ideas:
You have a 32-bit processor. There are several bit-twiddling tricks to take a bitmap and calculate the number of neighbors of several cells in parallel on such a processor.
It's often faster to store the neighbor counts, incrementing all 8 neighbors at birth and decrementing all 8 neighbors at death, rather than recalculating the number of neighbors from scratch every generation -- but it doesn't look like you have enough memory for this approach.
Perhaps you could use 2x2 pixels per cell (so only 3,072 cells visible) or 3x3 pixels per cell (so only 1,376 cells visible), so your software does less work and so gives the illusion of running faster. (This also frees up enough RAM that you can do the neighbor count mentioned above).
Since many life patterns have large areas of dead space, perhaps have a small bitmap of "live regions" -- say, a 12x16 array of bits, where each bit is "0" if the corresponding 8x8 cell region is entirely dead, and "1" if any of the cells in the corresponding region is alive. The next-generation update only needs to look at live regions and the 1-cell-wide border of dead regions; you can skip checking the 6x6 cell core of dead regions. Also, you can completely skip the entire 8x8 cell region if its 4 nearest neighboring regions are also dead.
Since many life patterns have large areas of static unchanging "still life" patterns, perhaps have a small bitmap of "dynamic regions" -- say, a 12x16 array of bits, where each bit is "0" if the corresponding 8x8 cell region had no changes in the last generation update, and "1" if any of the cells in the corresponding region changed in the last update. The next generation update only needs to look at dynamic regions and the 1-cell-wide border of static regions; you can skip checking the 6x6 cell core of static regions, since it will be the same in the next generation.
If a pattern is "large enough", a representation based on Gosper's Hashlife may be able to store it in less RAM than storing a bitmap directly. Alas, I suspect you're far below the "large enough" threshold.
这篇关于康维生活的低成本使用效果是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
