一维的hashlife

Posted by wyj on March 29, 2020

上次的AGC的B题我想了两个多小时,最后还是完全不会。当时我对着打的表,想了一大堆策略,比如Hashlife+压位+FFT+迭代$O(\log{N})$次消除$2$等等乱搞,然而在$10^6$的数据规模面前都没什么用。真的讨厌这种打表没用的观察结论题。前几天又心血来潮去搜索了一下“CSS是否图灵完全”,出乎意料地得到了肯定的回答:CSS可以用来模拟Rule 110。我才知道存在一个基本元胞自动机是图灵完全的,非常震惊。于是打算实现一个快速模拟基本元胞自动机的算法,不要让那两个多小时白费了。

算法

我心中的计划是hashlife的一维版本+压位+小数据打表加速。上次看过小机房里的美国小朋友跑的生命游戏的源码,大概也是这个思路。然而我并不知道Hashlife算法的具体细节,更别提把它魔改成一维的了。所以我先学习了一遍二维的Hashlife算法,发现这个东西是可以扩展到任意维度的,改成一维当然很简单。

算法内容如下:

  • 给定长度为$2^{k}$的序列$a$,记录$F(a)$表示$a$演化$2^{k-2}$次之后的$a’[2^{k-2}\dots 3\times 2^{k-2}-1]$,可以发现这个$F(a)$不会引用到$a$中未定义的元素。
  • 为了求出$F(a)$,可以考虑分成两步。先求出演化$2^{k-3}$次之后的$a’[2^{k-3}\dots 7\times 2^{k-3}-1]$,再演化$2^{k-3}$次得到答案。
  • 这两步都是可以递归解决的,第一步可以用3个长度为$2^{k-1}$序列的答案拼起来,第二步可以用两个长度为$2^{k-1}$序列的答案拼起来。具体细节可以看下面的python。
  • 用一个哈希表记忆化$F$。

可以用python描述一下(用python是因为它最接近伪代码并且很短):

def solve(a:list)->list:
	if len(a)<=4:
		return bruteforce(a)
	if hash(a) in mp:
		return mp[hash(a)]
	n1,n2=len(a)>>1,len(a)>>2
	x,y,z=solve(a[:n1]),solve(a[n2:n1+n2]),solve(a[n1:])
	return mp[hash(a)]:=solve(x+y)+solve(y+z)

实现

在我的C++实现中,递归边界不是4,而是2048。边界如此之大是因为我打表预处理了任何一个24位序列演化8次之后的中间8位(就是四毛子那一类思想)。并且暴力可以压位,在先除掉了一个64的前提之下还是跑的飞快。然而再快的暴力也只是暴力,边界开得更大就会变慢。

为了更加简洁地支持取子串与合并子串的操作,我按照惯例使用了std::basic_string。完全无法想象用std::vector会有多丑陋。

为了代码方便,我只处理了输入长度为$2^k$的序列,将两侧填充为无限多个0,然后输出演化$2^{k-1}$次之后的结果。这个对于我来说完全够用了。

源码在此

测试

基本元胞自动机一共有256个规则,本质不同的只有88种。Wolfram把这256个自动机分成了4类。

  • 第一类:收敛到稳定态
  • 第二类:进入循环
  • 第三类:对初始条件极度敏感的混沌系统
  • 第四类:兼备规律而稳定的行为与复杂的交互方式

第一类和第二类的自动机是相当无聊的,在我的测试中只需要0.3s以内就可以模拟长度为$2^{20}$的序列演化$2^{19}$步。有一个Wiki上面也提到了的例外:73号规则,这个规则的周期可以任意长,并且每个周期内的内容完全是混沌的,所以在我的测试中用时像第4类一样久。

我的程序完全不能处理任何一个第三类自动机,在这个情况下会退化成$O(n^2)$的暴力。这是因为Hashlife算法的原理是把不同时期不同位置的类似pattern统一处理,而一个混沌系统是基本找不到这样的相同子问题的。值得一提的是规则102,这就是那道题$\bmod 2$的情况,也是属于混沌系统,然而据我所知$k$阶差分除了FFT是没有什么办法的。

第四类自动机是最有趣的,许多这一类的规则都被猜想是具有通用计算能力,然而目前只有110号规则被证明了。这是和生命游戏最相似的一类,可以看成是一堆子结构的交互。hashlife算法可以记录下来各种子结构的演化与子结构之间交互的结果,所以具有很强大的加速效果。然而不会像一二类那样直接发现规律报告答案,所以长度为$2^{20}$的序列演化$2^{19}$步需要15秒到30秒左右,哈希表大概需要使用300MB的内存,取决于初始条件。我观察了一下搜索树节点个数与序列长度的关系,大概近似于$O(N\log N)$。