姿势奇特——Amagiii教你怎么水大作业

发布于 2020-03-16  246 次阅读


最近,我们班助教下发了新学期数据结构课程的大作业。像大作业这么喜闻乐见,愉悦身心的东西,当然要想方设法水完她了~于是便有了今天这样一篇文章。

题目要求就是实现STL中的3个容器:优先队列,更加优秀的双端队列,有序映射。

其实就是封装三个非常经典的数据结构:可并堆,块状数组,平衡树。

先从最为简单的优先队列开始说起:

这道题给了5s的时限,1024m的内存,测试点只有5个,平均每个1s。

估算数据范围不会很大,卡常问题不会严重。于是我选择最为简单的:左偏树。

左偏树无非就是向左偏的树(废话),在key满足二叉堆性质的同时,满足左节点到空节点的最小距离>=右节点到空节点的最小距离

实现的话,完全基于合并,也没什么好说的。

合并无非就是判空决定是否停止、判key决定合并方向。

压入为让根和新节点合并,弹出则是将根替换成两个孩子的合并。

一开始由于maintain的时候没有判断左孩子为空则左右孩子互换而导致被卡成链表,优化后轻松通过。

提交记录:

这玩意竟然还跑得挺快。夭寿啦~我萌点没啦~

下面来看看第二题:双端队列。

由于要求了迭代器的存在,这道题目所需的代码量要大出不少。再加上分块细节本来就多,导致此题愈发难写。

我选择的分块方式为链表套数组(而不是更加好写的链表套链表),随机访问无非就是先跳链表再数组寻址。元素过多则分裂、元素偏移中心过多则搬运元素。

迭代器的话,由于要求O(1)访问,所以不能只记录序列位置,每次都从头开始跳,而是要用指针保存所在的块、指向的位置。+-的话直接从向后、向前寻址。(毕竟你不能把++的复杂度变成根号的对吧)

于是我就这样写了,但是却并不能通过编译。因为有些类没有默认构造函数,你不能直接new出来。

那好办,再封一层指针就好了,用的时候再new嘛。

Test2的memory怎么Fail了?

STL要求放进去的每个成员只能在被加入时构造一次,被删除时析构一次,且这个测试点专门检查它。

好吧,在搬运元素的时候直接指针移位,原位赋值nullptr。这回总归可以了。

最坑的是test3的鲁棒性测试,要求解决越界访问、失效迭代器的问题。

越界访问,判即可。越界迭代器?由于该测试点考察越界情况较为简单,所以只需要判断迭代器记录的全局位置是否越界。

于是就有了这一堆奇奇怪怪的代码:

压行有什么错?压行那么可爱,为什么要迫害压行~

于是~这玩意就慢如爪巴了qwq

最后的(也是最喜欢的)映射——也就是我们最为熟悉的平衡树啦~

助教说去年大部分人写的是红黑树,不过我这种寒假没有提前写的人当然是不愿意写红黑树的(还不是因为懒)。于是我便选择了:替罪羊树。

平衡树的实现没什么好啰嗦的。

除了一开始因为删除有两个孩子的节点时直接替代删除前驱导致前驱迭代器失效外,没有任何问题。

当然,除了慢。

替罪羊树喜闻乐见地TLE辣~虽然据说是zui快的不平衡树,但和拥有主动平衡能力的重量级选手们还是有不少的差距的。

至少,第7个测试点跑5s这一点,不可接受。

于是,我转向了:Size Balanced Tree。

只需要修改几个函数,替罪羊秒变SBT~

不过看在第7个点只比替罪羊快0.5s的份上,估计这玩意的效率也不太行。

果然,SBT也光荣地TLE了。

我愚蠢地怀疑,评测姬迁移后,OJ变慢了。于是便去询问AT。

(为了保护助教的权益,没有截图头像框)

没错,自带大常数是萌点,绝不是黑点~想想你被卡常数过不去题百般调试却又无可奈何的样子,是不是就像RBQ一样?

(某RBQ:没错,是我了是我了)

从AT口中得知fstqwq学长去年写的也不是红黑树。查看其GitHub仓库后,发现他写的居然是——Splay!

惊了,Splay常数辣么大,怎么能过去这题?

于是复制其代码在本地进行测试,发现SBT用时4.5s的第7个测试点,Splay仅用时1.2s。

仔细分析发现,评测过半的运行时间被消耗在了第7个点上,而第7个点和第1个点只有数据范围不同,测试模式都是顺序访问。而Splay会被卡成一个单链表,每时每刻的根节点和下一个要访问的节点只有1的距离。所以最后的是:线性复杂度~

岂不妙哉?我也改Splay~

虽然本地(macOS)测第7个点栈溢出RE,但是在远程Linux机器上ulimit -s unlimit后测试通过。

交上去:

Memory Test TLE,这不是我的问题,而是OJ的。

于是本地valgrind测试,发现如果不指定无限栈空间,则会RE。

算了,不管了,先让助教修OJ。

修好之后:

不出我所料,还真就RE了。

不就是栈溢出嘛~大不了我人工栈!

改完了,送~

什么?人工栈A了。

于是,这题就被我用各种奇奇怪怪的方法卡了过去。

(绝对不能让AT看到这篇博文,否则RBQ这个称呼怕是得成真~)

好的,就酱,2020年春季学期数据结构第一个大作业宣告完成。DDL为第9周星期四,现在是第3周星期三,提前了6周的时间。

代码开源地址:https://github.com/cmd2001/STLite-2020

最后,火车票大作业求组队啊qwq

求各位大佬们带带我qwq

保证认真担当开发组吉祥物,摸鱼划水整活卖萌样样精通~

我是Amagi_Yukisaki,撕裂时空之人。如果想破碎世界连续性的话,请最好离我近一些。以上。


透露出一股死宅的气息(本站游走在宕机边缘)