Count and say：一道力扣题目的进阶思考
本帖最后由 Kagamia 于 2023-5-13 01:07 编辑窝是一个高产似那啥的新人{:4_112:}
前情提要
最原始的题目出处在这里，是一个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)也不在话下。
如果你有更好的方案，欢迎留言回复，交流使我成长。 今天我很闲，所以真的去实现了一下，用的是golang。
golang并不算是优秀到能跟上思维速度的语言，甚至连基础集合类和内存池都要自己造。
这一白天，我写了三种实现，分别是：
[*]无脑写的，用于正确性校验。
[*]base V1，但是把逐字节计算改成了块计算，并添加了状态缓存。
type CountSayV2 struct {
stateCache mapStateOperation
}
type StateCondition struct {
Input 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较大会降低碰撞率和查询效率，且导致状态表本身存储过大本末倒置，但是会显著压缩计算量。实际选择可以自己判断。
这里给出一组我测得的数据：
blockSizelayerstatesmatchRate
6450383391.675173
6460486699.254468
6475513399.985256
25650601947.656318
256601519590.686827
256752115399.756964
102450245914.111072
1024602230245.302038
1024757249396.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年前的配置上也可以轻松答题了。 啊！这题还真是得靠一步一步来试、找到问题（比如最初的 S(78) 往后每一行长度明显呈现指数级递增趋势），然后再去解决问题（收集前面的每一行长度，可以画出函数曲线，并根据曲线的走势进行预估）。
其实如果很仔细地用心思考的话，确实还是能够发现其实不用完全存储一行的字符串，而是我可以利用我这一行已经计算好的部分直接开始下一行的计算；而我这一行计算到头了以后我就可以把我不要的东西丢弃，以及我可以压缩数列的存储。
0xAA55 发表于 2023-5-13 12:33
啊！这题还真是得靠一步一步来试、找到问题（比如最初的 S(78) 往后每一行长度明显呈现指数级递增趋势）， ...
是的，全程每一件事都是在优化复杂度常量，而不是指数本身。
但是每一件事都做到，就可以数十倍提升效率，这就像是在游戏里获得了一件“需求等级降低20”特效的装备，用只能计算S80的硬件提前跑出S100来。
是一件特别有成就感的事。 Kagamia 发表于 2023-5-13 23:16
是的，全程每一件事都是在优化复杂度常量，而不是指数本身。
但是每一件事都做到，就可以数十倍提升效率 ...
与此同时 你也成为了全论坛拥有宅币最多的人，可喜可贺 可喜可贺 0xAA55 发表于 2023-5-15 19:17
与此同时 你也成为了全论坛拥有宅币最多的人，可喜可贺 可喜可贺
他的论坛币怎么会有这么多，充值了么？ 美俪女神 发表于 2023-5-17 08:53
他的论坛币怎么会有这么多，充值了么？
手动给她加的:)
页:
[1]