这篇博客是一次课程作业。
项目 | 内容 |
---|---|
班级:北航2020春软件工程 006班(罗杰、任健 周五) | 博客园班级博客 |
作业:设计程序求几何对象的交点集合,支持命令行和GUI | 结对项目作业 |
个人课程目标 | 系统学习软件工程,训练软件开发能力 |
这个作业在哪个具体方面帮助我实现目标 | 体验结对编程;学习Windows下动态链接库的编译与使用 |
项目地址 | GitHub: clone/https |
本作业涉及到的小组及其成员:
学号 | CnblogProfile | GitHubRepo |
---|---|---|
17231145 * (结对伙伴) | @FuturexGO | *Repository |
17373331 * (本文作者) | @MisTariano | |
17231162 † (另一小组) | @PX_L | †Repository |
17373321 † (另一小组) | @youzn99 |
个人部分PSP与反思
PSP2.1 | 预估耗时(分钟) | 实际耗时(分钟) |
---|---|---|
Planning | 30(tot) | 20(tot) |
· Estimate | 30 | 20 |
Development | 860(tot) | 1230 (tot) |
· Analysis | 90 | 200 |
· Design Spec | 30 | 30 |
· Design Review | 60 | 60 |
· Coding Standard | 20 | 40 |
· Design | 120 | 60 |
· Coding | 360 | 720 |
· Code Review | 60 | 60 |
· Test | 120 | 60 |
Reporting | 90(tot) | 40(tot) |
· Test Report | 30 | 0 |
· Size Measurement | 30 | 10 |
· Postmortem & Process Improvement Plan | 30 | 30 |
In Total | 980 | 1290 |
本次作业耗时超出预估,主要原因集中在对Windows下类库管理与编译流程的不熟悉上。在Linux上,一个.so
共享库可以非常简单地被编译使用,加之Linux下编译器版本借助apt管理,环境变量往往比较清晰,因此借助cmake等管理工具很少出现编译上的问题。但是windows下的编译更为复杂,比如MinGW GNU及MSVC两条编译工具链间的异同、动态链接头.dll.a
的使用、PATH内不同编译器间的冲突管理都是需要考虑的细节。在编译Qt GUI的时候我就由于系统内两套Qt类库(新安装的5.14与此前Anaconda自带的5.9)间的版本兼容问题迟迟不能运行打包好的可执行文件。
此外,由于我和同伴对松耦合的期望较高,在接口设计上我们花了比预估更久的时间来打磨一份足够好用的设计。总的来说,这次作业虽然时间超过了一开始的预估,但总归没有太多被浪费。
设计思想与方法
Information Hiding与Loose Coupling
好的设计总是高内聚而低耦合的。我们的设计思路正是遵循这样的原则展开:
- 只暴露恰到好处的细节,隐藏用户不需要也不应该关心的内部数据结构、算法流程、底层操作,避免程序被以错误的(我们不希望的或未预期的)方式调用,达到高内聚。虽然很残忍,但我们必须假想用户是鲁莽而疯狂的——他有可能多次初始化一个重要的内存池,或用电视遥控器把火箭发动机关闭。
- 将整个计算模块合理封装,对外暴露多个功能单一的无状态接口,实现接口与接口、接口与实现间的低耦合,当遇到新的接口格式/标准时可以方便地借助转接器等设计模式通过组合现有接口实现接口扩展/接口迁移。历史告诉我们,忠于开闭原则的人终将得到嘉赏。
这其实是一套老生常谈的东西,能把哭泣的小孩烦到闭嘴。然而一旦做到了这两点,我们就可以快速制定一套标准化的外层接口,并将程序接入——这个时候接口函数的声明与定义就可以完全分离了——我们就可以借助动态链接库提供代码定义,使程序可以被热更新。这就达成了作业要求的代码松耦合。
Code Contract
契约式设计我们已经在大二的OO课程中有关JML的章节里初步接触过了,简单的说这是一种先建立接口抽象约束(契约),再依照契约实现接口并检验功能的开发流程。它十分类似于一种防御式编程、测试驱动开发及内联文档的结合体,对于瀑布式开发模型这种需求先得到完备设计再完成编码的工作流,契约可以贯穿开发始终,确保所有需求都被恰到好处地执行。然而对于更快速的迭代模式(比如课程关注的敏捷开发),编写契约将耗费大量精力而降低开发效率,与追求快速迭代适应需求、极小化文档的宗旨矛盾。另一方面,契约语言(如JML)的编写往往由需求提出方给出,这要求相关人员有一定的开发与专业基础。加之工具链不成熟、相关工具开发难度较大等因素,如今并没有得到广泛应用。
对于JML工具链及契约编程的简单介绍,我在大二时曾写过一篇相关博客,感兴趣可以移步查阅。
接口的具体设计与实现*
我们一开始按照自己的接口设计(私有接口,或customInterface
)对核心模块进行了封装。
之后为了验证松耦合,我们与另一组的同学@PX_L共同设计了在各自接口标准之上的新标准(公有接口,StdInterface
)。
这样我们都以新标准接口导出DLL可以方便地验证GUI、命令行、测试模块与核心模块的松耦合,之前各自已经完成的对customInterface
的单元测试也无需重构,只需在customInterface
基础上加壳即可。
我们设计的customInterface
和StdInterface
的主要特点为:
- 考虑到我们希望接口能具有较强的兼容性,我们使用C风格接口,不使用C++的面向对象、STL等特性。这样今后稍微改动就可以被C、C++、Python等各种语言调用。
- 动态内存管理由接口内部实现,外部调用者无需直接操作指针。
- 数据被良好封装,外部调用者无法更改和直接访问数据,也无法知道数据的地址。
- 支持多例,即支持一个GUI程序中开多画布,每个画布数据独立。
用图可以阐释如下(为了理解方便,可能与代码有出入,如变量名等):
C风格 私有接口 customInterface:弱耦合
我们首先定制的接口,将计算类的基本操作进行了简单封装。代码请见src/interface.h
:
#ifndef GEOMETRY_INTERFACE_H
#define GEOMETRY_INTERFACE_H
#include <unordered_set>
#include "Shapes.h"
#include "StdInterface.h"
// 数据管理实例类
struct gManager {
std::vector<Geometry> *shapes;
std::unordered_set<Point, hashCode_Point, equals_Point> *points;
gPoint upperleft;
gPoint lowerright;
};
// 初始一个数据管理实例
gManager *createManager();
// 关闭实例,释放其占用的内存资源
void closeManager(gManager *inst);
// 清空实例中当前缓存的所有形状和交点
void cleanManager(gManager *inst);
// 向实例中添加形状
ERROR_INFO addShape(gManager *inst, char objType, int x1, int y1, int x2, int y2,
gPoint *buf, int *posBuf);
// 根据文件输入向实例中批量添加形状
ERROR_INFO addShapesBatch(gManager *inst, FILE *inputFile, gPoint *buf, int *posBuf);
// 获得当前交点总数
int getIntersectionsCount(gManager *inst);
// 获得当前实例中交点综述
int getGeometricShapesCount(gManager *inst);
// 获得当前所有交点,写入buf为首地址的连续内存中
void getIntersections(gManager *inst, gPoint *buf);
// 获得当前所有图形,写入buf为首地址的连续内存中
void getGeometricShapes(gManager *inst, gShape *buf);
#endif //GEOMETRY_INTERFACE_H
注意到这套接口提供了一个数据管理器gManager
,允许外部程序创建、持有计算中需要持久化的数据区并控制内存释放时机,这样所有的计算操作都不需要再维护全局缓存数据,这使所有接口都是无状态的,更易于解耦与使用。
这套封装已经已经足以覆盖对交点计算库的使用需求,但注意到两个问题:
- 由于追求泛用性使用C风格接口,以结构体的方式给出的
gManager
中类型为Geometry
的数据是可以被直接访问到的,而这个类型实际上是std::variant<Line, Circle>
(在src/Shapes.h中定义),用户的程序可以以我们不希望的方式添加对这个类型数据的操作,产生对这个类的耦合。一旦其他实现中没有提供这个类型,就不可能在不修改用户代码并重新编译的前提下将用户程序迁移至新的计算库实现。因此,这里并没有满足信息隐藏的原则,且难以实现松耦合。 - 由于接口中用到了
Shapes.h
定义的结构,Shapes.h
被引入了用户项目,对用户不透明。因此用户不仅可以调用interface.h
中声明的接口函数,还可以调用Shapes.h
中声明的各种计算操作——这也是不满足信息隐藏原则的。实际上这还会导致Point.h
的引用——用户程序在编译时必须同时包含这三个头文件,提供的动态库也必须完整实现这三个头文件中声明的函数,这使得程序借助松耦合取得的修改与扩展空间变得极小。
因此为了实现松耦合,我们在与另一组协商后设计了下述公有接口标准,对这些接口的引用关系与数据定义进行了集中整理。
C风格 公有接口 StdInterface:松耦合
我们的公有接口标准保留了C风格接口和无状态两个设计点,在单个头文件中给出了用户程序需要关注与使用的全部数据结构定义与函数声明。请见src/StdInterface.h:
// 错误代码枚举
enum ERROR_CODE {
SUCCESS,
WRONG_FORMAT,
VALUE_OUT_OF_RANGE,
INVALID_LINE, INVALID_CIRCLE,
LINE_OVERLAP, CIRCLE_OVERLAP,
};
// 运行状态与错误信息封装
struct ERROR_INFO {
ERROR_CODE code = SUCCESS;
int lineNoStartedWithZero = -1;
char messages[50] = "";
};
// 形状结构
struct gShape {
char type;
int x1, y1, x2, y2;
};
// 交点结构
struct gPoint {
double x;
double y;
};
// 画布结构,类似私有接口中的gManager,为用户程序提供数据管理
struct gFigure {
unsigned int figureId;
gShape *shapes; // only available after updateShapes()
gPoint *points; // only available after updatePoints()
gPoint upperleft;
gPoint lowerright;
};
// 创建画布
gFigure *addFigure();
// 释放画布资源
void deleteFigure(gFigure *fig);
// 清空画布中的形状与交点
void cleanFigure(gFigure *fig);
// 将形状添加至画布
ERROR_INFO addShapeToFigure(gFigure *fig, gShape obj);
// 将字符串desc中描述的形状添加至画布
ERROR_INFO addShapeToFigureString(gFigure *fig, const char *desc);
// 读取文件名为filename的文件并将其描述的图形批量导入画布
ERROR_INFO addShapesToFigureFile(gFigure *fig, const char *filename);
// 从标准输入流中读取形状并加入画布
ERROR_INFO addShapesToFigureStdin(gFigure *fig);
// 根据给定的形状索引移除形状
void removeShapeByIndex(gFigure *fig, unsigned int index);
// 获取交点总数
int getPointsCount(const gFigure *fig);
// 获取形状总数
int getShapesCount(const gFigure *fig);
// 将修改形状数据后新的交点数据同步到给定画布数据区points字段中
void updatePoints(gFigure *fig);
// 将修改形状数据后新的形状数据同步到给定画布数据区shapes字段中
void updateShapes(gFigure *fig);
不难发现这份接口涵盖的功能是上文中私有接口的超集。同时注意到在私有接口中存在的数据隐藏等问题,在这份接口定义中已经不存在了。
因此用户程序在编译时只需要包含这份头文件,就可以加载任何实现了这套接口的动态库并正常运行。
我们的松耦合实验便基于此接口完成。具体流程是:在完成标准制定后,参与的两组先协作完成这份头文件的编写,再分别将自己的私有接口组合以实现公有接口函数,最终分别编译动态库并进行互换实验。
核心模块内的设计——UML阐释
核心模块性能评估与改进*
性能评估与改进的工作主要由 @FuturexGO 完成,约用时3h。
由于我们继承了个人作业的思路,使用std::unordered_set<>
进行去重,因此一个值得关注的问题是:
花在计算交点上的时间多,还是花在去重交点上的时间多?
如何分别优化两部分?
计算交点部分的优化
于是,在最初的版本,我们基于一个随机生成的样例对程序进行Profile,结果如下:
可以看出在该版本下,计算部分占用了30.6%的总时长,维护HashSet部分占用了13.2%+5.9%等时间,最后delete一个大数据结构占用了20.4%的时长。
对于我们的设计,一个通常的函数调用路径可以看成(为了介绍简便进行了再加工):
1. std::vector<Point> intersection(Shape1 &x, Shape2 &y);
<--> (std::visit 解析std::variant 和 Template Shape1&Shape2)
2. std::vector<Point> intersection(Line &x, Line &y);
<--> (进一步的逻辑)
3. bool checkPointLine(Line &l, Point &p);
bool checkPointHalfline(Line &l, Point &p);
bool checkPointSegment(Line &l, Point &p);
bool checkHalflineOverlap(Line &x, Line &y);
...
展开函数调用树(此处未展示)我们发现,计算最密集的第三层(使用点积、叉积等计算几何方法检查点是否在给定范围上、检查是否重叠导致无穷多交点等)花费的时间并不占第一层的子树下的绝对多数(\(<70\%\))。
于是我们想到,既然两个图形的交点至多为2个,其实并没有必要使用std::vector<>
作为返回值。并且上述的一些被频繁调用的子逻辑函数可以内联。
进一步,我们的思路为:
-
避免拷贝。使用引用或指针将容器传进参数里,作为“输出参数”。但是
std::visit(visitor{}, arg1, arg2,...)
所要求函数的参数必须都是std::variant
类型,不支持其它类型,因此此处不适用。 -
合理内联。上述的几个bool函数可以内联,以减少反复更改调用栈的开销。
-
减少使用大规模的STL容器,用灵活的小STL替换。此处使用
std::vector<>
实在没有必要。并且在之后的更新中我们加入了判断两个图形相交是否合法(是否产生无穷多交点异常)的逻辑,因此需要将返回值除了交点外添加一个bool值。于是,我们使用了灵活的std::tuple<>
将其重构成:typedef std::tuple<bool, int, Point, Point> point_container_t; point_container_t intersection(..., ...);
其中第一个位置bool表示相交的合法性,第二个位置int表示有几个交点,第三第四个位置表示交点。如果只有一个交点,则第四个位置的变量无意义;如果没有交点,则两个Point对象均无意义。
于是改进后,我们对同一组数据进行Profile,得到结果:
可以看出,保持closeManager()
函数没变,其占用率从之前的20.4%上升到了24.6%,说明整个程序主体部分的运行时间减少了\(1-20.4\%/24.6\%=17\%\),是一个很大的提升(我们管这个叫“delete测速法”