一、三次作业简单介绍

本单元作业最终需要实现一个路径管理系统。可以通过各类输入指令来进行数据的增删查改等交互。

第九次作业：

实现两个容器类 Path 和 PathContainer

实现指令：

添加路径	PATH_ADD 结点序列
删除路径	PATH_REMOVE 结点序列
根据路径id删除路径	PATH_REMOVE_BY_ID 路径id
查询路径id	PATH_GET_ID 结点序列
根据路径id获得路径	PATH_GET_BY_ID 路径id
获得容器内总路径数	PATH_COUNT
根据路径id获得其大小	PATH_SIZE 路径id
根据结点序列判断容器是否包含路径	CONTAINS_PATH 结点序列
根据路径id判断容器是否包含路径	CONTAINS_PATH_ID 路径id
容器内不同结点个数	DISTINCT_NODE_COUNT
根据字典序比较两个路径的大小关系	COMPARE_PATHS 路径id 路径id
路径中是否包含某个结点	PATH_CONTAINS_NODE 路径id 结点

 

 

 

 

 

 

 

 

 

第十次作业：

实现容器类 Path 和数据结构类 Graph 

实现指令：

容器中是否存在某个结点	CONTAINS_NODE 结点id
容器中是否存在某一条边	CONTAINS_EDGE 起点结点id 终点结点id
两个结点是否连通	IS_NODE_CONNECTED 起点结点id 终点结点id
两个结点之间的最短路径	SHORTEST_PATH_LENGTH 起点结点id 终点结点id

 

 

 

第十一次作业：

实现容器类 Path 和地铁系统类 RailwaySystem

实现指令：

容器中是否存在某个结点	CONTAINS_NODE 结点id
容器中是否存在某一条边	CONTAINS_EDGE 起点结点id 终点结点id
两个结点是否连通	IS_NODE_CONNECTED 起点结点id 终点结点id
两个结点之间的最短路径	SHORTEST_PATH_LENGTH 起点结点id 终点结点id

 

 

 

关键点 1 —— ALS(可捎带电梯)规则：

可捎带电梯调度器将会新增主请求和被捎带请求两个概念。 主请求选择规则： 　　如果电梯中没有乘客，将请求队列中到达时间最早的请求作为主请求 　　如果电梯中有乘客，将其中到达时间最早的乘客请求作为主请求 被捎带请求选择规则：

电梯的主请求存在，即主请求到该请求进入电梯时尚未完成 该请求到达请求队列的时间小于等于电梯到达该请求出发楼层关门的截止时间 电梯的运行方向和该请求的目标方向一致。即电梯主请求的目标楼层和被捎带请求的目标楼层，两者在当前楼层的同一侧。

其他：

标准ALS电梯不会连续开关门。即开门关门一次之后，如果请求队列中还有请求，不能立即再执行开关门操作，会先执行请求。

关键点 2 —— 多线程编程：

　　这是我第一次接触多线程编程。多线程就是多个线程一起去协同完成一个任务，通过充分去共享资源来达到提升效率的一种编程思想。

　　在本单元的作业中，线程安全是一个贯穿全程的问题，这部分内容处理的还算好，但对我困扰极大的是CPU时间超时问题，我对wait()、notify()机制的使用还是有很大的不熟练。

关键点 3 —— 输入输出接口：

　　本单元作业的输入输出使用的都是课程组提供的统一接口，避免了对输入输出做大量处理的麻烦。这在第一单元的作业中是让我们非常痛苦的一个地方，是bug高发地带也是优化难题之一。

 

二、SOLID设计原则

SOLID 原则基本概念：

　　程序设计领域， SOLID (单一功能、开闭原则、里氏替换、接口隔离以及依赖反转)是由罗伯特·C·马丁在21世纪早期 引入的记忆术首字母缩略字，指代了面向对象编程和面向对象设计的五个基本原则。当这些原则被一起应用时，它们使得一个程序员开发一个容易进行软件维护和扩展的系统变得更加可能SOLID被典型的应用在测试驱动开发上，并且是敏捷开发以及自适应软件开发的基本原则的重要组成部分。

