结对编程博客

1、GitHub项目地址

2、PSP表格

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

 

3、看教科书和其它资料中关于Information Hiding, Interface Design, Loose Coupling的章节，说明你们在结对编程中是如何利用这些方法对接口进行设计的

• Information Hiding：

  信息隐藏指在设计和确定模块时，使得一个模块内包含的特定信息（过程或数据），对于不需要这些信息的其他模块来说，是不可访问的。

  • 信息集中化。减少函数之间的耦合，函数间仅通过很少的的变量来协作处理数据。

  • 隐藏变量。尽量使用private变量，并尽量避免其他类需要访问本类的数据。

• Interface Design:

  页面布局的首要目的就是为了页面功能的秩序感，使其在页面功能的分类以及轻重缓急的表现上更加合理，符合用户的心智模型。

  • UI使用了vertical spacer，各个选项增加了中文注释，并且有错误提示。

• Loose Coupling：

  松耦合的目标是最小化依赖。松耦合这个概念主要用来处理可伸缩性、灵活性和容错这些需求。

  • 减少函数之间的耦合，在不同模块之间的的交互的信息尽可能的少。

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

计算模块主要有6个类，Core类，DFS类，Error类，Input类，PreProcess类，RingDfs类。

Input类用于从输入中提取所需要的信息，如模式、开头结尾、路径等。

PreProcess类用于处理数据，包括分割单词，并依据分割出的单词生成图，输出结果等。

DFS类用于寻找图中是否有环。

RingDfs类用于根据生成的图进行搜索，寻找符合要求的最长路径。

Core类用于封装。

Error类用于异常时报错。

Input类

方法名	作用	调用方法
Input(int num, char * paras[])	根据程序参数，提取相应信息，如各类参数，文件路径等	本类私有方法，Error(string str)方法
Input(string str);	根据输入字符串提取相应信息	本类私有方法
int getMode()	返回指定的单词链类型，1为单词数，2为字母数
int getIfRing()	返回是否允许环
int getHead()	返回指定的单词链开头，0为无限制，否则为字母的ASCII码值
int getTail()	返回指定单词链结尾，规则同上
string getPath()	返回输入的文件路径
string getInput()	返回输入的完整字符串，用于调试

PreProcess类

方法名	作用	调用方法
PreProcess(char* wordss[], int len, int r);	根据输入的单词表、长度、是否有环，判断是否合法并生成图	本地私有方法，Error(string str)方法
PreProcess(string str, int n, char* words[], int r)	根据输入的包含所有单词的字符串、长度、是否有环，生成单词表与图。单词表char* []是为了满足接口要求。	本地私有方法
PreProcess(string str, int r)	根据输入的路径与是否有环，生成单词表与图	本地私有方法
void printGraph()	打印合并同首尾单词后的图
void printRingGraph()	答应元素
void print(vector <string> ary)	根据输入的容器，将其中单词按顺序输出至solution.txt
void VecToStr(char* result[], vector <string> ans)	将图转化为单词表格式，以满足同接口要求	Error(string str)方法

DFS类

方法名	作用	调用方法
DFS(PreProcess pp)	生成实例
void getGraph()	获取已生成好的图
bool hasRing()	判断图中是否有除了自环以外的环

RingDFS类

方法名	作用	调用方法
RingDFS(PreProcess pp)	生成实例，pp中含有图等信息
vector <string> initDFS(int mode, int head, int tail, int ring)	根据输入的各类参数，以及获取到的图，搜索符合要求的单词链，并返回结果	本地私有方法，Error(string str)方法

Core类

方法名	作用	调用方法
int gen_chain_word(char* words[], int len, char* result[], char h ead, char tail, bool enable_loop)	根据输入的单词表、长度、参数等，搜索单词数量最多的符合要求的单词链	Input::Input
int gen_chain_char(char* words[], int len, char* result[], char head, char tail, bool enable_loop)	根据输入的单词表、长度、参数等，搜索字母数量最多的符合要求的单词链	同上

Error类

方法名	作用	调用方法
void Error(std::string str)	根据输入的报错信息抛出异常

算法基于bfs的改进（改进原理见第6部分），基本原理简单易懂。对于无环的情况下，建图时合并了同首尾单词，只保留字母数量最大的单词。

