②操作系统进程调度管理，进程被调度在 CPU 上执行，操作系统决定在各个时段内执行哪个进程。操作系统可挂起某个正在执行的进程，在后续时刻可以恢复执行被挂起的进程。每个时间只能有一个进程在执行，其他进程处于休眠状态；一个进程的执行被分为多个时间段；在特定时刻，CPU 可以“闲置”；调度无规律，可看作是随机调度。

③大学课表管理：课程需要特定的教室和特定的教师。假设各周的课表都是完全一样的，同样的课程安排将以“周”为单位进行周期性的重复，直到学期结束；一门课程每周可以出现 1 次，也可以安排多次，且由同一位教师承担并在同样的教室进行；允许课表中有空白时间段；同一个时间段内可以安排不同的课程；一位教师也可以承担课表中的多门课程。

相同之处：都包含了具有不同特征的“时间段集合”对象。每个时间段对应一个对象标签。

不同之处：有三个维度上的差异。①是否允许时间轴上有空白。在应用1中，不允许有空白；在应用2和应用3中，允许有空白。②是否允许不同的 interval 之间有重叠。在应用1和应用2中，不允许有重叠；在应用3中，允许有重叠。③是否包含周期性的时间段。应用 3 中以“一周”为单位重复某个课程，但应用1和应用2中不存在这种情况。

1. 面向可复用性和可维护性的设计：IntervalSet<L>

该节是本实验的核心部分。

1. 1. IntervalSet<L>的共性操作

描述了一组在时间轴上分布的“时间段”，每个时间段附着一个特定的标签，且标签不重复。因此共性的方法包括：

静态工厂方法empty()：创建一个空对象。

void insert(long start, long end, L label)：在当前对象中插入新的时间段和标签。

Set<L> labels()：获得当前对象中的标签集合。

boolean remove(L label)：从当前对象中移除某个标签所关联的时间段。

long start (L label)：返回某个标签对应的时间段的开始时间。

long end (L label)：返回某个标签对应的时间段的结束时间。

IntervalSet<L> copy()：返回这个对象的副本。

1. 1. 局部共性特征的设计方案

前两个应用选择CommonIntervalSet 这一实现，最后一个应用选择MultiIntervalSet 这一实现

1. 1. 面向各应用的IntervalSet子类型设计（个性化特征的设计方案）

CommonIntervalSet函数，其中 insert() , labels() , remove() , start() , end()五个函数都是对 IntervalSet 中函数的重载，参数与返回值同上文。其他函数：

toString() 将标签集合中的所有标签的信息转换为字符串输出，返回一个很长的字符串

checkRep() 检查数据逻辑上是否有错误，返回 true 或 false

CommonIntervalSet 中定义了一个装载 Label 类成员的集合 Labels，变量为私有类型。自定义类名为 Labels，成员变量一共有三个：start、end、name，其余方法都是根据三个变量实现功能的

1. 面向可复用性和可维护性的设计：MultiIntervalSet<L>
  1. MultiIntervalSet<L>的共性操作

静态工厂方法empty()：创建一个空对象。

MultiIntervalSet(IntervalSet<L> initial)：利用initial中包含的数据创建非空对象。

void insert(long start, long end, L label)：在当前对象中插入新的时间段和标签。

Set<L> labels()：获得当前对象中的标签集合。

boolean remove(L label)：从当前对象中移除某个标签所关联的所有时间段。

IntervalSet<Integer> intervals(L label)：从当前对象中获取与某个标签所关联的所有时间段。

1. 1. 局部共性特征的设计方案

由于要求必须使用 IntervalSet<L>作为其 rep 的一部分，因此选择IntervalSet<L>组成的List作为rep。一个IntervalSet中只存储某个标签对应的一个时间段，如果一个标签对应多个时间段，需要分散在不同的IntervalSet中。

对于empty()方法，直接返回一个具体实现类。

对于initial初始化方法，直接将传入的IntervalSet的副本作为rep的一个元素。

