項目 | 内容 |
---|---|
這個作業屬于哪個課程 | 2020春季計算機學院軟體工程(羅傑 任建) |
這個作業的要求在哪裡 | 個人項目作業 |
我在這個課程的目标是 | 完成一次完整的軟體開發經曆 并以部落格的方式記錄開發過程的心得 掌握團隊協作的技巧 做出一個優秀的、持久的、具有實際意義的産品 |
這個作業在哪個具體方面幫助我實作目标 | 體驗《建構之法》中提到的 效能分析及個人軟體開發流程對于項目開發帶來的幫助 |
教學班級 | 006 |
項目位址 | Intersections | q2l's GitHub |
Personal Software Process Table (PSP)
在開始實作程式之前,在下述 PSP 表格記錄下你估計将在程式的各個子產品的開發上耗費的時間。(0.5')
PSP2.1 | Personal Software Process Stages | 預估耗時(分鐘) | 實際耗時(分鐘) |
---|---|---|---|
Planning | 計劃 | 10 | |
· Estimate | · 估計這個任務需要多少時間 | ||
Development | 開發 | 115 | 180 |
· Analysis | · 需求分析 (包括學習新技術) | 20 | 15 |
· Design Spec | · 生成設計文檔 | ||
· Design Review | · 設計複審 (和同僚稽核設計文檔) | ||
· Coding Standard | · 代碼規範 (為目前的開發制定合适的規範) | 5 | |
· Design | · 具體設計 | ||
· Coding | · 具體編碼 | 30 | 60 |
· Code Review | · 代碼複審 | ||
· Test | · 測試(自我測試,修改代碼,送出修改) | ||
Reporting | 報告 | 80 | |
· Test Report | · 測試報告 | ||
· Size Measurement | · 計算工作量 | ||
· Postmortem & Process Improvement Plan | · 事後總結, 并提出過程改進計劃 | ||
合計 | 235 | 270 |
解題思路
解題思路描述。即剛開始拿到題目後,如何思考,如何找資料的過程。(3')
首先拿到題幹,是一道 幾何題目 ,具體分析如下:
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiIn5GcucUUaZzLcBTMvw1Mw8CXwIDMy8CXzV2Zh1WavwVbvNmLjlGc1lmbuk2Lc9CX6MHc0RHaiojIsJye.png)
對于直線交點的求解我們有很多種方法,從直接的暴力運算到矩陣表示等等,考慮到代碼的風格和可擴充性我們不采取直接暴力求每個交點然後存儲的方式,我們選用了克萊姆法則求解線性方程組的方法,将直線表示為參數方程處理。
是以我們加以定義結構體存儲(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日。