一些经典的系统idea

类似于 CS61C 提出的体系结构经典 idea我也想在这里总结一下我在学习/读论文过程中看到的可复用的 idea很多文章就是对这些 idea 进行排列组合用于实现 tradeoff 的一部分实现整体的性能目标

分层以利用局部性

数据的访问存在局部性指令的局部性体现在循环和经常调用的函数上数据的局部性体现在数组上存在局部性的时候就可以用少量快速昂贵的存储上层和大量慢速廉价的存储下层进行组合实现既快速又大量的存储这里纯粹是讲利用局部性达到的提升假如上层($t_1$)比下层($t_2$)快20倍但是直接访问上层内容命中率为95%那么访问数据期望的时间是$0.95t_1+0.05t_2=1.95t_1$命中率更高时效果更好

内存层级系统是最经典的例子寄存器L1i/L1d Cache, L2 Cache, L3 Cache, 内存虽然机制有所不同但是可以加上硬盘一层一层叠起来实现接近寄存器读写速度和硬盘容量的存储这中间还可以再添加层级例如固态硬盘的控制芯片一般会自带一些缓存块和一个缓存系统类似的例子还有用于地址翻译的 TLB 会带有页表的 CacheDPDK 的内存池会在每个核设置 Cache操作系统会缓存文件系统的元信息/文件内容存储敏感的应用程序如数据库会自行建立对硬盘数据的缓存等等无论在硬件还是软件中Cache 的思想都是十分常用的

Fast Path

这是一种优化复杂逻辑的方法软件中经常出现这种情况某部分的逻辑很复杂但是如果加以一定的假设/理想条件逻辑就能得到大幅的简化如果这种假设经常能够被满足那么就可以为满足这种假设的情况单独编写一个简单的分支这就是 Fast Path而只在假设不满足的时候进入复杂分支

存在这种优化的信号通常是为了解决某个不经常出现的问题引入了某种新的数据结构/逻辑而新逻辑的 overhead 非常高

例如TCP 为了解决不经常出现的乱序包问题而引入了重排 buffer 这种数据结构于是每收到一个包都需要在重排 buffer 中寻找它的位置就多了一份访问链表/红黑树的 overhead如果不认真加以解决这份开销会在每次收到数据包时发生影响严重解决的方案就是对经常出现的情况数据包顺序到来进行特殊的检查这里就是存储一个待接收的序列号发现序列号等于待接收的号时就直接放在重排buffer的开头另一个例子来自 SRNIC(NSDI 23)RDMA 为了解决不经常出现的乱序问题而在硬件中引入了 bitmap 结构重传队列结构和复杂的重传逻辑带来较高内存开销解决方案就是只在硬件实现顺序到来的部分逻辑监测到乱序时就通知软件进行处理以节约硬件资源由于数据中心网络中乱序很少发生对整体性能的影响很小

批处理

批处理通常用于将一些较高的重复的 overhead 均摊到多次操作中例如 mTCP 与 I/O 库的交互就是批处理式的网卡一次传递给 mTCP 多个数据包mTCP 再生成一批事件传递给应用均摊了 mTCP 与 I/O 库交互的上下文切换等开销I/O 库与网卡的交互也是批处理式的均摊了一些昂贵的 PCIe 操作开销再例如 TCP delayed ACK 是希望 TCP 实现不要收到每个数据包都发送 ACK平均每 2 个包发送一个 ACK 是推荐的量这个量的选取还考虑到了 ACK 承载的拥塞控制功能如果没有这方面考虑可以将发送频率设置得更低TCP Nagle 是希望 TCP 不要发送过多的小数据包而是攒成更大的数据包进行发送显存对不同区域内容的写入顺序要求并不严格因此可以将需要写入显存的数据暂存起来再一起成批写入显存的硬件以均摊与显存交互的开销这些都可以看做批处理思想的例子

批处理涉及到平均处理时间和响应时间的 tradeoff批处理时平均处理时间比较短但是最早到来的请求需要等待其他请求的到来才能被写入所以响应时间会变慢如果能取得平衡就能得到较好的效果

抽象生成与中间层

编译器的诞生可以说是计算机发展史上的一次工业革命它将人们从手写汇编的繁重劳动中解放出来开始用高级语言编程这里要说的概念都是从编译器中得到的启示

抽象