5、画出UML图显示计算模块部分各个实体之间的关系

 

 

 

6、计算模块接口部分的性能改进。 记录在改进计算模块性能上所花费的时间，描述你改进的思路，并展示一张性能分析图（由VS 2015/2017的性能分析工具自动生成），并展示你程序中消耗最大的函数

以下为无环，单词数量9900的运行情况：

 

可见，大部分时间花在了建图时的各种关于内存的操作上。这是因为在优化了无环的搜索算法后，将搜索部分的复杂度限制在了O(26x26)，速度很快，因此关于内存的各类操作成为了最占用时间的操作。

对于算法的具体优化如下：

对于无环的搜索，按如下方法建图：因为无环，所以以26个字母为节点，单词为边，以a开头b结尾的单词，表现为由节点a指向节点b的一条边。

在搜索算法上，以递归BFS搜索为基础，在节点b的递归退出时，即可确保b往后的所有路径均已遍历，因此可以得到以b为开头，能搜索到的最长符合要求的单词链长度，保存该长度，记为L(b)。之后若其他节点访问节点b时，比如上述例子中的a节点访问b节点，不需要再次进入b递归，只需要比较（L(b)）与（由a指向b的边长度）之和，与原本的L(a)的大小，并将大者保存为新的L(a)即可。

这样，在所有节点递归结束后，得到了每个节点往后所能达到的符合要求的单词链的最大长度。根据此信息输出最长路径即可。

该算法确保了每条边只走一次，不会重复走同一条边（同一个单词），因此，在无环的基础上其复杂度为O(26x26)。

但是，在有环的问题中，因为环的存在以及该方法无法判断L(b)中有哪些节点，因此可能会导致重复走同一条边，该算法无法使用。

7、看Design by Contract, Code Contract的内容 ，描述这些做法的优缺点, 说明你是如何把它们融入结对作业中的

契约式设计就是按照某种规定对一些数据等做出约定,如果超出约定,程序将不再运行,例如要求输入的参数必须满足某种条件。

我们要求发现了bug之后，先对输入进行测试，保证了输入符合约定之后，再将相关模块交给负责人修改。

8、计算模块部分单元测试展示。 展示出项目部分单元测试代码，并说明测试的函数，构造测试数据的思路

部分单元测试代码如下：

 

这两部分测试数据，测试的是方法Input Input(string str)，方法Input Input(int num, char* paras[])。两个方法的作用分别是根据输入的字符串，或程序的参数提取相应的设置信息，文件路径等。

测试的思路是构造符合被测方法输入数据结构要求的数据，并尽量复杂，以达到更高的分支覆盖率。

以图中的测试用例为例，因为测试的是处理输入的方法，因此在构造输入数据时尽量构造较为复杂的输入，即尽量输入更多的参数，以覆盖较多的分支。

对于异常测试，测试代码如下：

 

在catch方法中通过判断异常信息是否符合预期的方式，来判断是否触发了所要测试的异常。

同时，在应该触发异常的代码下一行加入一条永假的断言Assert::AreEqual("Error Test Didn't Throw Error!", " ");，以确保通过的测试，是触发了正确的异常，而不是没有触发异常导致没有进入catch，根本没有运行catch中的断言。

9、计算模块部分异常处理说明

所有的异常如下：

