面向对象

OO第四单元总结——UML 一.正向建模与开发 ​ 在本单元中，主要的训练目的是通过画UML图进行正向建模与开发，即首先通过画UML图(类图/状态图/顺序图)等设计程序的架构，然后进行代码实现。 ​ 在本单元作业中，我主要通过类图进行正向建模与开发。在进行代码实现之前，首先画类图来确定出大致的属性、方法、交互关系等，关于一些比较具体的实现例如参数等先略去，在完成代码过程中进行补充。 二.架构设计 ​ 本单元的架构设计在三次迭代中保持的相对稳定，除了类中的方法等细节变动，在类的层面上遵循着面向对象的奥义，对于出现的每一个事物都建一个类，在第二次作业中新增漂流角类。 第一次作业 第二次作业 第三次作业 ​ 在三次作业中，我首先进行大略的UML类图的绘制，然后根据第一版类图进行代码构建，在编写代码的过程中不断完善细节和类之间的交互关系，反过来对UML图中的关系进行修改，达到了代码设计和UML模型之间的追踪关系。 三.架构设计思维演进 ​ 第一单元聚焦于层次化设计，通过表达式计算这一实际问题来引导同学们进行表达式->项->因子的递归下降建模。在第一单元中，我对于递归下降的理解是不断深入的，在架构设计上，针对递归下降的结构进行设计，即对表达式、项、因子三个层次进行建模，其中因子设计为一个接口，不同种因子设置为接口的实现。 ​ 第二单元聚焦于多线程设计，通过新主楼电梯运行这一实际问题来引导同学们进行多部电梯之间的多线程协作编程实践(个人体感上第二单元是最难的，难以复现的bug让人恼火)。在第二单元中，我的架构设计主要在于多线程之间的交互关系上：输入线程、调度器线程、电梯线程之间使用怎样的数据结构，怎样降低耦合度，提高内聚度。 ​ 第三单元聚焦于JML规格化设计，通过迷你社交网络这一实际问题来引导同学们根据JML代码来编写实际的JAVA代码。这一单元实际上对于架构设计没有要求，同学们要完成的任务在于根据已经给出的架构进行规格化代码编写，主要的问题是规格与实现分离：给定了JML规格，但不指定具体实现，这其中的算法效率需要同学们进行设计。我感触比较深的点除了使用复杂度较优的算法之外还有进行复杂度分摊：对于一个常使用的复杂度较高的算法可以将他的复杂度分摊在其他较少使用的方法中，达到全局优化的效果。 ​ 第四单元聚焦于UML正向建模与设计，在这单元中我尝试首先通过UML类图进行代码架构的建模与设计，然后在代码编写的过程中优化类之间的协作关系以及数据结构，最后反过头来完善UML图中的细节以及修改与代码不符的设计。在第四单元中，我更加深刻地感受到架构设计的重要性，一个好的架构设计可以为代码实现减小实现难度同时维持较好的扩展性，而架构设计的奥义在于高内聚低耦合，在OOpre以及OO课程中我的感受就是“对每一种事物都建一个类来完成对应的职责”。 四.测试思维演进 ​ 在四个单元中，我都是采用边缘数据测试+大量随机数据压力测试的方法，在第三单元中，采用了参数化JUnit测试。 ​ 在代码编写过程中，我会编写一些简单的样例对已经编写好的代码进行测试，相当于对每一个方法都进行一个小测试，在过程中不断debug，防止最后bug堆积增加debug难度。 ​ 完成代码编写后(首先跑样例)，手动构造一些从简单到极端数据测试数据范围、运行时间、算法效率等(当然本机运行时间和评测机完全不同，只是进行不同实现间的比较)。然后进行大量随机数据压力测试，这里要感谢DPO的评测机以及Kai_ker的评测机支持。 ​ 以上都是进行黑盒测试，在时间充裕的情况下，我还会进行白盒测试，即从头到尾读几遍自己的代码，再推敲一遍实现细节，往往白盒测试能够触碰到一些黑盒测试碰不到的角落bug。 五.课程收获 ​ 从OOpre初次接触JAVA编程，到OO课程结束已经可以独立编写千行级别有一定质量的代码，我在一次次代码作业中提高编程能力，在一次次博客作业中总结编程经验。从赤手空拳到满载而归，这是一个充满艰辛的过程。 ​ 面向对象思想是一种好用且高效的思想，理解面向对象思想并不难，通俗的说就是对每一种事物都理解为一个类，有属于自己的职责；但是要想真正写好面向对象代码则需要在不断实践中掌握各种设计模式、不断提高架构设计能力、不断体会高内聚低耦合的设计思路，这也正是课程组在作业中要求我们掌握的。 ​ 彼时的少年，站在成长的巅峰，回首来时，满路崎岖。诚实地说学习OO的过程于我而言是痛苦的，难忘深夜新主楼debug的种种艰辛，但是带给我的代码能力的成长也是非常之大的。 ​ 在写OO的过程中，我喜欢用Pomodoro Logger记录自己努力的时间，hhhhh真是花了很多时间(只展示时间最长的两次作业)。 ​ 如今在OO课程结束的节点，我很赞同OO是一门绝世好课，无论从课程制度还是难度设置上都越来越合理(可以实实在在地给予同学们一个完整的青春)。感谢老师、助教、研讨课上高谈阔论的同学、Kai_ker哥在我的OO课程中赠予的帮助。写完了这篇博客，我就要和2024春季的OO课程说再见了，心头感慨万分，甚至有些舍不得，我深知对我能力提高这样大的课程恐怕再难遇到，诚惶诚恐，用每一行代码，每一篇博客小心翼翼地记录下属于我的OO时光。

