「BUAA-OO」 OO二三事

写在前面

OO 全称 Objective Oriented，所谓面向对象，最重要的当然得有对象了，对象都没有，你去哪面向对象呢？所以趁着大二，听劝，赶紧找一个哈！

好了，言归正传，我们先说明一下什么是面向对象，所谓面向对象，就是把现实世界中的事务抽象成一个个的对象，然后通过对这些对象的操作来实现我们想要的功能。每个对象有它自己的属性和方法，属性就是对象的特征，方法就是对象的行为。比如说我们有一个学生对象，它有名字、年龄、性别等属性，还有吃饭、睡觉、学习等方法。

值得注意的是，面向对象只是一种设计思想，它并不是某个语言的专属。大家想想我们大一学习的 C 语言，难道它无法实现面向对象编程吗，答案当然是否定的，类可以是结构体，方法可以是函数指针，然后问题就迎刃而解了。那么有同学又要说了，这也太难了，从来都没写过函数指针啊！没错，写不出来是你菜，可不是人家 C 语言实现不了哦😥。课程组之所以为我们选择 Java 来实现面向对象编程主要是因为 Java 提供了很多现成的库和工具，让我们可以更方便地实现面向对象编程，同时也可以让我们更好地理解面向对象的思想。

关于面向对象的思想，个人认为在 OOpre 的博客中已经讲得较为详尽，大家具体可以参照这篇 Blog: OOpre闯关有感。当然，在正课中如果遇到了新的有用的思想我会在这里跟大家补充分享的。

本着前人栽树，后人乘凉的原则，笔者希望可以将自己每单元较为成熟的架构和大家分享，帮助大家省去重构的麻烦。同时分享几个容易被hack的点，帮助大家在编程过程中规避bug。(如果大家的作业和2026年的很像的话希望可以帮助到大家)😁

Unit1

架构

本单元主要是表达式计算，表达式的计算主要分为三大步：词法分析,语法分析和计算结果。词法分析主要是将输入解析成token，语法分析主要是将token解析成抽象语法树，计算结果主要是通过访问抽象语法树来计算结果。具体的实现细节请看笔者的架构图。

这里是Unit1的设计的类：

这里是Unit1架构简图：

Mainclass是程序的入口，负责调用各个类来实现客户要求的功能。在Mainclass内部首先要调用的就是input类，负责从标准输入中读取表达式(这里强烈建议实现Input类)，然后将输入的表达式传递给lexer类进行词法分析，得到一个token列表，然后将token列表传递给parser类进行语法分析，得到一个抽象语法树，最后将抽象语法树调用Poly类进行计算，得到最终的结果并调用output类进行输出和优化(这里依旧强烈建议实现Output类)。

在上述过程中，无论是选择表达式、求导还是函数等等新增的功能都算作是 Factor。架构如此清晰，你怎么能错呢，牢弟？

Unit1-Hack点

如果你有一个清晰的架构，你几乎不可能出现WA的问题，大多是TLE问题，但是这个问题真的很恶心，因为评测机几乎测不出来这种边界bug这就需要大家从往届学长留下的测试点中找点灵感了。

hack点1：选择表达式

我问你，[(1==1) ? 1 : 一坨],后面这一坨你是算还是不算？算了的话那你几乎强测就会被挂掉了，所以我们只需要条件命中时计算，条件未命中时跳过就好，像这样：

 Polynomial polyA = leftCond.toPoly();
 Polynomial polyB = rightCond.toPoly();
 Polynomial tmp = new Polynomial();

if (polyA.equals(polyB)) {
     tmp = trueBranch.toPoly();
 } else {
     tmp = falseBranch.toPoly();
 }

hack点2：递推函数

这里其实课程组并没有那么苛刻，提前存储之类确实是好办法，但是其实只要大家不用那种最笨的递归都可以过。完全可以用到再算啊，没问题的，只要你在算的过程中使用中间变量稍微存一下就行了，没那么多所谓的限制。

举个简单的例子：

tmp = 3*a + 4*b
a=b
b=tmp

It’s okay，完全没有问题的。

