结对编程——最长单词链

项目	内容
这个作业属于哪个课程	2023 年北航软件工程
这个作业的要求在哪里	结对项目-最长英语单词链
我在这个课程的目标是	学习软件工程的科学理论知识，在实践中锻炼自我思考能力和团队开发能力
这个作业在哪个具体方面帮助我实现目标	通过两人合作完成一个小项目，锻炼思考、合作和时间管理能力

1.项目说明

• 教学班级：周四上午班
• 项目地址：https://github.com/SE-cjj-wxz/wordlist-app

2 各模块开发耗费时间

PSP2.1	Personal Software Process Stages	预估耗时（分钟）	实际耗时（分钟）
Planning	计划	120	240
· Estimate	· 估计这个任务需要多少时间	120	240
Development	开发	1440	1870
· Analysis	· 需求分析 (包括学习新技术)	120	240
· Design Spec	· 生成设计文档	120	120
· Design Review	· 设计复审 (和同事审核设计文档)	60	60
· Coding Standard	· 代码规范 (为目前的开发制定合适的规范)	60	30
· Design	· 具体设计	240	240
· Coding	· 具体编码	480	720
· Code Review	· 代码复审	120	120
· Test	· 测试（自我测试，修改代码，提交修改）	240	360
Reporting	报告	390	510
· Test Report	· 测试报告	240	120
· Size Measurement	· 计算工作量	30	30
· Postmortem & Process Improvement Plan	· 事后总结, 并提出过程改进计划	120	360
	合计	1950	2620

3 阅读教材与资料

Information Hiding： 信息隐藏是指在设计软件系统的时候，将系统内部的实现细节隐藏起来，只向外界提供必要的接口和信息，从而达到保护系统安全性和保证系统可维护性的目的。

在设计我们的计算模块的时候，通过实现 core.cpp 在用户交互界面和内部图的数据结构之间建立起一层抽象，将图的数据结构和实现都封装起来，只提供三个接口供外界调用。

Interface Design： 界面设计是为软件、应用程序或网站等交互系统的用户界面进行的设计和优化，旨在创造一种易于使用、直观、具有吸引力和有效的界面，以增强用户体验。

我们在进行界面设计的时候，考虑了输入、输出、选项的特点，使得界面简洁美观。我们通过下拉框的形式让用户选择选项，减少了用户误操作的可能性。在此基础上，我们由对多个选项取值进行约束，更进一步防止用户选择逻辑上不合理的选项。

Loose Coupling： 松散耦合是一种设计原则，指的是在软件系统中，各个组件或模块之间的依赖关系应该尽可能地松散。组件之间应该相互独立，可以独立地开发、测试、部署和维护，而不会互相影响或依赖过于紧密。

我们的用户界面和计算模块遵循了松散耦合的设计原则，可以独立地开发、测试，开发人员只需要遵守约定的接口即可。我们与其他小组交换了 GUI 和 core 并完成测试，这也证明了我们的设计符合松散耦合。

4 计算模块接口的设计与实现过程

4.1 建图与数据结构

我们的建图方式是每个字母作为一个结点，每个单词作为一条有向边，从单词首字母对应的结点连接到单词尾字母对应的结点，对于自环需要特殊处理。此外，为了方便处理，我们为强连通分量单独建类。

具体来说，我们实现了以下数据结构来存储图：

• 结点类：每个字母对应一个结点，记录这个结点的出边、自环、入度
• 边类：每个单词对应一条边，记录单词字符串，边权，边的终点。
• 图类：记录图上的每个结点和强连通分量
• 强连通分量：存储属于这个强连通分量的结点，存储强连通分量任意两点之间的最短距离

4.2 计算模块接口

能够构成所有单词链的数目

计算模块对应接口为：countChains

根据输入的单词列表建图，判断是否成环。若成环，则抛出异常。否则在图上进行拓扑排序，拓扑排序的同时记录答案。

计算最多字母数量的单词链

计算模块对应的接口为： getLongestCharChain

根据输入的单词列表建图，边权为单词长度，判断是否成环。

若不成环： 对图中的结点进行拓扑排序，按照拓扑序进行 DP 转移，DP 转移方程为：
$$value[v]=max(value[v],value[u]+e.value),e:u\to v$$
每当结点 v 出队时，更新自环的贡献：
$$value[v]\leftarrow value[v]+circle[v]$$
若存在环： 先求出图的强连通分量，同时也得到了强连通分量之间的拓扑关系。然后对每个强连通分量内部使用 DFS 算法求解出任意两个点之间的距离。对于自环，都在 DFS 时加入答案，在拓扑序 DP 的阶段只考虑强连通分量之间的边。

附加型参数：