OO第三单元——JML 一. 单元架构设计 ​ 相比于前两单元需要自行设计架构，充当架构设计师的角色，U3不需要设计架构，需要完成的任务是依据课程组给出的架构设计合理的类协作关系以及依据JML写对应的代码(码农日常)。 ​ 关于课程组给出的架构可以简单概括如下图 二. 算法实现与性能 ​ 本单元更加关注的是对于既定的JML或者说给定的功能要求，具体的算法实现和效率。强测中对于性能有一定要求，性能不佳会爆CTLE。我的理解中，CTLE字面意思上是CPU时间超时，换句话说其实就是**“算的次数太多“**，在本单元作业中，可以采用缓存一些计算复杂度较高的结果进行优化等，下面基于每一次作业进行分析。 1. hw9 ​ 这一次作业中主要的性能考察点是关于query_block_sum中查询两个点是否联通的功能。在本次作业中，通过addRelation和modifyRelation可以建立起一个社交图，这其中需要注意的是modifyRelation操作可能删边。很多大佬同学实现了可以删边的并查集，我选择了实现较为简单(懒)的BFS。使用BFS进行联通查询面对大量查询指令有CTLE风险，故可以考虑对BFS进行一点简单优化，例如使用双向BFS。关于双向BFS，其实就是从起点和终点同时开始搜索，面对图中点非常多的情况可以大幅减少开销。 ​ 下面是一张摘自广度优先搜索之双向bfs（实操篇）-CSDN博客的一张很形象的图片。 ​ 双向BFS的优势其实就是大幅减少搜索宽度，减少遍历一些点，让它看上去没有那么暴力。由此还有一种优化的思路就是均衡取节点。当我们从给起点和终点分别设置的队列中取节点时，可以选择从size较小的那一个队列中取出(size较大的那一方说明他每一层中的宽度较大，遍历开销大)。下面给出我的具体实现（主要想法是起点终点两个队列两个visited数组，当前遍历如果另一边如果遍历过，结束）： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 import java.util.HashMap; import java.util.LinkedList; import java.util.Queue; public class BreadthFirstSearch { public static boolean isConnected(MyPerson person1,MyPerson person2) { if (person1.getId() == person2.getId()) { return true; } HashMap<Integer, Boolean> visited1 = new HashMap<>(); HashMap<Integer, Boolean> visited2 = new HashMap<>(); visited1.put(person1.getId(),true); visited2.put(person2.getId(),true); Queue<MyPerson> queue1 = new LinkedList<>(); Queue<MyPerson> queue2 = new LinkedList<>(); queue1.add(person1); queue2.add(person2); while (!queue1.isEmpty() && !queue2.isEmpty()) { if (queue1.size() < queue2.size()) { MyPerson now = queue1.poll(); if (next(now,visited1,visited2,queue1)) { return true; } } else { MyPerson now = queue2.poll(); if (next(now,visited2,visited1,queue2)) { return true; } } } return false; } private static boolean next(MyPerson now,HashMap<Integer,Boolean> visited, HashMap<Integer,Boolean> visited2,Queue<MyPerson> queue) { for (Person next : now.getAcquaintance().values()) { if (visited.containsKey(next.getId())) { continue; } if (visited2.containsKey(next.getId())) { return true; } queue.add((MyPerson) next); visited.put(next.getId(),true); } return false; } } ​ 对于另一个查询指令query_triple_sum也需要进行动态维护，在addRelation加边和modifyRelation删边时进行判断，并更新qts的值。 ...