hack点3：提公因式优化

提公因式其实是一个较为简单的优化，大家还是有必要实现的，但是在实现的过程中由于exp内部本质也是一个Polynomial，所以在实现化简过程中会反复调用optimizePoly和optimizeExp函数，导致递归过深，带来超时的问题。解决这个问题其实也很简单，引入一个memoMap就行，只要我们在化简过程中算出来过，就把他存下来，再用到的时候直接取值返回，就可以避免重复计算了。

public static String optimizePoly(Polynomial polynomial) {
        Map<Polynomial, String> memo = new HashMap<>();
        return optimizePolyInternel(polynomial, memo);
    }

后续只要将momoMap传递下去就行了，具体的实现可以见笔者的个人仓库.这个memoMap的思想还是有必要学习一下的，毕竟在很多递归的场景下都可以用到，能够有效的减少重复计算，提高效率。

关于优化

这也是本单元我想讲的核心。我希望诸位在优化之前问自己几个问题：我为什么要优化？我要怎么优化？我的优化需要花掉我多少时间？如果你在思考了三个问题之后一拍桌子，“没问题，我就这么干了！”那你就去，遵从内心就好。

对于第一单元来说，我为什么优化？因为优化可以挣性能分，可以提升成绩。这是实打实的，咱不扯别的，做优化就是为了卷。那我要怎么优化呢，首先最简单的合并同类项，把系数为正的项提前。这是最好实现并且优化效果最明显的两步。接下来对 exp 的提公因式可以进一步优化某些表达式，最后还可以将exp的内容拆开分别提公因式，但是这个操作及其极其复杂，需要花费我大量的时间去实现。于是我选择了放弃最后一步优化，腾出时间来趁着春光正好出去走走，毕竟大学就四年，一直卷也没意义。当然这只是我的个人观点，可能有些同学实现最后一步优化就一顿饭的功夫，那你是大哥，你放开干；可能有些同学不拿这个性能分心里非常难受，那你也去干，总之遵从内心，在看到OO成绩时问心无愧就好。

所以，要不要优化，要优化到什么程度，还请诸位三思🫡。

Unit2

很多人觉得电梯月是魔鬼月哈，但是从个人角度来讲，我真的没觉得他和前一单元有什么区别。虽然我也不知道为什么，可能是对多线程的理解每个人不一样，抑或是我没有实现影子电梯？总之电梯没什么好怕的，Just Brave it!.

三次作业的迭代要求

第二单元三次作业的演进：第一次先建立基本线程模型，第二次把调度器和状态机做完整，第三次再把系统推进到双轿厢和换乘场景。

第一次作业中，我的主结构是 InputThread -> 全局 RequestQueue -> DispatchThread -> 各电梯局部 RequestQueue -> Elevator。这一版使用生产者消费者模型，把输入、分配、执行三层职责拆开，让每个电梯线程只关心自己的局部队列和轿厢内乘客。架构图如下

第二次作业加入维修请求后，系统不再只是“多部电梯并行跑”，因此我引入了 ElevState，把 NORMAL、REP_ACCEPT、REPAIR、TEST 等状态。与此同时，DispatchThread 开始真正承担“全局调度器”的角色，而不只是转发请求架构图如下：

第三次作业加入双轿厢升级和回收后，并发难点进一步上升。此时新增的 ShaftContext、ShaftState、PassengerRegistry 和 isBusyMap 让系统从“多线程执行”变成了“多线程共享资源并协同执行”。我觉得这也是二单元最核心的训练：不仅要会写线程，还要会给共享状态建模。最终的架构如下:

总体架构：

Unit2-Hack点

到了第二单元Hack点就变得多样化起来，不仅有TLE，还有各种各样的WA，每个人都有自己的原因，我把我出现的bug整理如下，如果能帮诸位在强测抢一点分那最好不过了。这里再说一句，强测很好过，恶心的数据点大多数来自互测，所以大家没必要对自己的强测太过担心

hack点1：电梯维修时输入乘客