编译器的工作就是根据抽象而人类易懂的高级语言生成功能简单易于执行的低级语言抽象从来没有增加程序员能做的事情它只是对程序员进行了更多的限制但这种限制降低了程序员的心智模型一旦理解高级语言后高级语言编写的程序就比低级语言更加易懂高级语言可以针对其要表达的内容简化语法从编译器和程序员共同认同的假定中推断信息编程语言的例子不必再举举一些其他抽象的例子

  1. 操作系统将对硬件的操作抽象为系统调用这里的低级语言相当于操作硬件的寄存器高级语言就是系统调用例如将对硬盘/网络的访问抽象为文件只允许程序员把它当成流来读取/写入从编译器和程序员共同认同的假定中推断出按流操作的能力已经足够简化了程序员对硬盘/网卡的操作十分易懂同时还实现了对硬件统一高效安全的管理
  2. Rubik 是一个用于生成网络中间件的领域特定语言将连接抽象为 id, sequence, 状态机和数据的集合只允许程序员操作这些数据结构降低了心智开销这样的数据结构设计以及优化过程中用到的假设都从编译器和程序员共同认同的假定中推断出非常多的信息
  3. 极端一点的例子导航系统的起点终点语言就是一种抽象语言补充语法有选择交通工具红灯少/价格便宜/时间短的偏好选择等

生成

从高级语言生成低级语言的过程是自动化的特别地对代码的优化过程也可以自动化进行这说明编写低级语言的过程中隐含了许多重复性的劳动它们被自动化后减少了程序员的心智负担而且机器通常做得比程序员还要好

中间层

在源语言和目标语言中间可以插入中间语言将源语言先编译成中间语言再编译成目标语言通常这里的中间语言是对各种目标语言共性的提炼因此语言前端只需编译到同一种中间语言中间语言再编译成各种目标语言前端的工作便无需针对多种目标语言重复进行减少了重复的工作量同时中间语言比源语言更加具体更加接近机器执行的语义因此便于进行优化这些几乎是照着 LLVM 说的此外Rubik 也用到了中间语言进行优化目标语言是 C 语言目前看来没有多目标语言的必要DPDK 的 EALSQL Server 的 SQLPAL 用中间层的方式实现了跨操作系统Nginx 自己实现的事件处理层实现了多种系统调用epoll/kqueue/IOCP之上的事件处理

6.824 Lab2B Raft

2022.12.18 完成了 Lab2B内容是实现 Raft 的共识算法经过 200 轮测试的检验没有发现问题我就当作实验完成了这里记录一下过程中发现的比较有意思的 bug它们不一定很难修改很多也都明确地写在 Raft paper 的 Figure 2 中但是去思考它们为什么会导致错误什么情况会触发这些错误是很有意思的一件事并且能帮助我们更好地理解 Raft 这个系统想到读 paper 时没有想到的问题

Livelock

有时会发生这种情况系统虽然在线但不再做有效的工作连心跳都不发送打印许多日志后发现集群由3台机器组成一直在选举而且永远是同一个机器竞选而另外两台机器拒绝投票因为 Candidate 没有通过 up-to-date 检查Raft paper 5.4.1这个 bug 错在 RequestVote RPC 的接收方不加判断地更新重新选举定时器正确地做法是仅在投票时更新定时器拒绝投票时不更新定时器来保证自己可以正确地超时启动竞选在这里Candidate 没有通过任何 Follower 的 up-to-date 检查说明它无法竞选成功要使系统继续工作需要另外两台机器之一超时启动竞选

类似地AppendEntry RPC 应当在 RPC term 没有过期时更新定时器注意这不要求 RPC 成功因为 RPC 可能因为 log 不一致而失败这时 Leader 会自减 nextIndex[] 并重试这仍然构成一个 Heartbeat应当更新定时器

错误地认为 log 冲突导致不必要的删除

在 Raft Paper Figure 2 中AppendEntry Step 3是

If an existing entry conflicts with a new one (same index but different terms), delete the existing entry and all that follow it.

我曾经在比较 term 时出错用 existing entry 的 term 与 AppendEntry 的 term 比较了正确的做法与 AppendEntry 中新的 Log Entry 的 term 进行比较这可能会导致不必要的删除日志因为传输的新 Log Entry 不一定是当前 term 的内容也可能是之前 term 的内容

这会导致问题的场景是如果 AppendEntry 在网络中经历了较高的延迟RPC 可能已经过期正确做法下两条 log 不会冲突所以不会删除而这个错误会导致删除这条以及其后所有的 log而我们很可能之前已经告诉了 Leader 我们拥有那条 log如果集群中拥有这条 log 的机器数刚好过半Leader commit 并应用到状态机上这时我们删除了这条 log拥有 log 的机器数就不再过半如果此时 Leader 再离开集群重新选举的 Leader 就不一定包含这条 log 了正常情况下新Leader 包含这条 log 这件事由 5.4.1 的 up-to-date check 保证也就是 committed log 被回滚了

助教的这篇博文也提到了这一问题

这个 bug 是我阅读代码发现的这可能并不好测试根据我的理解6.824 的测试用例并没有模拟乱序的网络通信