• -h：对于不能作为首字母的字母结点，其初始值为 -1，在 DP 转移的过程中，如果 value < 0 则不能向外转移。对于能作为首字母的结点，其初始值为0。
• -t：最后计算最大值的时候只统计能作为尾字母的结点的值。
• -j：删除不能出现的首字母对应的结点的所有自环和出边。

计算最多单词数量的单词链

计算模块对应的接口为： getLongestWordChain

与计算最多字母数量的单词链的过程基本一致，唯一的区别是建图时将边权都赋值为1。

5 编译器编译无警告

6 UML 图

7 计算模块接口部分的性能改进

7.1 性能测试

我们使用了 Google 开源的性能分析工具 gproftools 来分析程序的性能，部分截图如下：

上面文本一共六列，分别是：

• 分析样本数量（不包含其他函数调用）
• 分析样本百分比（不包含其他函数调用）
• 目前为止的分析样本百分比（不包含其他函数调用）
• 分析样本数量（包含其他函数调用）
• 分析样本百分比（包含其他函数调用）
• 函数名

7.2 性能改进

以性能测试中的程序为基准，将其某一组数据运行时间作为 baseline 。

由性能分析结果可知，最耗时的函数是 SCC::dfs ，考虑通过并行的方式提高运行效率，我们采用 OpenMP 并行计算以强连通分量每个点为起点的 DFS 。该函数中使用 vector<string> 记录遍历的路径，字符串拷贝耗时较大，用边类的指针代替字符串。

改进后性能对比：

• baseline：35.2 s
• OpenMP：16.7 s
• OpenMP + pointer：11.4 s

最终加速比约为 3.1

8 契约式设计

契约式设计（Design by Contract）是一种软件设计方法，它强调程序中的各个模块应该像一份契约一样，在其接口上明确定义它们的职责、行为和约束条件，并将这些条件作为代码的一部分进行明确表示。

契约式设计通常由三部分组成：

• 前置条件：指在函数或方法执行之前必须满足的条件，如果前置条件不满足，则函数或方法应该返回错误或异常。
• 后置条件：指在函数或方法执行之后必须满足的条件，例如返回值的类型和值的范围等。
• 类不变式：指在类的所有方法执行之前和之后都必须满足的条件，以确保类的内部状态始终保持一致。

Code Contract 是一种在 .NET 平台上实现契约式设计的框架，它允许程序员在代码中使用断言来定义类和方法的契约条件，以确保这些条件在运行时得到满足。

契约式编程的优点：

• 增强程序的可靠性和正确性
• 提高代码的可读性和可维护性

契约式编程的缺点：

• 需要开发者额外的学习时间和维护成本
• 契约式编程引入新的概念和机制，会增加代码的复杂性

以本项目中的强连通分量 DFS 为例：

• 前置条件：强连通分量的建图完成，每个结点的自环和出边都已经就绪了
• 后置条件：强连通分量中任意两个结点之间的最长单词链已经求出
• 类不变式：强连通分量中结点和边的结构不改变

9 计算模块部分单元测试

countChains 接口的单元测试示例：

TEST(testCase, test14) {char* words[] = {"algebra","apple","exe","elephant"};int ret = 8, len = 4;char** result = (char**)malloc(sizeof(char*) * 100);int ans = countChains(words, len, result);EXPECT_EQ(ans,ret);
}

getLongestWordChain 接口的单元测试示例：