[S] Single Responsibility Principle (单一功能原则)

• 每个类或方法都只有一个明确的指责。

• 类职责：使用多个方法，从多个方面来综合维护对象所管理的数据。

• 方法职责：从某个特定方面来维护对象的状态（更新、查询）。

[O] Open Close Principle （开闭原则）

• 软件实体应该是可扩展，而不可修改的。也就是说，对扩展是开放的，而对修改是封闭的。

• 对扩展开放，意味着有新的需求或变化时，可以对现有代码进行扩展，以适应新的情况。

• 对修改封闭，意味着类一旦设计完成，就可以独立完成其工作，而不要对类进行任何修改。

[L] Liskov Substitution Principle（里氏替换原则）

• 任何父类出现的地方都可以使用子类来替代，并不会导致使用相应类的程序出现错误。

• 子类虽然继承了父类的属性和方法，但往往也会增加一些属性和方法，可能会破坏父类的相关约束。

[I] Interface Segregation Principle（接口隔离原则）

• 当一个类实现一个接口类的时候，必须要实现接口类中的所有接口，否则就是抽象类，不能实例化出对象。

• 软件设计经常需要设计接口类，来规范一些行为，避免往一个接口类中放过多的接口。

[D] Dependency Inversion Principle（依赖反转原则）

• 代码应当取决于抽象概念，而不是具体实现。

• 高层模块不应该依赖于低层模块，二者都应该依赖于抽象。

• 抽象不应该依赖于细节，细节应该依赖于抽象。

• 类可能依赖于其他类来执行其工作。但是，它们不应当依赖于该类的特定具体实现，而应当是它的抽象。

 

三、三次作业的类图与度量分析

度量分析标识：

• • ev(G)　　本质复杂度

  • iv(G)　　 设计复杂度

  • v(G)　　 循环复杂度

  • OCavg　 平均方法复杂度

  • OSavg　 平均方法语句数（规模）

  • WMC　　加权方法复杂度

  • v(G)avg　平均循环复杂度

  • v(G)tot　总循环复杂度

 

第五次作业：

1、架构构思：

　　总体架构我是按照指导书的建议走的

• 主线程进行输入的管理，使用ElevatorInput，负责接收请求并存入队列

• 开一个线程，用于模拟电梯的活动，负责从队列中取出请求并进行执行，执行完后继续取继续执行

• 构建一个队列，用于管理请求，且需要保证队列是线程安全的

　　Main类中的main方法负责创建电梯线程，同时作为输入线程，管理输入，接受请求并存入队列，线程结束标志是读到null。

　　ElevatorThread类是电梯线程，按照FIFO策略的傻瓜电梯，每次搭载一名乘客，完成任务后再搭载另一名乘客，线程结束标志是读到null同时队列为空。

　　Request类包含三个属性id、from和to，在输入接口的三个get方法（getFromFloor()、getToFloor()、getPersonId()）的帮助下新建对象。同时利用IDEA自动生成三个属性的get方法（这步在完成之后才发现其实有点多余，可以直接使用输入接口里的PersonRequest）。

　　RequestQueue类作为请求队列，用于管理请求，以ArrayList为基础，保证线程安全，并配上所需的方法。

 

2、项目分析：

UML类图：

度量分析：

 

 

 

3、自我总结：

　　Main类main方法的ev(G)、iv(G)和v(G)都很高，原因在于main方法中包含了输入处理，这一部分我基本是按照指导书输入接口的Demo设计的，暂时还没有想到很好的解决办法。

 1 ElevatorInput elevatorInput = new ElevatorInput(System.in);
 2 　　while (true) {
 3    　　PersonRequest personRequest = elevatorInput.nextPersonRequest();
 4        　　if (personRequest == null) {
 5            　　elevatorThread.setEnd(true);
 6           　　 break;
 7　　　　　　　} else {
 8               Request request = new Request(personRequest.getPersonId(),
 9            　　personRequest.getFromFloor(),
10            　　personRequest.getToFloor());
11            　　queue.addRequest(request);
12            }
13    　　}
14 　　 elevatorInput.close();