对于insert()方法，首先判断非法情况。之后遍历IntervalSet列表得到标签对应的所有时间段，判断已存在的时间段和要增加的时间段是否存在重叠，如果重叠则抛出异常；若不重叠，就寻找某个不存在该标签的IntervalSet，将这个时间段插入该IntervalSet，如果列表中所有的IntervalSet都包含该标签，就需要新建一个空白的IntervaSet加入列表，再进行插入。

对于labels()方法，可以直接返回第一个IntervalSet中的所有标签组成的集合。（因为插入时都是从头开始遍历的，因此不会存在某个标签出现在后面的IntervalSet而不在第一个IntervalSet中的情况）

对于remove()方法，直接对每个IntervalSet调用remove()方法即可。

对于intervals()方法，遍历IntervalSet列表得到标签对应的所有时间段，将时间段从小到大进行排序（前面time的实现中进行了说明）。然后将每个时间段以它的顺序作为标签插入到一个IntervalSet中并返回。

此外，还需要重写toString方法提供容易阅读的信息。

1. 1. 面向各应用的MultiIntervalSet子类型设计（个性化特征的设计方案）

使用decorator装饰器的方法进行是否允许不同的interval之间有重叠以及周期性的维度的个性特征的设计。向装饰器中传入待装饰的MultiIntervalSet，并在继承该装饰器的具体子类中实现相应的个性化功能

1. 面向复用的设计：L

设计三个应用的不同标签，分别为“员工”（Employee）、“进程”（Process）、

“课程”（Course）。并且它们都是immutable类。

①对于Employee，具有的属性为：姓名、职务、手机号码。

除了相应的get方法之外，还需要重写equals()、hashCode()和toString()方法。equals()的判断依据是：只有三个属性均相同时才认为是相同的。

②对于Course，具有的属性为：课程 ID、课程名称、教师名字、地点。

除了相应的get方法之外，还需要重写equals()、hashCode()和toString()方法。equals()的判断依据是：只有四个属性均相同时才认为是相同的。

此外，Course类实现了Comparable接口，这是为了APP中显示课程顺序的合理性。

③对于Process，具有的属性为：进程 ID、进程名称、最短执行时间、最长执行时间。

除了相应的get方法之外，还需要重写equals()、hashCode()和toString()方法。equals()的判断依据是：进程ID相同时认为是相同的。

1. 可复用API设计
  1. 计算相似度

遍历s1中的标签，查看s2中是否存在相同的标签，如果不存在，则对相似度没有贡献；如果存在，那么这个标签在s1和s2中各有一个时间段的集合，计算这两个时间段集合的重合长度，将所有的重合长度加在一起除以MultiIntervalSet的时间跨度就是两个MultiIntervalSet的相似度。

1. 1. 计算时间冲突比例

对于IntervalSet来说，由于它是一个特殊的MultiIntervalSet，因此可以把它转换成MultiIntervalSet后再调用针对MultiIntervalSet的计算时间冲突比例的函数。

对于MultiIntervalSet，维护一个冲突时间段的集合conflictTime，初始时为空。遍历set中的标签，判断该标签和其他标签的时间段是否存在重合，如果存在，就将冲突的时间段加入conflictTime。向conflictTime加入时间段也需要考虑重合的问题，集合中不能有重合的时间段，因此向conflictTime加入时间段时需要进行适当的合并。最后conflictTime中的时间长度除以总的时间跨度就是时间冲突比例。

1. 1. 计算空闲时间比例

对于IntervalSet来说，由于它是一个特殊的MultiIntervalSet，因此可以把它转换成MultiIntervalSet后再调用针对MultiIntervalSet的计算空闲时间比例的函数。

对于MultiIntervalSet，原理类似于3.2.3中的blankIntervals()方法。维护一个空闲时间段的集合freeTime，初始时为整个时间段。遍历set中的所有时间段，并将其从freeTime中删去。最后freeTime中的时间长度除以总的时间跨度就是空闲比例。