CommitIndex 的激进更新导致某些机器做出错误 commit

问题在于TestBackup2B 会有很小的概率失败原因是某台机器作出的 commit 和其他机器已经作出的不一致这个问题困扰了我很久直到我离开电脑准备睡觉时才想到这个问题可能的原因在 Raft Paper Figure 2 中AppendEntry Step 5 是

If leaderCommit > commitIndex, set commitIndex = min(leaderCommit, index of last new entry).

这个 new 很重要我的错误在于直接用 log 长度更新 commitIndex正确的做法是用 AppendEntry RPC 中携带的最新 Entry 的下标来更新 commitIndex这会导致 commitIndex 的更新过于激进后面的尚未确认与 Leader 同步的 log 也会被 commit这看起来应该经常出错为什么在 TestBackup2B 中很少出现呢因为带有错误 log 的机器在连接到正确集群时Leader 会不断地自减 nextIndex[] 并重试 AppendEntry RPC直到在某处 Log 吻合这时该 Leader 会第一次更新该 Follower 的 commitIndexcommitIndex 首次被更新时 AppendEntry RPC 通常携带新的 Entry而这个 Entry 和 RPC 接收方的 log 是冲突的所以 log 都在步骤 3 中被清空了于是步骤 5 中 index of last new entry 也就是 log 的长度那什么时候才会触发这个错误呢答案是 commitIndex 首次被更新时接收到的是心跳不带 Entry 的 AppendEntry RPC它不会清空后面的错误的 log而且还会更新 commitIndex这就要求心跳刚好在 nextIndex[] 减少到正确值的时候发送所以出现的概率很低

要定位这个 bug 还是很困难的因为这个问题出现的概率真的很低跑50次出1次问题左右每跑一次都需要等很久而且每次 commit 都打印一条信息导致输出很长推荐一篇文章Debugging by Pretty Printing是 6.824 的一名助教写的帮助我们更好地用日志调试分布式系统

Committing entries from previous terms

我在 Leader 上的 CommitIndex 更新采用的方法是matchIndex[] 中第 n/2+1 大的数这时要注意这条 log 还需要属于当前 term否则无法宣布 commit也就是不能 commit 之前 term 的日志原因在 Raft paper 的 5.4.2 节和 Figure 8 中有详细说明

复读大三

开学的时候我感到很想完成几门早有耳闻的北美CS课程的实验6.s081MIT操作系统课cs144斯坦福计算机网络15-213CMU计算机系统结构6.824MIT分布式系统构建一个真正 work 的系统同时认真把它搞透于是想到了一个命题我大四课这么少用来复读大三怎么样如果大三可以重来我会做些什么呢

目标

考虑到我同时需要科研以及工作效率并不如想象中高我定下了一个看起来可行性很高实现后也很有收获的目标完成 6.s081cs14415-213 三门课程的实验完成质量需要比较高这里提出几点要求

  1. 严格按照要求完成实验主要关注分数要求所有通过性测试必须通过跑分性测试达到较高分数线和任务点要求如 6.s081 的两个功能选择一个实现不能不选
  2. 清楚明白地了解自己在做什么不能做完实验还感到有哪里含糊不清楚如果有疑问至少需要具体地列出来并在能力范围内尝试解决

更高的要求包括阅读源码从零复现系统不做硬性要求

视前几周的精力情况决定要不要做6.824第二周需要先尝试起来把 Raft 的论文读起来

计划

目前的计划每周每门课一个lab除 6.824 外第一周已经做完了 cs144 Lab0-26.s081 Lab015-213 bomb lab(4/6)data lab以前做过不再重做6.828 lab1 是以前做过的按照第一周的进度来看这个计划还是很有希望按期执行的不过预测后期难度会增加尤其是 OS…如果出现这种情况可以2周/1.5周一个lab

如果计划理想进行到了中后期 cs144 就做完了可以投入更多精力做 6.824

注意到这里没有编译原理有点尴尬…其实我是很想手搓编译器的而且不想用 yacc/bison除开科研可能需要的编译知识之外它的优先级可能和分布式系统相同暂时先不列入计划执行一段时间上面的计划再重新考量这个重新考量不晚于第三周周末

本文每周一更新


进度记录

2022.9.20

这周突然特别想手搓OS所以进度甚至比预想的还慢…cs144和6.s081推进了一个实验没有问题但是csapp没有做这周目标和上周一样其中csapp的目标是做完bomb lab并再做一个不过手搓OS进度还挺好的快要进入用户态了

2022.12.18

成功地复刻了之前的每个学期都没能坚持学完网课的历史…好在这学期不是一事无成这里来总结一下