　　ElevatorThread类run方法的iv(G)和v(G)很高，也是由于一个长期为真的while循环所导致的。

 1     public void run() {
 2         while (!isEnd()) {
 3             if (!queue.isEmpty()) {
 4                 try {
 5                     elevator.work(queue.getRequest());
 6                     queue.removeRequest();
 7                 } catch (InterruptedException e) {
 8                     e.printStackTrace();
 9                 }
10             }
11         }
12     }

 

4、程序bug分析：

　　这次作业比较简单，我中测只提交了两次就通过了，强测和互测也是全部安全通过。

　　第一次提交中测，我出现的问题在于，在读到null时就结束了所有线程，并没有考虑到请求队列中是否还有未完成的请求。

　　于是我将主线程结束标志设为读到null，ElevatorThread结束标志设为主线程读到null且请求队列为空。

　　ElevatorThread原结束标志：

1 private synchronized boolean isEnd() {
2 　　return end;
3}

　　　　ElevatorThread现结束标志：

1private synchronized boolean isEnd() {
2 　　return end & queue.isEmpty();
3}

 

5、性能分析：

　　这次作业我采用的调度策略是完全按照FAFS调度策略走的，按照请求进入系统的顺序，依次按顺序逐个执行运送任务，不过这次作业不存在性能分，虽然效率很低，但更多是让我们熟悉熟悉多线程，为后面的作业做准备。

 

6、互测分析：

　　第一次作业的互测其实是非常困扰我的，很大的原因在于输入的顶点投放和正确性比对。最后我所采用的策略是非常傻瓜的自编数据，同时将输入时间戳全部设置为[0.0]，在本地投放后复制粘贴。

　　由于这次作业并不复杂，大家的程序设计的也都很周期，本次互测并没有测出bug。

 

第六次作业：

1、架构构思：

　　这次的总体架构我仍然是按照指导书去写的，不过还是有一些变动：

• 主线程进行输入的管理，使用ElevatorInput，负责接收请求并存入队列

• 构建一个调度器（本次的调度器可以和队列是一体的）

• 用于管理请求

• 和电梯进行交互并指派任务给电梯

• 且需要保证调度器是线程安全的

• 构建一个电梯线程，负责和调度器进行交互（比如每到一层进行一个交互）接收任务，并按照一定的局部策略进行执行。

• 设计的重点依然在于最大限度降低耦合，每个对象只应该管自己该管的事。

　　Main类、ElevatorThread类和Request类几乎保持不变，变化的主要是Elevator类和RequestQueue类。

　　RequestQueue类作为请求队列与调度器的统一体，包含了排序、选择捎带对象、分配任务等功能。我在上完理论课后，将原来的数据结构 ArrayList<> 换为了 Vector<>。Vector<> 相比与 ArrayList 的优势是它是线程安全的，对于同一个vector对象多个线程调用get、remove、size等方法时，它们是串行执行的。

　　我看了源码后发现，确实很多方法都有同步关键字synchronized，从而保证所有的对外接口都会以 Vector对象为锁，即，在vector内部，所有的方法都不会被多线程访问。

　　但是，单个方法的原子性（注：原子性，程序的原子性即不会被线程调度机制打断），并不能保证复合操作也具有原子性。

　　所以，虽然源代码注释里面说这个是线程安全的，因为确实很多方法都加上了同步关键字synchronized，但是对于符合操作而言，只是同步方法并没有解决线程安全的问题，还需要人为的去增加锁。

　　然而，如果是这样的话，那么用 Vector 和 ArrayList 就没有区别了，而且 Vector 的执行效率要低于 ArrayList，这一条是我在第七次作业中才发现的，在这种情况下，用 Vector 还不如用 ArrayList。

 

2、项目分析：

UML类图：

度量分析：

 

 

 

3、自我总结：

　　这次作业的重灾区在于RequestQueue类和Elevator类。