• 输入错误

  • Chain Type Parameter Error

    在已经输入过-w或-c参数，即指定过单词链类型的情况下，再次输入这两个参数。

    单元测试：

    try {
               Input input("-w -c ..\Pair_Programming\DFSTest2.txt"); Assert::AreEqual("Error Test Didn't Throw Error!", " "); } catch (string str) { string s = "Chain Type Parameter Error"; Assert::AreEqual(s, str); }

  • Head Duplicate Definition Error

    在已经使用-h指令规定过开头的情况下，再次指定开头。

    单元测试：

    try {
               Input input("-w -h a -h a ..\\Pair_Programming\\DFSTest2.txt"); Assert::AreEqual("Error Test Didn't Throw Error!", " "); } catch (string str) { string s = "Head Duplicate Definition Error"; Assert::AreEqual(s, str); }

  • Lack Space Error

    在一次性输入所有参数时，参数之间、-h指令与制定的开头字母之间应有空格。没有空格时抛出次异常。

    单元测试：

    try {
               Input input("-w -ha ..\\Pair_Programming\\DFSTest2.txt"); Assert::AreEqual("Error Test Didn't Throw Error!", " "); } catch (string str) { string s = "Lack Space Error"; Assert::AreEqual(s, str); }

  • Head Letter Error

    指定的开头字符不是字母。

    单元测试：

    try {
               Input input("-w -h + ..\\Pair_Programming\\DFSTest2.txt"); Assert::AreEqual("Error Test Didn't Throw Error!", " "); } catch (string str) { string s = "Head Letter Error"; Assert::AreEqual(s, str); }

  • Tail Duplicate Definition Error

    使用-t指令指定过结尾的情况下再次使用该指令。

    单元测试：

    try {
               Input input("-w -t a -t a ..\\Pair_Programming\\DFSTest2.txt"); Assert::AreEqual("Error Test Didn't Throw Error!", " "); } catch (string str) { string s = "Tail Duplicate Definition Error"; Assert::AreEqual(s, str); }

  • Tail Letter Error

    制定的结尾字符不是字母。

    单元测试：

    try {
               Input input("-w -t + ..\\Pair_Programming\\DFSTest2.txt"); Assert::AreEqual("Error Test Didn't Throw Error!", " "); } catch (string str) { string s = "Tail Letter Error"; Assert::AreEqual(s, str); }

  • Ring Parameter Duplicate

    多次使用-r参数。

    单元测试：

    try {
               Input input("-w -r -r ..\\Pair_Programming\\DFSTest2.txt"); Assert::AreEqual("Error Test Didn't Throw Error!", " "); } catch (string str) { string s = "Ring Parameter Duplicate"; Assert::AreEqual(s, str); }

  • Parameter Type Error

    输入的参数不符合规定。

    单元测试：

    try {
               Input input("-w -z ..\\Pair_Programming\\DFSTest2.txt"); Assert::AreEqual("Error Test Didn't Throw Error!", " "); } catch (string str) { string s = "Parameter Type Error"; Assert::AreEqual(s, str); }

  • Lack Chain Type Parameter

    在输入中没有使用-w或-c制定指定单词链类型。

    单元测试：

    try {
               Input input("-h a ..\\Pair_Programming\\DFSTest2.txt"); Assert::AreEqual("Error Test Didn't Throw Error!", " "); } catch (string str) { string s = "Lack Chain Type Parameter"; Assert::AreEqual(s, str); }

• 数据错误

  • Input File Doesn't Exit

    输入的文件路径不存在。

    单元测试：

    try {
               PreProcess pp ("noFile.txt", 0); Assert::AreEqual("Error Test Didn't Throw Error!", " "); } catch (string str) { string s = "Input File Doesn't Exit"; Assert::AreEqual(s, str); }

  • Multiple Self Ring Found

    在不允许有环的情况下，出现了多个自环。

    单元测试：

    try {
               PreProcess pp("..\\Pair_Programming\\PPErrorTest1.txt", 0); Assert::AreEqual("Error Test Didn't Throw Error!", " "); } catch (string str) { string s = "Multiple Self Ring Found"; Assert::AreEqual(s, str); }

    其中，PPPErrorTest1.txt的内容如下：

    bc cc cd df ff beee eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee eeeeeeeee ef fg gb

     

  • No Word Chain in File

    输入的文件中单次数量小于2，不构成单词链。

    单元测试：

    try {
               PreProcess pp("..\\Pair_Programming\\PPErrorTest2.txt", 0); } catch (string str) { string s = "No Word Chain in File"; Assert::AreEqual(s, str); }

    其中，PPErrortEST2.TXT文件内容如下：

    bc ​

  • Ring Detected When not Allowed

    在没有使用-r参数，的情况下，单词链中出现了环。

    单元测试：

    try {
               PreProcess pp("..\\Pair_Programming\\DFSTest1.txt", 0); DFS dfs(pp); dfs.getGraph(); dfs.hasRing(0); Assert::AreEqual("Error Test Didn't Throw Error!", " "); } catch (string str) { string s = "Ring Detected When not Allowed"; Assert::AreEqual(s, str); }

    其中，DFSTest1.txt文件的内容如下：

    bc cc cd df ff beee eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee ef fg gb

