當前位置：首頁 > 编程资源 > 综合教程 >内容正文

综合教程

结对编程——最长单词链

發布時間：2023/12/4 综合教程 19 生活家

生活随笔收集整理的這篇文章主要介紹了结对编程——最长单词链小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

項目	內容
這個作業屬于哪個課程	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→vvalue[v] = max(value[v], value[u] + e.value), \quad e:u \rightarrow v value[v]=max(value[v],value[u]+e.value),e:u→v
每當結點 v 出隊時，更新自環的貢獻：
value[v]←value[v]+circle[v]value[v] \leftarrow value[v] + circle[v] value[v]←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種異常，列表如下：

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);}
}

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);}
}

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);}
}

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);}
}

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);}
}

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);}
}

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);}
}

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);}
}

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);} 
}

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);}
}

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);} 
}

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);}
}

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);} 
}

logic_error(”the result is too long”);

其中前12種異常均在CLI和GUI外層處理，真正交給 core 處理的異常只有最后的13和14兩類，對于指針數組result的長度上限為20000的異常，我們程序會在超出上限時報錯并保證返回值正確。（但是由于當輸入滿足單詞個數的限制時必然不可能使result數組長度溢出，因此我們并沒有構造針對的測試樣例，但仍然支持該異常的檢測）。

11.界面模塊的詳細設計過程

本項目我們使用了基于c++的QT 進行圖形化界面設計與實現。

11.1功能需求分析

支持導入文本文件
支持輸入文本
功能型參數必須選一個（采用下拉選項，強制限定三選一）
輔助型參數選了必須要有值（下拉選項：無 + 26個字母，同樣強制限定值合法）
是否選擇成環（使用checkBox實現）
支持保存結果到文件（solution.txt）
顯示每次操作命令的運行計時（計時功能）

11.2異常處理

選定參數后點擊開始計算，之后判斷是否有如下異常：

-n和其他任何參數一塊選
在不選-r的情況下成環
沒有滿足條件的結果需要

11.3界面實現

使用 Qt designer 進行界面設計與實現，同時添加合理的布局限制，保證當窗口大小變化時界面布局依然合理美觀。

11.4功能實現

下面結合幾個具體的功能解釋具體的邏輯實現思路（總體思路是使用lambda表達式進行邏輯書寫）：

導入文本

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);});

點擊右上角”上傳文件“即可選取單詞文本：

保存結果

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();});

點擊”導出結果“即可將結果報錯到指定位置的文件中：

異常提示

以 -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 實際花費時間

已經記錄在最開始的表格中。

總結

以上是生活随笔為你收集整理的结对编程——最长单词链的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。