　　RequestQueue类主要在于调度器与队列一体，我的排序方法addAndSort()和寻找捎带方法getPiggy()有很多的for循环，导致复杂度升高。

　　而对于Elevator类，我非常后悔的是我的每次进入、输出和开门关门都是手动进行，没有把它们包装为方法，导致错误几率和复杂度增加，在第七次作业中我就第一时间将它们作出了改变。

 1 public class Elevator {
 2 
 3     private void arriveFloor(int floor) throws InterruptedException {
 4         Thread.sleep(runTime);
 5         TimableOutput.println("ARRIVE-" + floor + "-" + name);
 6     }
 7 
 8     private void openDoor(int floor) throws InterruptedException {
 9         TimableOutput.println("OPEN-" + floor + "-" + name);
10         Thread.sleep(doorTime);
11     }
12 
13     private void closeDoor(int floor) throws InterruptedException {
14         Thread.sleep(doorTime);
15         TimableOutput.println("CLOSE-" + floor + "-" + name);
16     }
17 }

 

 1 public class Request {
 2 
 3     public void inElevator(char name) {
 4         TimableOutput.println("IN-" + id + "-" + from + "-" + name);
 5     }
 6 
 7     public void outElevator(char name) {
 8         TimableOutput.println("OUT-" + id + "-" + to + "-" + name);
 9     }
10 }

　　另一方面，由于在电梯运行过程中，不断的取最高（最低）楼层，利用for循环遍历捎带队列，导致循环复杂度很高，使得我的v(G)高居不下。Elevator类的WMC也达到了吓人的44。

 

4、程序bug分析：

　　这次作业，我中测一直卡在最后一个点，提交了很多次才通过，而强测和互测全部安全通过。

　　前两次的中测提交修复了除最后一个点外的所有样例发现的bug，都是一些小细节错误，然而最后一个点始终测不出来，我翻阅了讨论区和水群，最后发现了跟我有相似经历的同学，他们给我提供了一些非常有价值的样例，比如

1-FROM-7-TO-10
2-FROM-7-TO-14
3-FROM-10-TO-5
1-FROM-1-TO-5
2-FROM-2-TO-6
3-FROM-3-TO-7
4-FROM-4-TO-8
5-FROM-5-TO-9

　　除此之外，因为这一单元的输入输出接口只有微小的不同，我发现我们可以选择用上一次作业的bug修复来寻找这一次作业的bug。

　　在这二者的帮助下，我最终发现我通不过最后一个点的原因在于，电梯在完成全部捎带任务后，自己所在楼层的更新有误。

 

5、性能分析：

　　本次强测性能分占强测总分的20%，我在强测中出现了两次80分，其他的性能分也并不高。

　　这次我的调动策略仍然非常保守，我的选择是将捎带队列按目标楼层的高低排序，在到达每一层加入捎带请求时，只考虑目标运动方向与现有运动方向是否一致，同时更新整体最终目标楼层。

 1 int updateTo = to;
 2 
 3 ……
 4 
 5 if (pigQueue.getLast().getTo() > updateTo) {
 6     updateTo = pigQueue.getLast().getTo();
 7 }
 8 
 9 ……
10 
11 if (pigQueue.getFirst().getTo() < updateTo) {
12     updateTo = pigQueue.getFirst().getTo();
13 }

 

6、互测分析：

　　第二次作业的互测，我首先是汲取了我在中测debug时的经验，将我的代码交到第一次作业的bug修复上，获取上次强测的数据，进行提交。

　　同时，在讨论区大佬和github的帮助下，在本地构建简易评测机，辅助测试。

　　这次作业大家把细节也都考虑到了，本次互测也并没有测出bug。

 

第七次作业：

1、架构构思：

　　终于来到了本单元最后一次作业，这次每个电梯的架构我是直接照搬的第六次作业，然而偷懒一时爽，强测火葬场，上一次作业的不规范让我在之后付出了很大的代价。

　　指导书的建议：

• 主线程进行输入的管理，使用ElevatorInput，负责接收请求并存入队列