1. 应用设计与开发

利用上述设计和实现的ADT，实现手册里要求的各项功能。

1. 1. 排班管理系统

使用DutyIntervalSet作为数据结构，同时维护一个Employee的集合可以存储未被安排的员工。刚进入时APP，会提示初始化一些信息，包括：排班开始日期、结束日期以及一组员工信息。初始化结束后，打印一个菜单，告诉用户提供的一些功能。

根据用户选择的功能采取相应的操作。选项1,2涉及对Employee集合的增删；3对应DutyIntervalSet的insert操作；4对应DutyIntervalSet的remove操作；5对应DutyIntervalSet的blankIntervals操作；7对应DutyIntervalSet的blankIntervals操作以及DutyIntervalSet的labels、start、end操作。其中自动编排”的实现方法：首先调用DutyIntervalSet的blankIntervals操作得到未被安排的时间段，然后遍历Employee集合，找出未被安排的员工，将这些未被安排的时间段和员工一对一匹配起来，并调用insert方法插入到DutyIntervalSet中。

1. 1. 操作系统的进程调度管理系统

使用ProcessIntervalSet作为数据结构，同时维护一个的Map存储进程和已执行时间的映射关系。进入APP后，会打印一个菜单，告诉用户提供的一些功能。

根据用户选择的功能采取相应的操作。其中选项1,2涉及对Map的增删；5，6对应ProcessIntervalSet的intervals操作。由于这些操作都是简单地使用一些函数，因此不再详细叙述。这里介绍3,4的实现方法，选项3：从时间点0开始进入一个循环，当所有的进程都被执行完成后退出循环。在循环中，首先使用随机数（random.nextBoolean）决定是否调度进程，如果决定不调度进程，则闲置一段随机的时间（random.nextInt）；如果决定调度进程，则随机选择一个未完成的进程（使用随机数选择进程的序号）并执行一段随机的时间（random.nextInt），执行结束后，如果该进程的总执行时间已经落到最短执行时间和最长执行时间的区间内，则该进程被执行完成，然后从这个时间点开始进行下一轮的循环。选项4：和选项3唯一的不同在于进程的选择不是随机的，而是选择距离其最大执行时间差距最小的进程。

1. 1. 课表管理系统

使用CourseIntervalSet作为数据结构，同时维护一个Course的Map存储未被安排的课程以及对应的剩余学时数。刚进入时APP，会提示初始化一些信息，包括：学期开始日期、总周数、以及一组课程信息。初始化结束后，打印一个菜单，告诉用户提供的一些功能。

根据用户选择的功能采取相应的操作。其中选项1,2涉及对Course映射的增删；3对应CourseIntervalSet的insert操作；4对应CourseIntervalSet的remove操作；5对应对Course映射的遍历以及显示；6,7对应API中操作的使用；8对应CourseIntervalSet的intervals操作。

1. 基于语法的数据读入

修改“排班管理”应用以扩展该功能。

1. 应对面临的新变化
  1. 变化1

评估之前的设计是否可应对变化、代价如何

如何修改设计以应对变化

1. 1. 变化2

评估之前的设计是否可应对变化、代价如何

如何修改设计以应对变化

1. Git仓库结构

请在完成全部实验要求之后，利用Git log指令或Git图形化客户端或GitHub上项目仓库的Insight页面，给出你的仓库到目前为止的Object Graph，尤其是区分清楚change分支和master分支所指向的位置。

实验进度记录

请使用表格方式记录你的进度情况，以超过半小时的连续编程时间为一行。

每次结束编程时，请向该表格中增加一行。不要事后胡乱填写。

不要嫌烦，该表格可帮助你汇总你在每个任务上付出的时间和精力，发现自己不擅长的任务，后续有意识的弥补。

日期	时间段	计划任务	实际完成情况
6.30-7.4		完成lab3	未完成

实验过程中遇到的困难与解决途径

