HashLife:压缩时间和空间的算法

HashLife-Tomas G.Rokicki，DDJ，2006年4月1日 压缩时间和空间的算法 通过Tomas G.Rokicki，2006年4月1日 快速执行缓慢的程序可能导致欢乐和沮丧。 但是有时，一种新方法会产生惊人的改进。 快速执行缓慢的程序可能导致欢乐和沮丧。 通常，您能做的最好的事情是做一个低级技巧，使程序速度提高一倍甚至四倍。 例如，许多读者可能已经使用位级操作实现了约翰·康威（John Conway）的“生命游戏”，从而显着提高了速度。 但是有时，将几个想法结合在一起的全新方法会带来惊人的改进。 威廉·高斯珀（William Gosper）发明了一种简单的算法“ HashLife”（ ），结合了四叉树和备忘录，从而为生活游戏带来了天文学的加速。 在本文中，我将最简单的Life实现演化为该算法，解释了它的工作原理，并在某些宇宙成长为数十亿个细胞时，为数万亿个世代运行。