• 构建一个调度器（本次的调度器可以和队列是一体的）

• 用于管理请求

• 和电梯进行交互并指派任务给电梯，并可能需要处理请求的先后顺序依赖关系

• 且需要保证调度器是线程安全的

• 对于性能优化党，调度器还需要对调度的优劣性有一定的判断，并以任务分配的方式给出较优的统筹规划结果

• 如果感觉一层调度分配器有点不够用或者已经越发臃肿的话，可以考虑构建多层分配器，将请求分配逻辑进一步拆分+细化，甚至使用多个线程构建为类似流水线的分配模式。

• 构建三个电梯线程

• 三部电梯统一建模。

• 各自进行一定的配置（容量，速度，楼层），并维护状态。

• 各自负责和同一个调度器进行交互（比如每到一层进行一个交互）接收任务。

• 各自基于接收到的任务按照一定的局部策略进行执行。

• 设计的重点依然在于最大限度降低耦合，每个对象只应该管自己该管的事。

　　我的做法是，将输入线程从主线程中拿了出来，主线程在创建完各个对象和各个线程后就自动结束。剩下由 InputThread 和 SchedulerThread 交互，接收请求并存入队列，SchedulerThread 和三个 ElevatorThread 交互，指派任务给电梯，完成换成工作，从而达到数据共享。

 

2、项目分析：

UML类图：

度量分析：

 

 

 

3、自我总结：

　　在汲取了第二次作业的教训后，我第三次作业中将之前写到的开关门、到达和进入离开都写成方法，增加程序的可读性，同时降低复杂度。

　　这次作业的重灾区在于Elevator类和SchedulerThread类。

　　Elevator类中的addPigQueue方法，是用来管理捎带队列的，所以需要不断遍历请求队列，寻找可以捎带的对象，导致复杂度很高。

　　SchedulerThread类中的run()方法则是因为我在不断遍历请求队列中的每一个元素，提取出来原楼层和目标楼层后再让它和三个电梯的可达楼层作循环比对，还要判断电梯是否超载，导致恐怖的方法复杂度。

 1 public void run() {
 2         while (!queue.isEmpty() && (queueA.size() < 5 || queueB.size() < 7 || queueC.size() < 6)) {
 3             r = queue.getFirst();
 4             from = r.getFrom();
 5             to = r.getTo();
 6             if (contains(floorA, from, to)) {
 7                 if (queueA.size() < 5) {
 8                     queueA.addAndSort(r);
 9                     queue.removeRequest();
10                 }
11             } else if (contains(floorB, from, to)) {
12                 if (queueB.size() < 7) {
13                     queueB.addAndSort(r);
14                     queue.removeRequest();
15                 }
16             } else if (contains(floorC, from, to)) {
17                 if (queueC.size() < 6) {
18                     queueC.addAndSort(r);
19                     queue.removeRequest();
20                 }
21             } else if (contains(floorA, from)) {
22                 if (queueA.size() < 5) {
23                     setTemp(r);
24                     queueA.addAndSort(r);
25                     queue.removeRequest();
26                 }
27             } else if (contains(floorB, from)) {
28                 if (queueB.size() < 7) {
29                     setTemp(r);
30                     queueB.addAndSort(r);
31                     queue.removeRequest();
32                 }
33             } else if (contains(floorC, from)) {
34                 if (queueC.size() < 6) {
35                     setTemp(r);
36                     queueC.addAndSort(r);
37                     queue.removeRequest();
38                 }
39             } else {
40                 queue.addRequest(r);
41                 queue.removeRequest();
42             }
43         }
44     }

 

4、程序bug分析：

　　如果说前两次作业都比较顺利的话，这次作业就是惊险刺激+大型翻车现场。

　　这次作业，我的正确性没有问题，问题集中在CPU时间上。我的中测一直在出现 CPU_TIME_LIMIT_EXCEED ，花费了非常多的时间去修复，同时强测和互测也出现了很多的 CPU_TIME_LIMIT_EXCEED，可以说我这次作业中线程之间的通讯与轮转存在着很大的问题。