遇到的难点	解决途径
时间不够

实验过程中收获的经验、教训、感想
1. 实验过程中收获的经验和教训

设计ADT时一定要考虑得全面且清楚，在最终决定实现方案后再编写代码，否则在后面的应用实现中发现问题时只能再重新设计。同时，在编写APP时，一定要事先考虑健壮性的问题，不然，在编写完代码之后进行测试时会遇到很多的健壮性问题，这时再去修改就会使得代码很臃肿，可读性变差，出错的可能性更高。

1. 针对以下方面的感受
重新思考Lab2中的问题：面向ADT的编程和直接面向应用场景编程，你体会到二者有何差异？本实验设计的ADT在五个不同的应用场景下使用，你是否体会到复用的好处？

面向ADT的编程需要从实际中进行抽象，并进行合理的设计，有很好的可扩展性和可复用性；而直接面向应用场景编程只针对特定应用，每次更换应用场景时都要重新编程，扩展性很差，只适合简单的应用场景。本实验中设计一个ADT就可以应用到三个不同的场景，大大缩短了开发时间。

重新思考Lab2中的问题：为ADT撰写复杂的specification, invariants, RI, AF，时刻注意ADT是否有rep exposure，这些工作的意义是什么？你是否愿意在以后的编程中坚持这么做？

这些工作使得客户端了解各方法的功能但无法得知内部具体实现，可以防止内部变量被客户端恶意修改，时刻检查表示不变量，保证安全性。虽然这些工作有些麻烦，但却是好的软件必须具备的，因此我愿意在以后编程中坚持这么做。同时，在复杂的软件开发过程中，好的注释可以节省大量阅读代码的时间，使得开发时间大大降低。

之前你将别人提供的API用于自己的程序开发中，本次实验你尝试着开发给别人使用的API，是否能够体会到其中的难处和乐趣？

有难处，没有乐趣

你之前在使用其他软件时，应该体会过输入各种命令向系统发出指令。本次实验你开发了一个解析器，使用语法和正则表达式去解析输入文件并据此构造对象。你对语法驱动编程有何感受？

语法驱动编程为实际应用提供了很大的便利，用户无需繁琐地一行一行地输入信息，而只需提供一个文件以及一定的语法规则即可。而对于应用的开发者，只需根据语法规则编写代码，即使改变语法规则也可以很快地修改实现代码，有很好的可维护性。

Lab1和Lab2的大部分工作都不是从0开始，而是基于他人给出的设计方案和初始代码。本次实验是你完全从0开始进行ADT的设计并用OOP实现，经过五周之后，你感觉“设计ADT”的难度主要体现在哪些地方？你是如何克服的？

ADT的难度主要体现在抽象上。一个好的ADT既不能过于具体，也不能过于抽象。需要从大量应用场景中寻找共性，抽象的程度也很难把握。对于这种情况，只能反复的推敲，比较不同设计方案的差异并选择最好的ADT设计方案。

“抽象”是计算机科学的核心概念之一，也是ADT和OOP的精髓所在。本实验的五个应用既不能完全抽象为同一个ADT，也不是完全个性化，如何利用“接口、抽象类、类”三层体系以及接口的组合、类的继承、设计模式等技术完成最大程度的抽象和复用，你有什么经验教训？

接口、抽象类、类的抽象程度一定是逐渐降低的，将所有应用的共性抽象为接口，然后在抽象类以及类中添加新的特性。通过接口的组合可以形成新的接口，并可以具备不同接口中的抽象。类的继承也可以增加更具体的新的特性。同时，使用正确的设计模式可以使得代码的可复用性和可维护性最大化。

关于本实验的工作量、难度、deadline。

工作量大，难度大，deadline紧

到目前为止你对《软件构造》课程的评价。

总体而言有一定价值，新接触了一门语言，知道做软件的过程中大概步骤和注意事项。但PPT用英文造成了较大困难。

码农公寓

相关文章