转载

OO的奇妙冒险2

OO的奇妙冒险 ~多线程入门与魔鬼的优化~

目录

  • 总体分析
  • 作业内容分析
  • 作业内容总结
  • 互测的收获
  • 公测互测bug分析与总结
  • 优化分析
  • 不太正经的个人自嗨

总体分析

公测

  • 中测(基础与进阶):
    • 这一单元的作业相比于第一单元,在中测方面可以说变得更加简单了。没有了WF的检测,基本上随便写写就能过中测,更何况中测的难度肉眼可见的降低了
  • 强测(正确性):
    • 强测的正确性其实也不是特别难搞。在这三次作业中,我只在我第三次作业的第一个架构中发现了正确性bug,但更换了正确性有保障的新架构后,就没有特别严重的bug了。和中测同理,在没有WF的情况下,通过强测的正确性也不太困难。
  • 强测(性能):
    • 第一次作业没有性能分,直接跳过
    • 第二次作业我一开始的思路是,ALS比较垃圾所以我要用Look。接下来我写了Look算法的底层,加入了常数优化和转向优化。在周一晚上和同学讨论之后,发现了输出流可以重定向,由此衍生出来自己的Look+纯Look+ALS的三电梯模式。受于时间限制和没有写出SSTF或随机+搜索,性能分很低
    • 第三次作业我快被自己的性能蠢哭了。我首先从第二次的架构继承了一个出来,但是有软件性的死锁bug。换了新架构后,采用非常简单的动态规划+Scan算法,性能分几乎为0。事后想来,主要的bug还是出在Scan身上。用Look肯定会更好一些。

互测:

  • 这一单元的互测总体来说就是两个字:无聊。。
  • 在没有WF并且没有Tmax的环境下,只要好好写作业并做一些基础的测试,应该都没有什么正确性bug。与同学交流后总结出,这次的bug主要还是线程安全问题,也就是硬件问题。当然软件导致死锁的事情也时有发生,不过一般在提交前就解决了。
  • 虽然事后发现并没有正确性bug,但谁能在互测阶段就如此自信呢。在考虑到自己的实际能力比较低与可能出现的强测备份样例后,我这次的互测策略大概是:随便扫几个,重点关照类比较神奇的扫几个,然后开始空刀刷到16刀。在匿名的互测屋中,我既无法确定对方是扫完后没查到bug还是压根儿不会扫,又无法确定我这里扫出来没bug是真没bug还是数据生成器或SPJ有问题。因此,第6次作业我空刀8刀,第七次作业我空刀14刀。也许只有达到16刀的限制我才能安心吧。

作业内容分析

  • 第一次作业不是一般,也不是简单,而是非常简单。有多简单呢?之后的类图或者方法分析我就不讨论第一次作业了。下面直接贴出我第一次作业的全部代码:

    import com.oocourse.TimableOutput;
    import com.oocourse.elevator1.ElevatorInput;
    import com.oocourse.elevator1.PersonRequest;
    
    public class Main {
        public static void main(String[] args) throws Exception {
            ElevatorInput elevatorInput = new ElevatorInput(System.in);
            int height = 1;
            PersonRequest task;
            TimableOutput.initStartTimestamp();
            while ((task = elevatorInput.nextPersonRequest()) != null) {
                Thread.sleep(500 * (Math.abs(height - task.getFromFloor())));
                TimableOutput.println("OPEN-" + (height = task.getFromFloor()));
                TimableOutput.println("IN-" + task.getPersonId() + "-" + height);
                Thread.sleep(500);
                TimableOutput.println("CLOSE-" + height);
                Thread.sleep(500 * (Math.abs(height - task.getToFloor())));
                TimableOutput.println("OPEN-" + (height = task.getToFloor()));
                TimableOutput.println("OUT-" + task.getPersonId() + "-" + height);
                Thread.sleep(500);
                TimableOutput.println("CLOSE-" + height);
            }
        }
    }
  • 下面从第二次作业开始分析。

    • 第二次作业正确性也比较简单,维护一个等待队列和内部人员队列,然后直接向两边查找写Look算法即可。事后想来,第二次作业的优化其实很没有必要。理论上说,在有了输出流这个架构之后,完全可以写成Scan算法+随机概率p的转向。因为这样便可以涵盖几乎所有的情形。如果p按照常数从0.0跑到99.9,那么小概率能出现OPT。如果p是取决于当前状态(高度,方向,队列人数,队列人的状态)的话,估计很容易出现OPT。如果构造阶数比较高的马尔科夫模型,那不用多策略都有可能出现OPT。至于NN什么的,随便yy一下就好了。真放在OO课程中是不可能有人直接调model的。
    • 除了这种正常的基于期望的优化,还有另一种也是事后诸葛亮的基于数据点的优化。如果能提前摸到强测数据的针对性,那应该每一个极端情况写一个算法然后多策略,应该效果也不错。
    • 说了这么多,实现起来我就比较菜了。我只实现了Look+轻微的优化,ALS没写对,SSTF没写,随机性更是没有利用起来。不说了,说多了都是泪
  • 然后是第三次作业。

    • 总的来说,第三次作业我真是蠢爆了。我采用的是比较安全比较灵活的架构,但是性能爆垃圾。原因在于,我采用了类似Scan的算法。换句话说,如果底层忙而高层出现了一个请求,那么我的三个电梯都会被吸引上来。我曾经diss的分配实际效果比我高到不知道哪里去了。
    • 我的主要方式是,建立建筑类,输入一个请求就创建一个人,当他的高度达到了他的target并且他处在任一部电梯的外部,那么就销毁他。然后电梯Scan的调度,每到一层先看要不要开,如果要开就把内部人员全部踢出去,这样可以比较方便的实现任意换乘和高并发下的动态进入。然后相对的实现judgeIn方法即完成任务。总体代码量比较小
    • 线程安全方面,硬件(底层,单例类,交互等)主要靠线程安全容器无脑实现。软件(死循环,死锁等等)主要靠架构避免。我电梯为主的硬件方面,不会产生任何轮询相关的问题,无脑Scan虽然性能爆垃圾,但是正确性比较好保证。
    • 性能方面,这次的性能应该使用动态绑定,或者说动态分配的技术。我这次的性能方面,其实是一种静态分配,即任何一个任务,都同时分配给了3部电梯。实际效果其实还不如我曾经diss过的另一种静态分配——只分配给一部电梯。在我与同学讨论后采用的能开门即全部OUT的基础上,实现动态绑定还是不太困难的。但是,由于个人能力原因,我知道周二中午才完成新架构的实现,周二晚上才进行了基础的测试,因此性能爆零。

