Count and say：一道力扣题目的进阶思考

Kagamia

窝是一个高产似那啥的新人

前情提要

最原始的题目出处在这里，是一个QQ好友问题。
好吧，就是我自己！我今天要做自己的破壁者！

题目如下：jianshu/p/831f57c7458b

挺无厘头的一个字符串，但是很显然（教科书参考答案的常见用语），把这个字符串补全，你应该获得这样一个网址：
  https://www.jianshu.com/p/831f57c7458b
完整的题目就在那里。

如今我是永远不会登录简书了，首先我不理解为什么它突然强制让我绑定手机号微信号；其次它的弹窗广告太多了，用户阅读体验极差。
但是我也不想把题目复制过来，篇幅太长了，烦劳您点击一下吧。

这道题目来自力扣https://leetcode.com/problems/count-and-say/，它的原始题目是求每一行的字符串本身，而我简化了问题，你只需要告诉我长度即可。
但是这个长度需要到2^35，大于32GiB。

想象中，如果生成第n行，你需要知道第n-1行，如果第n行要占32GB，那第n-1行大约也要32GB。理想地，这道题目可以在一台拥有64GB内存的机器上轻松计算出来。
放在现在，内存已经十分廉价，论坛中很多小伙伴的个人工作站都可以满足这个要求。
不过这道题目是5年前出的，当然5年前你也可以为了解这道题目，使用虚拟内存替代内存，使用外存替代内存，使用公家的内存，使用云主机搞这么多内存，whatever，不用思考地硬算，总有一天可以算出来。

目前真正算出来的群友大概少于5名，而我们亲爱的A5因为懒得计算，通过114514个宅币把我骗进论坛作为交易，成功by-pass了我的好友验证。
此时此刻，你算出来也不好使了。我已经准备把这道题目从QQ好友问答中清除掉了。
当下一个人成功计算出来的时候，我就会设计思索下一道题目。

如果你遇到了诸如算力不够、内存不够、复杂度太高等困难，这里我会给你一些非常非常概括性的提示。
我曾经实现过它（要不然我自己是怎么设置答案的），但是代码丢了，所以我就不放代码了。

或者，等我病好了在重新写一份实现，以飨诸君。


解题提示

使用任何你熟悉的语言，在最新的CPU上，你应该很容易瞬间计算S(78)之前的结果。
即使你使用vb，或是python，算个S(50) ~ S(70)应该不是什么难事
能够正确地编程实现，就算过了第一关。

但是到了后面，你会体验到这么几个问题：

• 每一行长度明显呈现指数级递增趋势
• 所以计算时间也是指数
• 所以内存占用也是指数
  

到了一个阈值，你的计算机程序或耐心至少有一个会崩溃。
即便如此，收集前面的每一行长度，你能获得这个指数底数的一个非常精确的解，甚至能精确到5位有效数字。这是hint1。

这件事很重要。为什么呢？因为它可以用来估算目标的n大致是多少，以便于你可以选择及时存档、分布式计算等策略。
在这个精度下，你估算出n的误差不会超过1。能够想到这一层，就算是过了第二关。

经过了长时间的鼓捣，你会发现每一行只会出现123三种数字，0和4都不会出现。你会想到使用位域压缩来解决内存问题。
又经过长时间的鼓捣，你会发现123这几种数字产生的组合序列也是有限种，你会根据已有数据构建一个状态机，遇到固定序列查表跳转，来解决算力不足问题。
但这都只压缩了常量系数，你依然可能卡在指数成长的复杂度上，有没有“质的飞跃”般的优化方法呢？


下面一件事就是我思路的重点：
你一定要一层层计算吗？

其实仔细想想，这件事大可不必。
我打个比方，比如说，你想写一个杨辉三角，我们使用左对齐方式，写出来大概这样
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
...
似乎按行写出来非常顺畅。
但是你有没有想过，如果指定让你写6行就OK，你是不是，其实，可以竖着写？


而Count and say这道题目，其实你也可以竖着写。和杨辉三角不同的是，因为指数级长度的出现，竖着写会越写越长。
比如，我们从第5行“111221”开始竖着写，写到第8行，大概顺序是这样的。

这张图画的比较草率，箭头的源是单元格，目的是红色方块，excel自带单元格用于相同数字组合。
按你胃(anyway)，如果看不懂就自己用自己喜欢的格式推导一遍，你立刻就理解为什么它可以竖着来。

为什么“可以纵向推导”这件事很重要呢？

• 这个算法可以适当并行，第二列底部没推导完，第三列顶部其实可以并行开工了，只要斜向箭头已构造出来就可以不停地链式计算。
  但你会说按行计算也可以并行吖，就是越往后越费内存，所以做不了并行。
  那么请看下一个理由。
• 纵向推导意味着，当你推导完一列后，黄色已完成区域，就可以从内存中丢掉了，你只要记录一个累计长度就够了。
  这样每一行只剩下“已处理长度”和“待处理尾部数据”是有意义的，而这部分数据，很短，甚至也就占10字节，连6502的寻址空间都足够把它跑完了。
  最后，这种实现的前提是，你需要提前指定目标层数，才能放心大胆地舍弃数据，如此一来，前面的思考就全都没有白费。
  

参考实现

比较接近真实的场合，我没有使用刚才手算的这么极端的纵向计算方法。
因为在多线程下，运算单元太小而锁太多，导致线程调度成本过高。
对应地，我其实使用“块”作为运算单元，使用“协程”让每一层计算可被随时中断，使用“队列”向下一层传递数据，使用“阻塞管道”传递数据就自动实现了中断。
噢，这听上去是不是适合用go实现？
是的，我就是用c#实现的。c#有自动编译成协程的yield和await，有从go那里inspire来的channel，有轻量级工作单元Task，零件齐全。
我只要实现这样一系列函数就够了：