TEST(testCase, test8) {char* words[] = {"algebra","apple","zoo","elephant","under","fox","dog","moon","leaf","trick","pseudopseudohypoparathyroidism"};int ret = 2, len = 11;char head = 'l', tail = 0, ban = 0; bool circ = false;char** result = (char**)malloc(sizeof(char*) * 100);int ans = getLongestWordChain(words, len, result, head, tail, ban, circ);EXPECT_EQ(ans,ret);

getLongestCharChain 接口的单元测试示例：

TEST(testCase, test18) {char* words[] = {"algebra","apple","zoo","elephant","under","fox","dog","moon","leaf","trick","kkd"};int ret = 5, len = 11;char head = 0, tail = 'd', ban = 'l'; bool circ = true;char** result = (char**)malloc(sizeof(char*) * 100);int ans = getLongestCharChain(words, len, result, head, tail, ban, circ);EXPECT_EQ(ans,ret);
}

计算模块单元测试覆盖率：

10.计算模块部分异常处理说明

针对整个项目，我们设计了共14种异常，列表如下：

1. logic_error(”duplicate option ”);

TEST(testCase, test19) {int argc = 4; char* argv[] = {"-n","-n","input.txt"};string str = "duplicate option: -n";try {WordList(argc, argv);} catch(exception& e) {string err = e.what(); EXPECT_EQ(err, str);}
}

2. logic_error(”option that should have argument does not have argument”);

TEST(testCase, test20) {int argc = 4;char* argv[] = {"-n","input.txt","-h"};string str = "option that should have argument does not have argument: -h";try {WordList(argc, argv);} catch(exception& e) {string err = e.what(); EXPECT_EQ(err, str);}
}

3. logic_error(”option has illegal argument (not a single letter)”);

TEST(testCase, test21) {int argc = 5;char* argv[] = {"-h","an","-n","input.txt"};string str = "option has illegal argument: -h has an";try {WordList(argc, argv);} catch(exception& e) {string err = e.what(); EXPECT_EQ(err, str);}
}

4. logic_error(”illegal option”);

TEST(testCase, test22) {int argc = 5;char* argv[] = {"-b","a","-n","input.txt"};string str = "illegal option: -b";try {WordList(argc, argv);} catch(exception& e) {string err = e.what(); EXPECT_EQ(err, str);}
}

5. logic_error(”duplicate fileName”);

TEST(testCase, test23) {int argc = 4;char* argv[] = {"-n","input.txt","input2.txt"};string str = "duplicate fileName: input2.txt";try {WordList(argc, argv);} catch(exception& e) {string err = e.what(); EXPECT_EQ(err, str);}
}

6. logic_error(”missing functional parameters (-n -w -c)”);

TEST(testCase, test24) {int argc = 3;char* argv[] = {"-r","input.txt",};string str = "missing functional parameters (-n -w -c)";try {WordList(argc, argv);} catch(exception& e) {string err = e.what(); EXPECT_EQ(err, str);}
}

7. logic_error(”functional parameters are not compatible”);

TEST(testCase, test25) {int argc = 4;char* argv[] = {"-n","-w","input.txt",};string str = "functional parameters are not compatible";try {WordList(argc, argv);} catch(exception& e) {string err = e.what(); EXPECT_EQ(err, str);}
}

8. logic_error(”file does not exist”);

TEST(testCase, test26) {int argc = 3;char* argv[] = {"-n","input2.txt",};string str = "file does not exist";try {WordList(argc, argv);} catch(exception& e) {string err = e.what(); EXPECT_EQ(err, str);}
}

9. logic_error(”the file content is empty”);

TEST(testCase, test27) {char* words[] = {};int len = 0;char** result = (char**)malloc(sizeof(char*) * 100);string str = "the file content is empty";try {int ans = countChains(words, len, result);} catch(exception& e) {string err = e.what(); EXPECT_EQ(err, str);} 
}

10. logic_error(”n can only be used alone”);

TEST(testCase, test28) {int argc = 4;char* argv[] = {"-n","-r","input.txt",};string str = "-n can only be used alone";try {WordList(argc, argv);} catch(exception& e) {string err = e.what(); EXPECT_EQ(err, str);}
}

11. logic_error(”there is no matching result”);

TEST(testCase, test30) {char* words[] = {"ab","ss"	};int len = 2;char** result = (char**)malloc(sizeof(char*) * 100);string str = "there is no matching result"; try {int ans = countChains(words, len, result);} catch(exception& e) {string err = e.what(); EXPECT_EQ(err, str);} 
}

12. logic_error(”-h and -j cannot have the same value”);

TEST(testCase, test31) {int argc = 8;char* argv[] = {"-w","-h","a","-j","a","-r""input.txt",};string str = "-h and -j cannot have the same value";try {WordList(argc, argv);} catch(exception& e) {string err = e.what(); EXPECT_EQ(err, str);}
}

13. logic_error(”there is a circle in the chain without -r”)

TEST(testCase, test29) {char* words[] = {"word","draw"	};int len = 2;char** result = (char**)malloc(sizeof(char*) * 100);string str = "there is a circle in the chain without -r"; try {int ans = countChains(words, len, result);} catch(exception& e) {string err = e.what(); EXPECT_EQ(err, str);} 
}

14. logic_error(”the result is too long”);

其中前12种异常均在CLI和GUI外层处理，真正交给 core 处理的异常只有最后的13和14两类，对于指针数组result的长度上限为20000的异常，我们程序会在超出上限时报错并保证返回值正确。（但是由于当输入满足单词个数的限制时必然不可能使result数组长度溢出，因此我们并没有构造针对的测试样例，但仍然支持该异常的检测）。

11.界面模块的详细设计过程

本项目我们使用了 基于c++的QT 进行图形化界面设计与实现。

11.1功能需求分析

1. 支持导入文本文件
2. 支持输入文本
3. 功能型参数必须选一个（采用下拉选项，强制限定三选一）
4. 辅助型参数选了必须要有值（下拉选项：无 + 26个字母，同样强制限定值合法）
5. 是否选择成环（使用checkBox实现）
6. 支持保存结果到文件（solution.txt）
7. 显示每次操作命令的运行计时（计时功能）

11.2异常处理

选定参数后点击开始计算，之后判断是否有如下异常：

1. -n和其他任何参数一块选
2. 在不选-r的情况下成环
3. 没有满足条件的结果需要

11.3界面实现

使用 Qt designer 进行界面设计与实现，同时添加合理的布局限制，保证当窗口大小变化时界面布局依然合理美观。

11.4功能实现

下面结合几个具体的功能解释具体的逻辑实现思路（总体思路是使用lambda表达式进行逻辑书写）：

1. 导入文本

connect(ui->uploadFile, &QPushButton::clicked, this, [=](){QString fileName = QFileDialog::getOpenFileName(this,NULL, NULL, "Text files (*.txt);; *.*");if (fileName.isEmpty()) {return;}QFile myFile(fileName);if (!myFile.open(QFile::ReadOnly | QFile::Text)) {QMessageBox::warning(this, "文件打开失败", "你选择的文件不存在或者拒绝访问");return;}QTextStream in(&myFile);QString str = in.readAll();ui->inputText->setPlainText(str);});

点击右上角”上传文件“即可选取单词文本：

2. 保存结果

connect(ui->saveFile, &QPushButton::clicked, this, [=](){QString fileName = QFileDialog::getSaveFileName(this,NULL,  "solution.txt", "Text files (*.txt)");if (fileName.isEmpty()) {return ;}QFile myFile(fileName);if (!myFile.open(QIODevice::WriteOnly)) {QMessageBox::warning(this, "文件保存失败", "你选择的文件拒绝访问");return;}QTextStream stream(&myFile);stream << ui->outputText->toPlainText();myFile.close();});    

点击”导出结果“即可将结果报错到指定位置的文件中：

3. 异常提示

以 -n -r 为例，界面会提示用户 -n 不能和其他选项一块选择：

其他异常的提示形式与之类似，不再赘述。

12.界面模块与计算模块的对接

界面模块通过调用计算模块的动态链接 core.dll 实现相应功能，其中对于GUI中导入 dll 的方法，我们直接通过在 CMakelist中加入如下代码的方式实现：

find_library(CORE_LIB NAME core.dll PATHS ../bin/)
target_link_libraries(GUI ${CORE_LIB})

之后在 gui.cpp 中调用相应的 core.h 中定义的接口即可完成功能对接，对接效果如下，以 -w -r 为例：

其中输入文本为：

cecw cecwcwe cecwcwevwev rv gn rvb vd vt jt rukj mtnu gp yuo ytp tyip gkth ndry mugrlyipp oruk orpu
olkyur ppouthjdm tu pr olug ppouthjdml kmy ui ppouthjdmp yk yuto ppouthjdmty kyu ptpo yutp kr dyjy
ieytuyt ety uety uetyj eyj tyj ykj srh tes fcv etaw tm mtnua

可以看到结果正常输出，并且用时 28.11s。

附加题——与其他组互换模块

我们与另一组互换了模块，互换的最大问题是双发的开发环境不同，我们组是 window 环境，而另一组则是 window + Mac 环境。

另一组成员：

• 强生：20373249
• 申浩佳：20373776

1 本组core与另一组GUI

由于开发环境的不同，本组的 core.dll 并不能被另一组的GUI直接调用，因而我们选择将本组的源码直接发给对方，在对方的环境下链接生成 core.dll，最终结合运行成功，效果图如下：

2 本组GUI与另一组core

对方将 core.dll 发给本组，我们进行替换之后可以成功运行GUI，效果图如下：

3 本组core与另一组单元测试

除了进行计算模块和用户测试模块的互换外，我们使用对方的单元测试模块测试了本组的计算模块，测试效果如下：

13. 结对过程

结对编程采用线下的方式，地点通常在老主楼四楼的休息区。

14 结对编程优缺点

结对编程的优缺点：

• 优点：

  • 提高代码质量：两个人一起编写代码，每时每刻都在代码复审，质量高。
  • 促进知识分享：结对编程可以促进团队成员之间的知识分享和技能传授。
  • 改善沟通：结对编程可以帮助团队成员更好地沟通和协作，减少沟通障碍和误解。

• 缺点：

  • 人力成本增加：结对编程需要两个人一起工作，因此需要额外的人力资源。
  • 可能引起矛盾：两个人一起工作可能会出现意见分歧和矛盾，从而影响工作进度和质量。

队员优缺点分析：

姓名	优点	缺点
王雪竹	算法基础较好，使用C++语言相对较多，喜欢探索新技术	不熟悉 GUI 的编写
陈俊杰	熟悉 GUI 开发，时间规划能力强，信息搜集能力强	不熟悉 C++ 语言

15 实际花费时间

已经记录在最开始的表格中。