OO第二单元第三次作业 [toc] 0.本次作业新增需求 新增一种RESET请求，可以将单部电梯重置为双轿电梯 [时间戳]RESET_ACCEPT-电梯ID-换乘楼层-每个轿厢的满载人数-每个轿厢移动一层的时间(单位s) 重置电梯两个轿厢的参数相同（满载人数、移动一层的时间） 重置完成后轿厢A默认在换乘楼层的下一层，轿厢B默认在换乘楼层的上一层 轿厢A只能在换乘楼层及以下运行，轿厢B只能在换乘楼层及以上运行 两个轿厢不能同时处于换乘楼层 特别地，双轿厢电梯可以不受RECEIVE约束地从换乘楼层移动一层以离开换乘楼层 保证双轿厢电梯不会接收到第一类重置请求和第二类重置请求。 换乘楼层在3层和9层之间 双轿厢电梯耗电量为$\frac 1 4$ 1.处理流程分析 ​ 本次作业中主要的任务即为处理新增的RESET请求，对于上次作业已有的调度策略没有进行改变，目标比较明确。下面是时序图 1.1 UML时序图 1.2 新增RESET请求的处理 1.2.1 Elevator ​ 本次作业中对于双轿厢RESET请求的类协作与第二次作业中普通重置请求相同。这里我对于RESET请求的处理方式是接收到双轿厢RESET请求时新建一个线程，将原来的线程作为A轿厢，新建的电梯线程作为B轿厢。这里首先给出电梯新增的几个属性 1 2 3 4 5 6 7 //Elevator private char elevatorType = 'C'; // 轿厢类型 A B private int transferFloor = -1; private int lowerLimit = 1; private int upperLimit = 11; private Flag busyFlag = null; // 一组电梯共享一个flag进行通信 private AtomicInteger personSatisfied; elevatorType：电梯的类型，初始时电梯的类型为C类型，双轿厢重置后修改为A/B类型 lowerlimit/upperlimit：电梯的运行楼层限制，用于Dispatcher中对于符合运行范围电梯的筛选 transferFloor：换乘楼层(似乎没用，不是lowerlimit就是upperlimit) busyFlag：用于控制双轿厢电梯在换乘楼层互斥的需求，这里借鉴了讨论区中实现线程安全类的思路 personSatisfied：计数器，所有电梯线程和输入线程的共享变量，当一个乘客需求被满足(送到指定楼层)，该原子类型+1 ​ 参考NormalReset在第二次作业中的实现方式，DoubleCarReset我选择相同的实现方法，当电梯拿到DoubleCarReset请求之后立即进行重置 ...