设想一种情况，假设输入数据的限制时间是50s以内，一共有6部电梯，在49.5s时候维修5部，50s的时候放入一堆从底层到顶层的请求。那么在这种情况下你的乘客会被分配给谁呢？如果全部分给了那部不在维修中的电梯那你不就超时了吗。

所以我们在电梯维修状态下也需要为其分配乘客，即向电梯的等待队列里面添加元素，但是要注意RECEIVE输出的时机，要符合题目的要求。

hack点2：电梯队列的RECEIVE信息和增加元素信息的顺序

如果先放入队列再输出RECEIVE信息像这样：

queueMap.get(elevatorId).offer(request);
TimableOutput.println("RECEIVE-" + ((PersonRequest) request).getPersonId() + "-" + elevatorId);

在放入队列后电梯进程会立刻开始处理，这就意味着可能存在乘客已经被从1楼运送到2楼了，程序才慢吞吞地输出我收到乘客请求了的信息，显然这个不科学的。

hack点3：双轿厢电梯碰撞

评测机判断双轿厢电梯是否碰撞主要看的是输出信息而不是访问电梯的状态，所以保证电梯不碰撞的模块必须是原子操作，尤其不能漏掉输出。示例代码如下：

public synchronized String arrive(int elevatorId, int targetFloor) {
    while (!canArrive(elevatorId, targetFloor)) {
        // wait
    }
    // 更新楼层
    if (elevatorId == mainId) {
        this.mainFloor = targetFloor;
    } else {
        this.backupFloor = targetFloor;
    }
    notifyAll();
    // TODO 输出Arrive信息，一定要保证输出也包含在里面
    return Floor.toString(targetFloor);
}

hack点4：电梯wait无法醒来导致死循环

我的程序的wait逻辑是在电梯等待队列为空并且电梯等待队列没有达到end状态时才会进入wait，然后等待requestqueue的notify来唤醒。这个看起来非常合理，但是我们可以看一下这个数据点：

[1.0]UPDATE-1
[1.0]UPDATE-2
[1.0]UPDATE-3
[1.0]UPDATE-4
[1.0]UPDATE-5
[1.0]UPDATE-6
[2.0]1-WEI-60-FROM-F1-TO-F7
[15.0]RECYCLE-7
[15.0]RECYCLE-8
[15.0]RECYCLE-9
[15.0]RECYCLE-10
[15.0]RECYCLE-11
[15.0]RECYCLE-12
[15.5]2-WEI-60-FROM-F1-TO-F7

在15秒的时候，只有电梯1,2,3,4,5,6可以被分配乘客请求，但是电梯处于DOUBLE状态，无法到达F1接客，所以在我的Dispatch算法中不会被分配乘客请求，导致电梯线程一直在wait，无法被唤醒，无法唤醒就无法切换状态，无法切换状态就无法被分配乘客请求，形成死循环。

我的切换状态函数只在电梯run的情况下才可以执行：

public void run() {
    while (true) {
        syncStateWithShaft();     // 状态切换
        // 其他逻辑
    }
}

解决方法比较简单的就是让电梯在wait的时候不要无限等待被唤醒，而是每隔一段时间就自己醒来检查一下状态wait(20)，这样就可以避免死循环了。

hack点5：判断条件缺失导致Dispatch提前终止

在判断Dispatch结束的条件时我考虑了三个情况：

• 全局队列为空
• 输入结束
• 没有电梯处于busy(特殊)状态

细细想来有一个致命的漏洞，当全局队列为空并且电梯为double态时，是不是满足上述条件呢？当然，此时Dispatch终止，如果电梯在F2放下了换乘乘客，那这个乘客就永远无法被调度了。顺理成章，我们加入两个判断条件：

• 电梯里面有人 !elevator.isEmpty()
• 电梯的等候队列有人 !queueMap.get(elevatorId).isEmpty()

到这里似乎上述问题已经得到了解决，更阴间的还在后面。。。（真的是卡bug届领域的大神啊，我真的服了）

乘客从电梯等候队列移出，还没有放到电梯里面，这个空档期就是Dispatch停下来的绝佳时期。显然，这一顿修改下来无异于是在堆屎山，但是因为这个最后一次作业了，我选择继续打补丁，新增handlingPassenger变量来管理上下客：

