找回密码
 立即注册→加入我们

QQ登录

只需一步,快速开始

搜索
热搜: 下载 VB C 实现 编写
查看: 411|回复: 6

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

[复制链接]

2

主题

5

回帖

11万

积分

用户组: 技术宅的结界VIP成员

UID
8229
精华
2
威望
84 点
宅币
114696 个
贡献
80 次
宅之契约
0 份
在线时间
9 小时
注册时间
2023-2-9
发表于 2023-5-13 01:03:51 | 显示全部楼层 |阅读模式

欢迎访问技术宅的结界,请注册或者登录吧。

您需要 登录 才可以下载或查看,没有账号?立即注册→加入我们

×
本帖最后由 Kagamia 于 2023-5-13 01:07 编辑

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

前情提要

最原始的题目出处在这里,是一个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,你是不是,其实,可以竖着写?
QQ图片20230512235128.png

而Count and say这道题目,其实你也可以竖着写。和杨辉三角不同的是,因为指数级长度的出现,竖着写会越写越长。
比如,我们从第5行“111221”开始竖着写,写到第8行,大概顺序是这样的。
QQ图片20230513001413.png
这张图画的比较草率,箭头的源是单元格,目的是红色方块,excel自带单元格用于相同数字组合。
按你胃(anyway),如果看不懂就自己用自己喜欢的格式推导一遍,你立刻就理解为什么它可以竖着来。

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



参考实现

比较接近真实的场合,我没有使用刚才手算的这么极端的纵向计算方法。
因为在多线程下,运算单元太小而锁太多,导致线程调度成本过高。
对应地,我其实使用“块”作为运算单元,使用“协程”让每一层计算可被随时中断,使用“队列”向下一层传递数据,使用“阻塞管道”传递数据就自动实现了中断。
噢,这听上去是不是适合用go实现?
是的,我就是用c#实现的。c#有自动编译成协程的yield和await,有从go那里inspire来的channel,有轻量级工作单元Task,零件齐全。
我只要实现这样一系列函数就够了:
  1. struct Worker {
  2.   public int LayerID;
  3.   public long ProcessedLength;
  4.   public byte LastChar;
  5.   public byte LastCharLength;
  6.   void HandleBlock(Span<byte> b);
  7.   void HandleFinalBlock(Span<byte> b);
  8. }
复制代码

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

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

使用道具 举报

2

主题

5

回帖

11万

积分

用户组: 技术宅的结界VIP成员

UID
8229
精华
2
威望
84 点
宅币
114696 个
贡献
80 次
宅之契约
0 份
在线时间
9 小时
注册时间
2023-2-9
 楼主| 发表于 2023-5-13 16:50:10 | 显示全部楼层
今天我很闲,所以真的去实现了一下,用的是golang。

golang并不算是优秀到能跟上思维速度的语言,甚至连基础集合类和内存池都要自己造。
这一白天,我写了三种实现,分别是:
  • 无脑写的,用于正确性校验。
  • base V1,但是把逐字节计算改成了块计算,并添加了状态缓存。
    1. type CountSayV2 struct {
    2.   stateCache map[StateCondition]StateOperation
    3. }
    4. type StateCondition struct {
    5.   Input [blockSizeV2]byte
    6.   LastByte byte
    7.   LastByteCount byte
    8. }
    9. type StateOperation struct {
    10.   Output []byte
    11.   LastByte byte
    12.   LastByteCount byte
    13. }
    复制代码

    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年前的配置上也可以轻松答题了。
回复 赞! 2 靠! 0

使用道具 举报

1109

主题

1637

回帖

7万

积分

用户组: 管理员

一只技术宅

UID
1
精华
243
威望
742 点
宅币
24113 个
贡献
46222 次
宅之契约
0 份
在线时间
2287 小时
注册时间
2014-1-26
发表于 2023-5-13 12:33:07 | 显示全部楼层
啊!这题还真是得靠一步一步来试、找到问题(比如最初的 S(78) 往后每一行长度明显呈现指数级递增趋势),然后再去解决问题(收集前面的每一行长度,可以画出函数曲线,并根据曲线的走势进行预估)。

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

回复 赞! 靠!

使用道具 举报

2

主题

5

回帖

11万

积分

用户组: 技术宅的结界VIP成员

UID
8229
精华
2
威望
84 点
宅币
114696 个
贡献
80 次
宅之契约
0 份
在线时间
9 小时
注册时间
2023-2-9
 楼主| 发表于 2023-5-13 23:16:58 | 显示全部楼层
0xAA55 发表于 2023-5-13 12:33
啊!这题还真是得靠一步一步来试、找到问题(比如最初的 S(78) 往后每一行长度明显呈现指数级递增趋势), ...

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

是一件特别有成就感的事。
回复 赞! 靠!

使用道具 举报

1109

主题

1637

回帖

7万

积分

用户组: 管理员

一只技术宅

UID
1
精华
243
威望
742 点
宅币
24113 个
贡献
46222 次
宅之契约
0 份
在线时间
2287 小时
注册时间
2014-1-26
发表于 2023-5-15 19:17:34 | 显示全部楼层
Kagamia 发表于 2023-5-13 23:16
是的,全程每一件事都是在优化复杂度常量,而不是指数本身。
但是每一件事都做到,就可以数十倍提升效率 ...

与此同时 你也成为了全论坛拥有宅币最多的人,可喜可贺 可喜可贺
回复 赞! 靠!

使用道具 举报

55

主题

266

回帖

9310

积分

用户组: 管理员

UID
77
精华
16
威望
237 点
宅币
8184 个
贡献
251 次
宅之契约
0 份
在线时间
250 小时
注册时间
2014-2-22
发表于 2023-5-17 08:53:02 | 显示全部楼层
0xAA55 发表于 2023-5-15 19:17
与此同时 你也成为了全论坛拥有宅币最多的人,可喜可贺 可喜可贺

他的论坛币怎么会有这么多,充值了么?
回复 赞! 靠!

使用道具 举报

2

主题

23

回帖

1867

积分

用户组: 管理员

UID
4313
精华
1
威望
35 点
宅币
1746 个
贡献
21 次
宅之契约
0 份
在线时间
209 小时
注册时间
2018-9-24
发表于 2023-5-26 09:40:32 | 显示全部楼层
美俪女神 发表于 2023-5-17 08:53
他的论坛币怎么会有这么多,充值了么?

手动给她加的
回复 赞! 靠!

使用道具 举报

本版积分规则

QQ|申请友链||Archiver|小黑屋|技术宅的结界 ( 滇ICP备16008837号 )|网站地图

GMT+8, 2024-2-26 00:21 , Processed in 0.040951 second(s), 35 queries , Gzip On.

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表