手搓 OS 在虚拟机里已经跑得很不错了有了用户态多进程系统调用文件系统终端下一步工作包括文件系统的写出多核调度与内核锁搭建测试框架尝试了 USB 驱动但是比较困难暂时放下

bomb lab 做完了但也就止步于此其他 lab 没做

6.824 lab 2B 今天刚刚做完通过了 200 轮测试感觉神清气爽啊

科研方面在做一个DSLDSL编译后会生成一套网络协议栈的源码已经在实现编译后的系统原型了目前只差定时器和拥塞控制了通过阅读 RFC对 TCP 的理解比大三上课时高了不少

6.824 Lab1 MapReduce

前前后后做了15个小时看到PASSED ALL 30 TESTING TRIALS的那一刻太爽

概述

这个实验要求实现经典论文MapReduce的模型MapReduce在Google内部是跑在一个服务器集群里的这些服务器共享一个分布式文件系统GFS这个实验只要求实现运行在本机多个进程上的本地文件系统上的MapReduce模型省去了与分布式文件系统的交互要做负载均衡这个很重要而且应该很麻烦

实现过程流水账

先读论文花了3h左右内心活动这论文真简单

然后开始实现我并不会go语言官网那个tour我也就做了一点点事实证明全做完比较省时间第一次写的代码全是if-else我还没有加入容错机制的时候代码已经复杂到我读不懂了内心活动工业界实现这玩意的人是神仙吧然后我把3个小时码的200多行代码全都回滚掉了:-(

第二次写代码之前我决定写一个类似于有限状态自动机的东西事实证明这个模型还不错让我的思路变得比较清晰并且便于拓展然后花了2h画图+搭框架就是只写了一堆switch-case每种状态对应的转移和转移前需要进行的操作的注释然后就头晕下班了

今天是第三次碰这个东西今天如果再自闭我可能就要对这实验产生心理阴影了好在我上次的DFA没啥大问题只是有些corner case没想到缝缝补补搞了一段时间终于把注释转换成了代码最戏剧性的一刻来了开码10小时后我终于进行了第一次编译我以为会得到巨长无比的报错结果报错就八九行然后就是改完一行错再出现一行错改完最后一行错之后又蹦出来十几个错误改了若干年……通过编译之后他在起始状态就出错了……然后又改了若干年终于输出了结果

第一个教训把语言学明白勤编译勤测试

我查看输出文件的前三行共两万行发现与标准输出一样然后高兴地去跑测试脚本结果第一个正确性测试点就挂了……

第二个教训测试要认真严谨

然后又改了若干年期间多次翻阅论文发现人家写进论文的东西都是经过取舍和迭代的还是非常精华的后来就是无限改bug调试按下不表终于在今天码代码的第8小时通过了所有测试

做的不错的地方

  1. 画DFA
  2. 头脑不清楚的时候出门转转可以花掉长达20分钟的时间但是回来之后你就复活了

想要做得更好的地方

  1. 阶段性编译测试例如我的DFA设计好了这时候就可以测试下转移有没有问题然后再在转移前后加功能
  2. 有设计测试点的能力对于这个实验我是用户而且一定程度上可以说是赶时间所以用老师的脚本来测试调试没有什么错但是一旦成为真正意义上的开发者bug都要自己找不提开源社区之类需要有能力设计若干测试来检验自己的代码在各方面的正确性/性能这确实需要写一些没用的代码但是它们通常很简单而且很有用如算法竞赛里的对拍程序和暴力程序例如我尽管知道各个操作的时间/空间复杂度但还是不知道我这个实现并发性如何究竟有多少CPU时间是overhead
  3. 证明我的DFA的正确性
  4. Challenge
  5. 阅读老师的测试脚本学习写脚本

CF Edu123 题解

F. Basis

题面

考虑一群在操作 2 下可以互相变换的数组在其中可以取一个代表元$arr$假设$arr$$i$种数字组成$arr$中数字$j$所在的下标的集合记作$S_j$则这一群数组可以用集合的集合$\{S_1,S_2,...,S_i\}$来表示称为一个原型如果只能做操作2答案就是第二类斯特林数$\left\{n\atop i\right\}$的前缀和$i$从1加到$\min(k,n)$出于后面的实现方便将对$i$从2加到$\min(k,n)$的前缀和记作$A(n)$这可以用$O(n\log n)$的复杂度来求具体见oi-wiki

接下来考虑操作1我们发现刚才找到的那些代表元当中有些可以经操作1生成现在来删除它们将原型$arr$改写成连续的相同数个数的数组的形式记作$arr'$例如将$1,1,2,2,3$改写成$2,2,1$

  1. 如果$arr'$只有一个数就是说$arr$中全都是相同的数字我们发现$arr$一定可以由某个改写前有至少两个不同数的原型经一次操作1$F(a, n)$生成于是不用对$arr$计数也就是说题目中给的$k>1$不用考虑这种情况如果$k=1$输出1即可
  2. 如果$arr'$不只有一个数去掉$arr'$的最后一个数考察前面的那些数如果它们的$gcd$不为1$arr$可以被别的原型由操作1生成不用对$arr$计数对一个$gcd$$A(\lceil {n\over gcd}\rceil)$个原型可以被别的原型$a$生成$arr$中每连续$gcd$个数绑定再计算原型数也就是$A(\lceil {n\over gcd}\rceil)$注意$A$是从2开始加的因为数字全部相同的原型并不能由操作1生成$arr$如果这个$gcd$是合数可能这些冗余数组会被它的因子删除多次需要控制这个次数解决方法是用mobius函数就是说$gcd$我们计$\mu(gcd)$$A(\lceil {n\over gcd}\rceil)$

这里的mobius函数就是在对$gcd$的质因子集合$S$做容斥质因子集合$S$的子集$S'\subset S$可以与那些各质因子至多出现一次的$gcd$的因子建立一一映射一个子集中有奇数个因子就取$-1$偶数个因子就取$1$有质因子出现2次就取0子集为空集时对应于因子1也取1

对一个给定的$gcd$那些能经操作1$F(a, gcd)$生成的原型也可以被$gcd$的因子$d$们经操作1$F(F(a,d), gcd/d)$生成每个这样的原型被计了多少次呢答案是

$$\sum_{d|gcd}\mu(d)=\sum_{S'\subset S}(-1)^{|S'|}=\sum_{i=0}^{|S|}\binom{|S|}{i}(-1)^{i}\times 1^{|S|-i}=(-1+1)^{|S|}=[gcd=1] $$

也就是实现了$arr'$除去最后一块外的所有数互质$arr$就属于否则不属于这结束了我们的讨论关于$0^0$不等式和$[gcd=1]$的讨论可以和Trie树维护集合相交性相类比最后的答案是

$$\sum_{gcd=1}^n\mu(gcd)A\left(\left\lceil\dfrac{n}{gcd}\right\rceil\right) $$

直接整除分块求这个东西的一个上界是

$$O(\sum_{gcd=1}^n\dfrac{n\log n}{gcd})=O(n\log n\sum_{d=1}^n\dfrac{1}{d})=O(n\log^2 n) $$

注意不是$O(n\sqrt{n}\log n)$我们还可以合并同一个$\left\lceil\dfrac{n}{gcd}\right\rceil$对应的所有$\mu(gcd)$之和前缀和或者开桶统计一下就行这时由于后面那个求和只有其中的$\sqrt{n}$可能还达不到$\log n$可以理解为常数很小的$\log n$经测试$n=10^5$该和为6.83

Trie树维护集合相交性

这篇文章讲一个 trick他可以解决如下问题

维护一个结构可以添加和删除集合可以询问对询问中给定的新集合结构中有多少集合与之不交

用这个 trick可以在 $O(2^{|S|})$ 的时间复杂度内添加或询问一个集合 $S$ 所以在多个小集合的时候比较有用

对两个集合 $A$$B$ 考虑 $B$ 的所有子集维护一个计数器 $cnt$ 对每个子集 $S$ 如果它也是 $A$ 的子集$cnt$ 加上 $(-1)^{|S|}$

$$cnt=\sum_{S\subset (A\cap B)}(-1)^{|S|}=\sum_{i=0}^{|S|}\binom{|S|}{i}(-1)^i\times 1^{|S|-i}=(1-1)^{|S|} $$

$A\cap B=\emptyset$ 时形式上是$0^0$不定式根据定义式计算发现它有由空集贡献的 1 于是 $cnt$ 就标志着 $A\cap B$ 是否为空为空时 $cnt=1$ 否则 $cnt=0$

现在我们维护一个 Trie 树每个节点代表一个集合当添加集合 $A$给它的所有子集对应的节点权值加一删除时就为所有子集对应的节点权值减一可以注意到空集对应节点的权值就代表当前结构中维护的集合个数

然后考虑询问设在询问 $S$ 对所有 $S'\subset S$如果 Trie 树中有对应 $S'$ 的节点就为计数器加上 $(-1)^{|S'|}\times tr ie[S']$这样对结构中维护的每个集合若它和 $S$ 不交它对计数器的贡献就是 1 否则是 0于是计数器的值就代表了结构中与 $S$ 不交的集合个数

ARC136题解

这场 ARC 比较考验观察能力就是找到切入点的能力我会尽量在题解里给出一个观察的过程至于证明比猜到结论简单这场暴露出来我的容易进死胡同的问题也可能是人类本质就是一种思路做不出来的时候跳不出来思维僵化了以后训练中得注意对想不出来的题尝试跳出思维定势也可能只是 trick 掌握得不够导致跳出来也不知道想啥可以先多积累些思路毕竟思而不学则殆

C - Circular Addition

题面

收获的思路

  1. 在差分数组上看区间加减
  2. 问最小操作次数时找几个下界尝试证明其最大值可以取到证明时可以尝试把创造过程逆转为消除过程因为消除时的信息更多而创造是在创造信息

我看到了第一个切入点用差分数组处理区间加减问题如果您对这个题毫无头绪可以先对着这句话看自己能想到哪一步将目标数组看作环并作长为 $n$ 的差分数组发现这个差分数组和一定为 0而且每次操作一定是使得一个数 +1一个数 -1显然我们可以通过每次选择一正一负的一对位置操作来得到目标差分数组操作次数为差分数组中正值之和

然后我发现过不了最后一个样例仔细一看发现其实也没能给出前两个样例的具体操作步骤不太对劲具体来说就是可以交换差分数组上的操作顺序来获得额外的全体 +1buff这个信息在差分数组里被丢掉了从这时开始我就开始想着怎么最大化这个 buff以及是不是最大 buff 和零 buff 之间的所有值都能取到陷入了苦战

按照题解来讲的话我们已经观察到了一个操作次数下界还有另一个显然的下界就是数组中的最大值我们猜想他们中的最大值是可以被取到的然后反过来想将目标数组变为 0 的过程我们发现这个思路在近达上一场比赛 ARC135D 中就出现过需要学习一个

实际应用中这种猜想很可能会错尤其是难题所以姑且提出一个做题步骤

  1. 观察总结此前得到的事实提出猜想
  2. 代入样例若有误返回1
  3. 尝试证明若证伪返回1
  4. 如果证明或不会证而自信开码
  5. 如果没证出来且不太自信多造点样例再次手玩或对拍若有误返回1否则开码

按照步骤我们应当代入样例发现没问题开始尝试证明如果我们在每一时刻都能降低这一时刻的差分数组下界$L_1$最大值下界$L_2$中的最大值我们就构造性地证明了猜想的正确性为了降低最大者我们需要对$L_1$$L_2$的大小做出假设来进行进一步推理

  1. $L_1<L_2$此时数组中不可能有 0否则为了从 0 增加到 $L_2$差分数组中正值部分至少是 $L_2$这与 $L_1<L_2$ 矛盾于是全体 -1 即可这样能使 $L_2$ 减小 1
  2. $L_1>L_2$如果数组中有 0我们只要挑选一段包含最大值的极大非零区间来全体 -1这样能使 $L_1$ 减小 1如果数组中没有 0数组中一定有若干山谷所以一定可以找一段极大的连续最大值区间要求其左右不再是最大值来减 1这能使 $L_1$ 减小 1
  3. $L_1=L_2$如果数组中有 0一定是单调增加到 $L_2$ 再单调减小到 0将非零部分 -1 即可同时减小 $L_1$$L_2$如果数组中没有0数组中一定有若干山谷如果*极大的连续最大值区间*唯一那么将其减 1 即可否则一定可以找到一个区间覆盖所有的最大值例如除去最小值后获得的区间将这个区间全体减 1 即可

把这个过程反过来想会变得更难想尤其是 $L_1=L_2$ 时的操作所以这个减小双下限最大值的 trick 应该被加入知识库

D - Without Carry

题面

收获SOSdp

推荐博文SOSdpzeta transform 前者为后者前置知识本题只需要学习前者但是来都来了为什么不都学一下呢

读完博文直接就会做了不会就看官方题解不必多说

E - Non-coprime DAG

题面

收获我观察能力低下

  1. 不够耐心一条思路还没想透彻就放弃
  2. 可以把结论写出来更容易发现规律形式的不同会影响思考方式

在看题解之前您至少应该发现不可达互质并不等价例如9可以经12和14到达35并且经过了一定的思考

$i<j$ 考察 $i$ 是否可达 $j$ 后文同余符号皆模 2 $f(i)$$i$ 的最小质因子

  1. $i\equiv 0,\;j\equiv 0$此时一定可达
  2. $i\equiv 0,\;j\equiv 1$此时来到了第一个重要观察可以尝试经过 $j - f(j)$ 这一偶数到达 $j$ 所以不超过 $j-f(j)$ 的偶数都 ok 即要求$i\leq j-f(j)$而比它大的偶数$j$ 的差距已经小于其最小质因子了没有机会走到 $j$
  3. $i\equiv 1,\;j\equiv 0$类似于 2 要求$i+f(i)\leq j$
  4. $i\equiv 1,\; j\equiv 1$此时来到了第二个重要观察也是我卡住的地方由于我没有将上面的观察列出来我并没有注意经过偶数到达奇数这条路或者隐约觉得这效率低下其实这个类比还是比较明显的大脑好用时起码可以猜一个结论出来先写结论$i+f(i)\leq j-f(j)$ 即可首先两者都是奇数这就决定了只加一个一定为奇的质因数并不能使 $i$ 到达 $j$ 至少要加 2 个如果想由偶数搭桥显然i -> i+f(i) -> j-f(j) -> j的路径就是最优的如果不这样做要么 $i,j$ 有公因子此时 $i+f(i)\leq j-f(j)$ 必成立或者仍然可以理解为从偶数搭桥要么还是需要转到 $j-fac(j)$ 再转到 $j$ 其中 $fac(j)$$j$ 的某个因子而这一个转变最少也要加 $f(i)$ 转变后最少也要再加 $f(j)$ 到达 $j$ 本质还是从偶数搭桥

现在我们获得了可达的数学表达我又卡在这里了我去想 DAG 了并且没跳出来注意到不等号左右的内容都很相似并且右侧可以加1因为模2的限制两式仍然等价尝试总结为一个式子可以将不等式变形为

  1. $i+1\leq j$
  2. $i+1\leq j-f(j)+1$
  3. $i+f(i)\leq j$
  4. $i+f(i)\leq j-f(j)+1$

可以总结为

$i$ 可达 $j$ $\Leftrightarrow$ $up(i)\leq low(j)$其中 $up(i)=(i\equiv0)?i+1:i+f(i)$注意这个 $+1$ 这是因为 $i<j$ 不带等号$low(j)=(j\equiv0)?j:j-f(j)+1$

再次总结这个表达对任意的 $i, j$当且仅当 $up(i)\leq low(j)$$up(j)\leq low(i)$ 时他们之间可达用区间语言表达就更干净$[low(i), up(i))$$[low(j),up(j))$ 没有交点时可达注意区间开闭于是题目变成寻找有公共交点的区间族 $\{[low(i), up(i))\mid i\in\mathbb{N}\}$ 使得 $\sum_{i}A_i$最大随便做

ARC135题解

F暂时有个地方没搞明白但我会研究题解和正确代码把它搞会

C - XOR to All

题面

关键在于发现若干次操作一定可以等价于一次操作

假设进行了多次操作考察前两次操作$B_0$$B_1$由定义$B_0$一定是原数组中的一个数$B_1$一定是原数组中的某个数$A$$B_0$的异或和因为$B_1$取自被$B_0$更新过的数组我们发现$B_0,B_1$两次操作的结果等价于直接用$A$进行一次操作现在操作次数减少了1可以一直使用这个方法直到将多次操作等价为一次操作

现在只需要比较选择每个数对数组元素之和的影响这可以按位统计做到对每一位最多30位统计有多少个数在这一位是1然后选择$A_i$对和的影响就是$A_i$会对数组中所有的数翻转$A_i$中为1的那些位翻转的贡献可以由统计的数据计算出来

E - Sequence of Multiples

题面

赛后自己做出来了很高兴

下面记题目描述的数列本身为$A_i$而不论怎样得到它

初见端倪的朴素算法

观察一个特殊的例子$X=1,N=1e18$这时数列就是$1$$n$本身然后考察$X=2,N=1e18$发现数列是$\{2n\}$继续观察会总结出一个规律无论$X$如何$n$充分大时数列会变成$\{kn\}$的形式$k$为常数

证明假设第$n$项是$kn$那么第$n+1$项的一个上界是$k(n+1)$这比前一项大了$k$只要$k\leq n+1$这个上界就会被取到因为更小的$n+1$的倍数已经小于第$n$项了这不符合题目要求

于是我们发现这个$k$的变化趋势是很重要的如果我们能搞清楚什么时候$k\leq n+1$这之后的内容就可以$O(1)$计算了为了研究它构造新的数组$\{B_n\}:B_i=A_i/i$

在特殊例子上构造$\{B_n\}$会给我们一些最基本的认识例如$\{B_n\}$是不增的前面的证明过程稍加修改就能证明这个结论实际上我们感到它以类似于反比函数的速度减少

为了解出$B_i\leq i+1$的时刻我们研究$B_i$的变化趋势而这可以其定义中的$A_i$入手考察$A_i$的变化趋势我们发现$A_{i+1}-A_i\leq i+1$否则$A_{i+1}$会被$A_{i+1}-(i+1)$取代于是$A_i$大致以$O(n^2)$的速度增加具体来说$A_i-A_1\leq(\sum_{k=2}^{i} k)=(i+2)(i-1)/2$

得到了$\{A_i\}$的变化趋势两侧同时除以$i$即可得到$\{B_i\}$的变化趋势上界$B_i-\frac{X}{i}\leq \frac{(i+2)(i-1)}{2i}\leq i$$B_i\leq \frac{X}{i}+i$这个上界是有极小值的但我们知道$B_i$不增所以我们可以先增加$i$得到极小值然后等待$i+1$追上这个极小值显然这个极小值在$i=\sqrt{X}$附近取到$i=2\sqrt{X}$时就一定有$B_i\leq i+1$于是我们证明了如果我们暴力计算$\{A_i\}$直到$B_i\leq i+1$时间复杂度是$O(\sqrt{X})$尽管我们没有证明其下界但这个算法实际效率也不够高1e18 1e18的输入需要计算20秒10组就是200秒远不是常数问题

正解

$B_i$有一个类似于反比函数的一开始快速下降然后缓慢下降最后不变的变化过程对反比函数的取整求和有整除分块$B_i$能不能也找到某种分块来合并一些计算呢

在Linux上使用clash

更新我火星了有现成的GUI…请使用Clash for Windows的Linux版本

  1. release页面下载Clash.for.Windows-0.x.x-x64-linux.tar.gz
  2. 解压后执行./cfw
  3. 为了脱离命令行运行请看issue

以下为原文

东方网络为例按照机场默认的配置使用clash如果不够满意大概率参考API文档再稍微写一些代码就可以进行规则与节点的配置待更新

步骤

  1. releases页面中下载最新版clash内核一般的64位机器下载amd64版本即可解压后为一个可执行文件重命名为clash后执行chmod +x clash为其加上执行权限
  2. 在机场网站上下载配置文件命名为config.yaml执行./clash -t -f config.yaml如果没有问题说明配置文件正确
  3. 执行./clash -f config.yaml开启代理服务
  4. 配置系统代理选择"use manually specified proxy configuration"填入代理日志显示的代理地址+端口号
  5. 配置浏览器使用系统代理/配置浏览器代理指向clash现在应该已经可以访问google了如果不行检查配置文件的mode如果是direct改成rule或者global
  6. 按照官方wiki的步骤将其配置为守护进程

这样就足以支持日常需求了

页面调度算法

最优调度算法为什么最优

我们发现换页时换入的页总是固定的我们要挑选的是换出的页面优先换出不再被访问的页面是显然的首先注意换出的页面在下次访问时是一定会被换入的只要考虑没被换出的页面有没有离开即可如果不用最优调度算法换出A而换出一个下次访问更早的页面B那么

  • 如果A在下次访问A前未被调出那么换出A仍能使得下次访问B前B未被调出
  • 如果A在下次访问A前被调出了那么换出A有可能可以使得B不用被调出因为B的下次访问更早

于是换出A一定不比换出B差无论换出B后采用什么策略

堆栈式算法

堆栈式算法是指访问第$t$个页面时考虑驻留集大小为$n$时的驻留集$S$和驻留集大小为$n+1$时的驻留集$S'$如果可以证明在某种调度算法下无论对什么输入下的哪个$t$都有$S\subset S'$成立那么这个调度算法就是堆栈式算法

堆栈式算法的好处

这种算法没有Belady现象也就是页框增加时缺页中断次数不会增加

证明页框增加时由于任何时刻$S\subset S'$那么$P\notin S'\Rightarrow P\notin S$某页在页框多时缺页$\Rightarrow$该页在页框少时也缺页缺页中断次数不会更少

最优调度算法/LRU为什么是堆栈式算法

用数学归纳法初始时$S=S'=\emptyset$

假设对某个访问序列满足$S\subset S'$现在再访问一页$P$

$P\notin S'$那么$P\notin S$同时产生缺页中断设在$S$中换出页$P_1$$S'$中换出$P_2$对OPT/LRU中的每一种要么$P_2\in S'-S$要么$P_1=P_2$无论哪种情形换出页后仍满足$S\subset S'$

综上对任意输入这两种算法都是堆栈式算法

这个证明的核心在于要么$P_2\in S'-S$要么$P_1=P_2$看到网上的一个理解说是给驻留集里的页面一个与$n$无关的优先级选择优先级最高的那个于是不会选择$S-\{P_1\}$中的元素对FIFO算法这个优先级是进入时间然后我们会发现这个东西不完全取决于驻留集这个集合本身还取决于它进入驻留集的时刻有可能驻留集小时的缺页导致一个页面换出后再次换入但驻留集大时则总是驻留从而它在驻留集小时优先级低而驻留集大时优先级高这时有可能$P_2$是那个$S'$中总是驻留的页面$P_1$是其他的页面于是这个$P_2$现在仍在$S$中而不在$S'$