10、界面模块的详细设计过程

开发平台

使用的是Qt Creator 3.4.2进行开发的，由于Qt自带了前端设计的功能，开发起来比较简单。

1、设计界面

使用的是Qt Creator自带的设计面板，操作简单只需要拖拽即可，以下是具体设计。

 

2、编写后端

在设计好了界面之后，只需要编写好slots函数就可在设计面板中简单的关联(代码未全部贴出)

mainwindow.h:

#ifndef MAINWINDOW_H #define MAINWINDOW_H ​ #include 
    
      ​ namespace Ui {
       class MainWindow; } class MainWindow : public QMainWindow { Q_OBJECT public: explicit MainWindow(QWidget *parent = 0); ~MainWindow(); private: Ui::MainWindow *ui; bool H; int wc; bool R; bool T; QString tmp; bool fFile; private slots: void setC(bool b); }; #endif // MAINWINDOW_H
    

mainwindow.cpp:

#include "mainwindow.h" #include "ui_mainwindow.h" #include 
    
      #include "qtextbrowser.h" #include 
     
       #include 
      
        #include 
       
         #include 
        
          MainWindow::MainWindow(QWidget *parent) : QMainWindow(parent), ui(new Ui::MainWindow) { ui->setupUi(this); //ui->hideButton->hide(); } MainWindow::~MainWindow() { delete ui; } void MainWindow::setC(bool b){ this->wc = b?2:1; }
        
       
      
     
    

编写完成后，需要做的就是将函数与组件关联起来，同样在设计面板中操作。

 

 

关于Qt的信号槽机制，具体可以看这篇，由于是在设计模板中关联的，所以并不需要手动编写connect函数。

11、界面模块与计算模块的对接

首先，将计算模块打包成dll文件，为了使用方便，将统一的接口gen_chain_word(char* words[], int len, char* result[], char head, char tail, bool enable_loop)与接口gen_chain_char(char* words[], int len, char* result[], char head, char tail, bool enable_loop)定义为函数而非类方法。

打包好后，将生成的Core.dll文件复制到工程的debug文件夹或release文件夹中，通过以下代码导入两个上述接口：

typedef int(*ptr_word)(char* words[], int len, char* result[], char head, char tail, bool enable_loop); typedef int(*ptr_char)(char* words[], int len, char* result[], char head, char tail, bool enable_loop); HINSTANCE CoreDLL = LoadLibrary("Core.dll"); ptr_word gen_chain_word = (ptr_word)GetProcAddress(CoreDLL, "gen_chain_word"); ptr_char gen_chain_char = (ptr_word)GetProcAddress(CoreDLL, "gen_chain_char");

导入后，便可以直接调用两个函数。

12、描述结对的过程

在结对的过程中，首先我们在一起预估各个难度的复杂度，之后对于部分逻辑极为简单且不重要的部分如读入等，进行分工，并行开发提高速度。对于核心的部分，如搜索算法的完成、优化等，我们按照结对编程的原则，一人写一人检查，确保没有BUG以及算法的正确性。

 

13、看教科书和其它参考书，网站中关于结对编程的章节， 明结对编程的优点和缺点。结对的每一个人的优点和缺点在哪里

• 优点：在复审中对于能以找到的bug，结对编程能够避免钻牛角尖，增加debug的速度。在编写代码过程中，结对编程有助于促进两方思考，避免遗漏，增加正确性。也能相互监督保证代码质量。

• 缺点：对于一些比较简单的代码，结对编程会拖累双方的进度，影响项目进程。对于两个人都不擅长的领域，就没有结对的必要。

我的优缺点：

• 积极交流，认真负责，复审仔细

• 比较拖沓

同伴的优缺点：

• 主动负责，思路敏捷，完成工作多

• 缺乏交流

14、PSP表格

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

15、松耦合

我们与学号的队伍进行了松耦合测试，结果正确，对方使用我方Core.dll的运行结果截图如下：

在刚开始耦合时出现了问题，因为在对于head的定义中，我们组的逻辑是当head不为0即认为是规定的开头字母，但接口内部没有检查其正确性，而对方认为head不规定时为'0'。 出现问题后，我们组在接口内部加2上了对于参数的合法性判断，之后没有其他问题。

之后我们还与进行了耦合，运行正确，没有问题。