| 项目 | 内容 |
|---|---|
| 这个作业属于哪个课程 | 2020春季计算机学院软件工程(罗杰 任建) |
| 这个作业的要求在哪里 | 个人项目作业 |
| 我在这个课程的目标是 | 完成一次完整的软件开发经历 并以博客的方式记录开发过程的心得 掌握团队协作的技巧 做出一个优秀的、持久的、具有实际意义的产品 |
| 这个作业在哪个具体方面帮助我实现目标 | 体验《构建之法》中提到的 效能分析及个人软件开发流程对于项目开发带来的帮助 |
| 教学班级 | 006 |
| 项目地址 | Intersections | q2l's GitHub |
Personal Software Process Table (PSP)
在开始实现程序之前，在下述 PSP 表格记录下你估计将在程序的各个模块的开发上耗费的时间。（0.5'）
| PSP2.1 | Personal Software Process Stages | 预估耗时（分钟） | 实际耗时（分钟） |
|---|---|---|---|
| Planning | 计划 | 10 | 10 |
| · Estimate | · 估计这个任务需要多少时间 | 10 | 10 |
| Development | 开发 | 115 | 180 |
| · Analysis | · 需求分析 (包括学习新技术) | 20 | 15 |
| · Design Spec | · 生成设计文档 | 10 | 10 |
| · Design Review | · 设计复审 (和同事审核设计文档) | 0 | 0 |
| · Coding Standard | · 代码规范 (为目前的开发制定合适的规范) | 5 | 5 |
| · Design | · 具体设计 | 10 | 20 |
| · Coding | · 具体编码 | 30 | 60 |
| · Code Review | · 代码复审 | 10 | 10 |
| · Test | · 测试（自我测试，修改代码，提交修改） | 30 | 60 |
| Reporting | 报告 | 80 | 80 |
| · Test Report | · 测试报告 | 30 | 30 |
| · Size Measurement | · 计算工作量 | 20 | 20 |
| · Postmortem & Process Improvement Plan | · 事后总结, 并提出过程改进计划 | 30 | 30 |
| 合计 | 235 | 270 |
解题思路
解题思路描述。即刚开始拿到题目后，如何思考，如何找资料的过程。（3'）
首先拿到题干，是一道 几何题目 ，具体分析如下：
对于直线交点的求解我们有很多种方法，从直接的暴力运算到矩阵表示等等，考虑到代码的风格和可扩展性我们不采取直接暴力求每个交点然后存储的方式，我们选用了克莱姆法则求解线性方程组的方法，将直线表示为参数方程处理。
所以我们加以定义结构体存储(x, y)，由于单位向量和点的表示方式是一样的，所以不必额外定义。
我们可以自定义一个库来存储这些结构体的定义和关于结构体的运算符的重载。
此外，本次作业虽然 输入都是整数点，但是线段的斜率(即单位向量)并不是整数，还要考虑到浮点的精度问题，这里我们可以采用 重新定义为0的情况 来抵消一部分精度带来的损失。
由于这段时间任务较重，所以侧重于基础题的拿分，对于附加题选择放弃的做法。
设计实现
设计实现过程。设计包括代码如何组织，比如会有几个类，几个函数，他们之间关系如何，关键函数是否需要画出流程图？单元测试是怎么设计的？（4'）
由于本次作业较为简单，所以只定义了一个项目的类 Intersection，而对于 Point 和 Vector 所构成的直线方程并没有设计类，而是直接使用 struct 的结构体完成一系列的操作。
因为自己只实现了基础部分，所以用到的只有基本的线性代数的知识，目前阶段暂时不需要流程图的形式呈现出来。
单元测试的主要目的是 覆盖边角的情况，这种边角的情况包括三种：
- 平行直线
- 对于平行直线而言是否能够检测到并不发生 除零 操作。
- 得到的交点平行于x轴和y轴的时候能否得到正确结果。
- 垂直直线
- 垂直直线只是相交线的一种特殊情况，主要在后面的直线和圆的计算中会使用到，这里只是预留下来。
- 数据边界
- 一个是数据范围的边界是否能保证精度，这里采用了
eps=1e-12的精度来进行精度丢失的处理。 - 数据量压力测试，在给定的直线的数据分别是 1000 和 50000 的时候能否在规定的时间内完成运算并得到正确结果。
- 一个是数据范围的边界是否能保证精度，这里采用了
对于每一种情况我们都设计了若干个单元测试的样例进行测试，具体可见目录中的 UnitTest 中的 resources。
改进思路
对于我的实现，改进的路线是这样的：
- 一开始使用了
Set结构体，因为交点的个数的计算是无重复的。 - 分析了
Set数据结构的性能，其内部是 红黑树 实现，红黑树能时刻保证是一个有序的状态，但是要时刻维护，每次寻找是否已经存在交点的时候所花费的时间和层高相关，大致都是log(cnt_n)其中cnt_n是已经存入的交点个数。 - 尝试使用
Hashset，HashSet的内部实现是桶和哈希表的实现，每个元素被先存到一个桶内，桶内的元素通过一张哈希表进行连接。 - 尝试
List加Sort加Unique的新特性，在最后进行重复数据的筛除。
性能分析图
Code Quality Analysis
已消除所有警告，之前的警告是由于部分变量定义未使用和文件的忽略了某些函数的返回值所导致的。
代码说明
void Intersection::solveLineLineIntersection() {
int i, j, n, ssize;
Vector u, v, w;
n = (int) vectors.size();
ssize = (int) intersects.size();
for (i = 0; i < n; i++) {
for (j = i + 1; j < n; j++) {
u = points[i] - points[j];
v = vectors[i];
w = vectors[j];
double denominator = Cross(v, w);
if (dcmp(denominator) == 0) { // parallel case
continue;
}
double t = 1.0 * Cross(w, u) / denominator;
intersects.push_back(points[i] + v * t);
}
}
}
即利用了 克雷姆法则 实现直线交点的求解。
总结
本次对于Personal Software Process 的体验有一点感触，因为真实发现了自己的缺陷——编码很快但是其中的错误也存在。之所以测试部分花了这么久的时间是因为在撰写 "myIntersection.h" 的时候出现了笔误，对于 int dcmp(double x) 的函数使用弄反了，在重载 == 符号的时候语义变为了 当两个点的x值相等且y值不等 的时候两个点相等，导致在使用 unique 函数求解的时候出现了平行于x轴的线上有两个交点的时候会只保留一个点，出现了正确性的错误。
之前没有做过PSP的类似的时间规划，但这次使用了之后发现每次记录自己在哪里投入了 额外多的时间 是非常重要的，因为这些额外的时间肯定是 自己的估计发生了偏差，并且 在实践的过程中 暴露了自己不知道的缺点。我的缺点就是会出现一些细节上的错误，导致自己花费大量的额外时间在测试的寻找漏洞上面。
这段时间挤压了太多的课内和课外的学习任务导致这次没能完成附加题的部分，实属可惜，不过学习不是一门课的成绩决定的，适当做出选择，这种选择也包括 放弃。只要能做到问心无愧，不是因为娱乐耽误了学习上的正事就可以了，下次继续努力吧。
2020年3月10日。