OO第二单元第二次作业 [toc] 0.题目新增需求 乘客不再固定电梯接送，设计电梯调度策略 增加RECEIVE输出，避免自由竞争策略 增加RESET请求，时长1.2s，在RESET期间电梯处于静默状态(不可以开关门、移动、RECEIVE等)，重置电梯 1.处理流程分析 1.1 电梯调度策略 ​ 在本次作业中，需要设计将乘客分配给合适的电梯的调度器(补第五次作业偷的懒)，我的设计中选择将调度器作为一个线程实现，输入线程与调度器线程交互，调度器线程与六个电梯线程交互。对于单个电梯运行的策略我保留了第五次作业的LOOK算法，对于多部电梯的分配策略，我选择了性价比较高的调参方法，性价比体现在代码量较少的同时能够拿到比较好的性能分数。UML时序图如下 1.1.1 UML时序图 1.1.2 调参算法 ​ 所谓调参算法其实就是选取几个有关电梯的指标，给这些指标赋予合适的参数，为每部电梯计算出得分，选择得分最高的电梯进行分配。我选取的指标有电梯接到该乘客需要走的距离，电梯中人数，电梯等待队列中人数，电梯容量，电梯速度。 距离：这里距离的计算是不准确的，没有找出电梯运行的上确界或下确界，即没有找出电梯运行到哪里就可以转向，而是同一按照1/11处理 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 private int getDistance(int fromFloor,int toFloor,int curFloor,boolean direction) { int distance = 0; int flow = (direction) ? 1 : -1; if ((toFloor - fromFloor) * flow > 0) { // 乘客移动方向与电梯当前移动方向相同 if ((fromFloor - curFloor) * flow >= 0) { // 电梯沿当前方向能接到乘客 distance = abs(fromFloor - curFloor); } else { if (flow == 1) { distance = 20 - curFloor + fromFloor; } else { distance = 20 + curFloor - fromFloor; } } } else { if (flow == 1) { distance = 22 - curFloor - fromFloor; } else { distance = curFloor + fromFloor - 2; } } return distance; } 电梯状态：电梯状态这个参数实际上是电梯容量、电梯中人数、电梯等待队列中人数三个量经过调参得来的，可以适当增加电梯等待队列中人数的权重，避免给一部性能好的电梯分配太多乘客，这样的性能可能还不如大家都运行 ...

OO第二单元第一次作业 [toc] 0. 前置知识 0.1 进程与线程 计算机中，我们把一个任务称作一个进程(Process) 在一个进程中，还包含一个至多个子任务，称为线程(Thread) 进程与线程是包含关系，一个进程中可以包含多个线程 线程内执行顺序确定，线程间执行顺序由操作系统调度，无法确定 tips:此单元作业中不要使用调试，会影响线程，转为使用打印调试法 0.1.1 创建新线程 Java语言中内置了多线程支持，当Java程序启动的时候，实际上是启动了一个JVM进程，然后JVM启动主线程来执行main方法，在main方法中我们可以启动其他线程 继承Thread类 从Thread类派生一个自定义类，覆写run方法 public class myThread extends Thread { @Override public void run() { // ... } } 实现Runnable接口 实现Runnable接口，重写run方法 public class myRunnable implements Runnable { @Override public void run() { //... } } 创建一个新线程 Thread t = new myThread(); Thread t = new Thread(new myRunnable) 启动新线程 t.start() 注：start()方法会在内部自动调用实例的run方法，直接调用run()方法不会创建新线程 线程入口run()方法的模版 public void run(){ try{ while(true){ if(has new task) { //... } else { break; } } //do something to finish } catch(InterruptedException e){ //该线程被调用interrupt //... } //do something to finish } 0.1.2 线程的状态 在Java程序中，一个线程对象只能调用一次start()方法启动新线程，并在新线程中执行run()方法，一旦run()方法执行结束，线程就结束了 ...

OO第一单元第三次作业 0. 题目需求 ​ 本次作业在上次作业的基础上主要增加了求导因子，同时自定义函数表达式中允许调用已经定义过的表达式。 求导因子(归结在因子中)，求导因子形式为dx(表达式)，含义为对表达式中的x求导，其中可以出现多次求导的情况，但是自定义函数表达式中不会出现求导算子 ==关于求导的形式化表述== 求导算子 -> ‘dx’ 求导因子 -> 求导算子 空白项 ‘(’ 空白项 求导因子 空白项 ‘)’ | 求导算子 空白项 ‘(’ 空白项 表达式 空白项 ‘)’ 注意：求导算子内部可能有表达式，应该调用parseExpr 注：形式化表述中允许了多层求导的情况，例如， dx(dx(x)) ==可能用到的求导公式== $$ I.f(x)\space =\space c\space ,f’(x)\space = \space 0 $$ $$ II.f(x)\space = \space x^n,f’(x) = nx^{n-1} $$ $$ III. f(x)\space = \space exp(x),f’(x) \space = \space exp(x) $$ $$ IV.[f(g(x))]’\space = \space f’(g(x))g’(x) $$ $$ V.[f(x)g(x)]’ \space = \space f’(x)g(x) + f(x)g’(x) $$ ...

OO第一单元第二次作业 0.题目需求分析 0.1 概念分析 本次作业在第一次作业的基础上添加了指数函数和自定义函数，其中 需要支持嵌套多层括号 新增指数因子，指数函数括号内部包含任意因子 新增自定义函数因子，自定义函数的表达式会给出且其中不会调用其他自定义函数 本次迭代表达式架构上的改变 支持前导0的十进制带符号整数 因子 变量因子，x 幂函数 一般形式：x^非负整数 省略形式：指数为1，x 指数函数：特指以e为底数的指数函数，表示为exp(<因子>)等 一般形式：exp(<因子>)^指数，注：该指数为exp()整体的指数 exp()的指数为非负整数 **省略形式：**指数为1时，写为exp(<因子>) 自定义函数 自定义函数中不会调用其他自定义函数，定义类似于 f(x,y,z) = 表达式（可能不全部包含x,y,z这三个变量） f,g,h是函数的函数名，本次作业中的自定义函数名只包括f,g,h即最多只有三个自定义函数 x,y,z是函数的形参，形参个数为1~3个，且同一函数定义中不会出现重复使用的形参 函数表达式为关于形参的表达式 函数调用的形式为f(因子，因子，因子)，例如f(x^2),g(exp(x^2),exp(x)),h(1,0,-0)，因子为函数调用中的实参，包含任意一种因子 注意：函数定义中不允许出现自定义函数，但是函数调用中的实参可以是自定义函数 常数因子 表达式因子 项 表达式 ​ 关于去括号要求中的**“必要的括号”** 指数函数调用时必要的一层括号exp() 指数函数对应的嵌套因子为不带指数的表达式因子时，该因子两侧必要的一层括号，例如 exp((x+1)^2)中(x+1)中的括号是不合法的，需要展开为不带指数的形式exp((x^2+2*x+1)) 0.2 表达式架构图 大致保留之前的架构，新增指数函数因子类和自定义函数因子类 1.处理流程分析 1.1 字符串预处理 由于自定义函数的引入，可以新增去除,后不必要的+ 1.2 语义分析 1.2.1 Lexer ​ 本次作业中，新增了EXP,F,G,H,COMMA(逗号)等token，需要增加识别功能。 1.2.2 Parser 1.2.2.1 parseExp ​ 在Parser类中新建一个方法parseExp，当我们读到的token为EXP时调用该方法进行解析。首先对括号内的因子进行解析，再对括号外的指数进行解析。 $$ exp()^n \space | \space exp() $$ public Factor parseExp() { // exp(<factor>)^<num> | exp(<factor>) // lexer : exp -> pos = pos + 4 already into the ( // 读到RP时接着往后读看有没有指数 int pow = 1;//默认指数为1 Factor innerFactor = parseFactor(); if (lexer.getCurTokenType() == TokenType.POW) { // 后面有指数 } return new Exp(innerFactor, pow); } 1.2.2.2 parseFunc 1.2.2.2.1 Definer ​ 为了成功地解析自定义函数，我们首先定义出Definer类，他的主要作用是处理自定义函数的定义以及调用。（相当于parseFunc的slave）其中定义出两个HashMap ...

OO第一单元第一次作业 0.training 想要通过课程组提供的training获取一点点思路QWQ 0.1 training-1 第一部分通过正则表达式的方法将一个只包含数字和“+”“*”符号的表达式转化为后缀表达式 思路梳理（已经提供好的代码）： Mainclass：对于该类，分析得到其处理的思路为构建出可以描述每一项的正则表达式，而后在表达式中进行匹配，再分别对获得的每一项进行后缀化(toString)，最后整体后缀化(toString)并输出 补充正则表达式如下 private static final String patternTerm = "\\d+(\\*\\d+)*"; (该表达式描述了，一项中至少有一个数字以及>=0个形如*number的部分) 上机tips：关于正则表达式，可以右键之后选择第一项进行检查 Expr：该类的重点为实现toString方法，由后缀化的项得到后缀化的表达式 若表达式中只有一项，则该项即为转换后的表达式 （例如 1 * 2 * 3） 若表达式中大于等于两项，对于前两项需要特殊处理，后面的项补充为项*的后缀化形式 StringBuilder sb = new StringBuilder(); sb.append(terms.get(0)); sb.append(" "); /* TODO */ sb.append(terms.get(1)); sb.append(" "); sb.append("+"); for (int i = 2; i < terms.size(); i++) { sb.append(" "); sb.append(terms.get(i)); sb.append(" "); sb.append("+"); } Term：该类的重点为实现toString方法，将项转化为后缀表达形式 在项的构造方法中对因子factors进行了划分，由于项只可能由数字或数字的乘积构成，使用*划分即可 String[] factorStrs = s.split("\\*"); 同Expr中toString方法，将第0个和第1个因子特判后缀化 0.2 training-2 第二部分通过递归下降的方法对一层括号，只包含“+”“*”运算符的表达式进行处理，输出其后缀表达式 思路梳理 对表达式进行层次化建模（语法树） ...