struct Worker {
  public int LayerID;
  public long ProcessedLength;
  public byte LastChar;
  public byte LastCharLength;

  void HandleBlock(Span<byte> b);
  void HandleFinalBlock(Span<byte> b);
}
复制代码

最后用channel把全部worker串连起来并全部启动，剩下的就是找点游戏消磨时间了。
在5年前的配置上，我大概使用400MB左右的内存，使用4c8t的4代酷睿cpu，10分钟左右完成了答题任务。
放到现在的配置上，结合块匹配、查表修改状态等优化方式，可能一杯茶功夫计算S(100)也不在话下。

如果你有更好的方案，欢迎留言回复，交流使我成长。

Kagamia

今天我很闲，所以真的去实现了一下，用的是golang。

golang并不算是优秀到能跟上思维速度的语言，甚至连基础集合类和内存池都要自己造。
这一白天，我写了三种实现，分别是：

• 无脑写的，用于正确性校验。
• base V1，但是把逐字节计算改成了块计算，并添加了状态缓存。
  

  type CountSayV2 struct {
    stateCache map[StateCondition]StateOperation
  }
  
  type StateCondition struct {
    Input [blockSizeV2]byte
    LastByte byte
    LastByteCount byte
  }
  
  type StateOperation struct {
    Output []byte
    LastByte byte
    LastByteCount byte
  }
  复制代码

  
  golang里包含定长数组（注意是array不是slice）的结构体可以作为map的key，节省了我实现hashcode和equal方法的时间，但每次匹配都要浪费一次memcpy。
  选择这个blockSize其实很讲究，简单来说，blockSize较小会提高状态碰撞率，但对效率提升不显著；blockSize较大会降低碰撞率和查询效率，且导致状态表本身存储过大本末倒置，但是会显著压缩计算量。实际选择可以自己判断。
  这里给出一组我测得的数据：
  

  blockSize	layer	states	matchRate
  64	50	3833	91.675173
  64	60	4866	99.254468
  64	75	5133	99.985256
  256	50	6019	47.656318
  256	60	15195	90.686827
  256	75	21153	99.756964
  1024	50	2459	14.111072
  1024	60	22302	45.302038
  1024	75	72493	96.668350

  
  在动态缓存表的内存消耗可以接受的场合，确实是缓存匹配长度越大越好，使用72M的额外内存就可以命中96%的数据块组合瞬间给出结果。当然这里可以用LRU啥的算法控制，就不深究了。
  这是blockSize=1024, n=50的benchmark，5x faster。
    cpu: 13th Gen Intel(R) Core(TM) i7-13700K
    BenchmarkCountSay/v1-24              384           3088507 ns/op         3913661 B/op         29 allocs/op
    BenchmarkCountSay/v2-24             1929            570841 ns/op         3913643 B/op         29 allocs/op
    BenchmarkCountSay/v3-24              417           2854088 ns/op         3913640 B/op         29 allocs/op
• 基于正文“参考实现”的实现，每一行是一个独立运作的图灵机，从channel接收数据，把输出丢到下一行的channel去，但没用上v2的优化，单纯只面向并行。
  这里有一个迷你优化，我先用v1实现输出第50行数据，再用上面这个方法构建worker并行，这个分界线是通过对内存占用估算函数求极值获得的。
  和其他方案比，它有一个绝对优势：内存占用平均只有10-15M，这使得计算S(75)以上成为绝对可能。（v1和v2只会OOM）
  其次，它真正存在多核计算，但实际行为是诡异的cpu占用率间歇性变高然后持续走低，当前阶段我无法解释这件事。
  最后，它可以结合v2的状态机缓存成为更优解，我就不做实验了。
  

在我的i7-13700K工作站上，没有关闭windows defender，没有设置电源方案至高性能，没有深刻的GC优化，v3简陋版计算S90耗时1m25s，计算S100耗时26m15s。
用心优化一下，在5年前的配置上也可以轻松答题了。

0xAA55

啊！这题还真是得靠一步一步来试、找到问题（比如最初的 S(78) 往后每一行长度明显呈现指数级递增趋势），然后再去解决问题（收集前面的每一行长度，可以画出函数曲线，并根据曲线的走势进行预估）。

其实如果很仔细地用心思考的话，确实还是能够发现其实不用完全存储一行的字符串，而是我可以利用我这一行已经计算好的部分直接开始下一行的计算；而我这一行计算到头了以后我就可以把我不要的东西丢弃，以及我可以压缩数列的存储。

Kagamia

0xAA55 发表于 2023-5-13 12:33
啊！这题还真是得靠一步一步来试、找到问题（比如最初的 S(78) 往后每一行长度明显呈现指数级递增趋势）， ...

是的，全程每一件事都是在优化复杂度常量，而不是指数本身。
但是每一件事都做到，就可以数十倍提升效率，这就像是在游戏里获得了一件“需求等级降低20”特效的装备，用只能计算S80的硬件提前跑出S100来。

是一件特别有成就感的事。

0xAA55

Kagamia 发表于 2023-5-13 23:16
是的，全程每一件事都是在优化复杂度常量，而不是指数本身。
但是每一件事都做到，就可以数十倍提升效率 ...

与此同时 你也成为了全论坛拥有宅币最多的人，可喜可贺 可喜可贺

美俪女神

0xAA55 发表于 2023-5-15 19:17
与此同时 你也成为了全论坛拥有宅币最多的人，可喜可贺 可喜可贺

他的论坛币怎么会有这么多，充值了么？

misakarinkon

美俪女神 发表于 2023-5-17 08:53
他的论坛币怎么会有这么多，充值了么？

手动给她加的