private void open() {
    handlingPassenger = true;   
    // 上客逻辑
    handlingPassenger = false;
}

只有在handlingPassenger为false时才能停下Dispatch

hack点6：CPU等待时轮询导致CPU运行超时

在Dispatch逻辑中，如果全局队列空了错误写法是这样的：

Request request = requests.poll();
if (request == null) {
    continue;
}
dispatch(request);

发现null立刻轮询，导致CPU一直在运行，最终被评测机挂掉了。正确的写法应该是：

Request request = requests.poll();
if (request == null)  {
    sleepBriefly();
    continue;
}
dispatch(request);

以上就是第二单元笔者认为比较容易挂的几个互测数据点了，希望能对大家的开发过程有点帮助吧。最后还是那句话，强测很好过，恶心的数据点大多数来自互测，所以大家没必要对自己的基础分数太过担心，just do it！

Unit3

第三单元的主题是JML与规格驱动开发，总体来说没什么难点，只需要照着课程组给出的JML来翻译成代码即可。其实你甚至不需要知道整个项目是什么意思，像个傻子一样翻译就行。

Unit4

第四单元考察的是UML建模思想。依次学习了类图，状态图，顺序图的建模。为了加深大家对这三类UML图的理解，我在这里简单的陈述一下具体的知识点。

类图

UML类图主要用于展示类，类的属性，类的方法，以及类之间的静态关系。类的表示方法为三层矩形框：

• 第一层为类名
• 第二层为类的属性
• 第三层为类的方法

常用的标示符：

• +public
• -private
• #protected

示例如下：

类与类之间的6种关系

• 依赖（Dependency）：一个类临时用到另一个类。比如A类的某一个方法把B类作为参数传入。
• 关联（Association）：类和类有长期的服务关系。比如A类把B类作为全局变量。
• 聚合（Aggregation）:整体和部分的关系，部分可以离开整体单独存在。比如A类包含B类，但是B类的生命周期不归A类管（汽车和轮胎）。
• 组合（Composition）：整体和部分的关系，部分不能离开整体而存在，整体对部分强拥有。比如A类包含B类，并且B随着A的创建而创建，销毁而销毁（人和大脑）。
• 实现（Implementation）：类实现接口。等于Java中的impements
• 继承（Generalization）：子类继承父类,A类继承B类。等于Java中的extends

状态图

UML状态图用于描述一个特定的对象在其生命周期中所经历的各种状态。主要包括以下四个元素：

• 初始状态
• 状态
• 转换
• 终止状态

状态转换三要素：

• Trigger（必填）：触发状态改变的函数。
• Guard（非必填）：只有当bool值为真时转换才能发生。
• Action（非必填）：状态转换时顺便执行什么操作。

顺序图

顺序图按照时间顺序，展示了对象之间互相发送消息，协同完成某个任务的流程，主要包括以下x个要素：

• 对象
• 消息
• 时间轴

不同对象之间传递消息，并且时间自上而下地流逝，越靠下的消息发生的时间越晚。

其中消息类型有以下四种：

• 同步消息：发送方发送请求后，必须等待接收方返回数据才能继续进行
• 异步消息：发送方发送请求后，无需等待接收方返回数据就能继续进行
• 返回消息：接受方处理完同步消息后，将结果返还给发送方。
• 自身调用：对象自己调用自己内部的方法。

实际上画的时候用Message让人看懂就行了😁

后记

行文至此，本学期的OO博客要跟大家说再见了，我们从递归下降法，闯关到多线程，最后归结到JML规格开发和UML类图设计。OO的核心目的并不是把我们练成coding大神，而是通过课程的学习掌握面向对象设计的思想，培养工程能力，为日后走向工作岗位打下坚实的基础。希望以上的知识能带给大家些许帮助，抑或是繁忙的学习生活中的一点慰藉。Cordial-Kid与你同在🫡。

Lyrics Sharing

你会翻过山看到万丈晴天
飞鸟正越过海面
你会迎着风放着胆唱着歌
把风景都看遍