　　我在强测公布后寻找了几位大佬学习架构，这次的超时问题主要还是架构的锅，所以我也是从上周就开始重构代码，想完完全全将整个电梯写好。

 

5、性能分析：

　　本次强测性能分占强测总分的15%。

　　我的单个电梯的调度策略仍与上次一致。而整体分发保证均衡性，避免出现任一电梯过载而其他电梯空闲的状态。对于换乘，我分析得知，从一楼层去往另一楼层，最多只需要1次换乘，所以完成所有的电梯至多需要进入两次请求队列。

　　我在Request类中定义了两个to属性：

1 private int to;
2 private int tempTo;
3 
4 public void setTempTo(int temp) {
5     this.tempTo = to;
6     this.to = temp;
7 }

　　在完成换乘时更新to：

1 public void setFromAndTo() {
2     this.from = to;
3     this.to = tempTo;
4 }

　　　　如果发现to和tempTo相同，证明是直达，直接移除电梯，否则再次加入请求队列：

1 private synchronized int leaveAndTransfer(int i, Request r) {
2     r.outElevator(name);
3     if (r.isTransfer()) {
4          r.setFromAndTo();
5          baseQueue.addRequest(r);
6     }
7     pigQueue.removeRequest(r);
8     return i - 1;
9 }

 

6、互测分析：

　　前两次互测的春风拂面消失不见，取而代之的是一场腥风血雨。

　　我的互测策略仍然是 上次作业的强测数据 + 简易评测机，可以说第二次作业的强测数据的命中率还是很高的，收获不小，但是比起被刀来说还是入不敷出，最后还是努力告诉自己不要当狼人，别拼命提交样例。

 

 

四、心得体会

1、线程安全：

　　在多线程编程的学习中，我入门的方法是图书馆借来的《Java多线程编程核心技术》，里面详细的讲授了线程交互的策略与线程安全的设计。

　　在设计架构时，我们需要分析出共享对象和在其上的共享线程们，这是我们进行线程安全设计的基础。

　　在编码过程中，我们要保障共享对象中的方法的安全性和共享线程之间的协同问题。

　　在保证所有在线程安全的同时，保障类自身功能的高内聚低耦合，这二者直接需要很多的权衡，我在本单元的作业中这一点做的并不好，度量分析出现了大量的飘红。 　　在线程轮询上，避免暴力轮询，多用wait和notify来实现逻辑上的同步。 　　锁是很重要很有力的工具，但一定一定不能滥用锁，同时要避免死锁。

 

2、设计模式：

　　设计模式方面，我所依靠的一方面是老师上课的教授，另一方面则是《图解Java大学城设计模式》。

　　为什么我们需要学习设计模式呢？

　　这就跟我们看别人的代码来学习一样，是为了学习里面的精髓。每一本设计模式的书都会告诉你，这些都是在讲究如何对修改封闭，对扩展开放的事情。

　　我们学东西，重要的是学idea，次要的是学technique。

　　翻译成编程的语言就是，我们学设计模式，是为了学习如何合理的组织我们的代码，如何解耦，如何真正的达到对修改封闭对扩展开放的效果，而不是去背诵那些类的继承模式，然后自己记不住，回过头来就骂设计模式把你的代码搞复杂了，要反设计模式。

　　设计模式归根结底就是因为使用的程序语言的抽象能力不足才发明出来的。

　　这个单元的学习过程中，第七次作业给了我很大的教训，让我明白运用好设计模式去设计架构的重要性，不然就会出现大量的崩盘。

　　在设计实现的时候，要尽可能的留出空间，按照Open Close Principle （开闭原则）和Liskov Substitution Principle（里氏替换原则），充分体现程序的可扩展性设计，在程序中能用父类就用父类，能用接口就用接口，能预留扩展空间就预留扩展空间。这样也能让我们在单元式的学习中不需要一次次的重构代码。

　　遵循良好的设计原则，有利于我们平常在开发中写出更可维护的代码，便于团队协作也有利于后来者。