互测的收获

  • 这一单元互测的收获大概可以直接跳过了叭

公测互测bug分析与总结

  • 如果性能bug不算bug的话,那这次公测互测我没有被找到bug。不过在于同学讨论后,我发现主要的bug集中于软件的隐形死锁。我自己之前也出现过A电梯没有15楼的需求却有着15楼的欲望,欲望得不到满足于是在15层疯狂日门的情况。

优化分析

  • 总体来看,这一单元的正确性没有特别多的问题,主要问题还是出在性能上。
  • 我在优化的时候体会到,优化是没有极限的。不是OPT的算法越优化,就越会发现确定性算法是有局限的。除非超越确定性算法。。。。
    • 我在优化中经常发现,面对各种各样的情况,想出各种各样的算法,最终都会追溯到随机性。我觉得,一个面向未知进行优化的模型,几乎只能依靠经验+概率。概率如何采用?我曾经尝试过完全随机,仅依赖当前状态这两个算法,并且探索过马尔科夫模型的可行性(然而太菜写不出来)。如果不想把决定权交给random,我只能通过主观判断大概率时间进行调度。
    • 当然,这种根据经验获取输出的当然不能无脑推给NN,还是要自己想一些算法的。无脑Scan一时爽,强测出分火葬场。对于一个算法完全0基础的人来说,利用确定性算法进行优化难且不实际。我在与同学讨论后发现,利用随机性的话,是有概率超过dalao写的高级确定性算法的。
    • 不过正如我之前想过的另一个问题:暴搜暴死,随机算法随机死。只要不是确定性的多项式算法,都有原地爆炸的可能。以我现在的视野,能看到的最逼近OPT的算法就是隐马尔科夫模型了。
  • 提到优化,不仅有上面提到了算法级的优化,还有很多常数级的优化。
    • 在经历了DS大作业后,我感觉常数优化一无止境而不稳定,因此从一开始就没有做出过多的常数优化。第二次作业出现了一些小插曲,不过第三次作业确实可以看到,常数优化没人权,不做也罢

自嗨

  • 第一次作业被晾了那么久了,拿出来说说吧
    • 我一开始是按照第七次作业没有超载的模式来构建第一次作业的。写了一部分之后我发现,他给的输入是阻塞式的。考虑到傻瓜调度的特殊性与没有性能分的客观实际,我想拿这次作业来玩一玩。我写出了一个30多行的程序。在与同学讨论并进行简化后,我成功压缩到了24行,轻松地完成了第一次作业。
  • 不得不说,第一次作业还是没啥好说的,直接从2开始。第二次的优化方案和可能的优化方案前文已经提及,这里主要讲一下第二次作业之后的一些感想。
    • 第二次作业我从主观上来说还是做了一些优化。因此,我仔细查看了每一个强测样例丢分的原因。256组完全被评测姬的前摇坑了,14组没写SSTF是自己太蠢,10组很神秘,可能是常数优化不够。与之对应的,是可怕的输出流重定向。在可预见的实现难度下,第三次作业一定会有暴搜党和疯狂多策略,混合多策略党。
    • 因此我直接建议禁止输出流,增加强测样例来体现平均,试图克服运气因素(运气因素的解决方法大概是,让OPT更难写出。毕竟我自己蠢的话是赖不了评测姬的)。然而我从一开始就错误的设计了算法,因此我第三次强测同样很低。
  • 最后是第三次作业
    • 由于对第二次的架构不满,我周日重新设计了整体架构,几乎全都推倒重来。然而,我周日和周一的大部分时间被消耗在了OS的debug上,因此完全没能好好地设计算法。最后我直接采用了Scan算法,可想而知,性能爆零。不过令我惊奇的是,我居然还有一组数据性能100,可能是我比较喜欢这组数据吧。
  • 最后,中测真的不可靠,assert+err.println+简易对拍基本才能确保正确性的基本要求

转载于:https://www.cnblogs.com/shhh2000/p/10735989.html

正文到此结束
本文目录