我是作業
結對情況
305 錦謀
403 俊
GitHub 項目連結
（其實是code.net項目連結）
生成JSON程式，需要輸入學生數和部門數
比對程式，需要輸入上面生成程式用的學生數和部門數
設計說明
接口設計（API）
class dep2stu()
{
virtual void readdata(int studentnumber,int department) = 0;
virtual void match() = 0;
virtual void printdata() = 0;
}
内部實作設計（類圖）
學生類的屬性主要包括了：學号、姓名、績點成績、興趣标記、加入部門數以及申請部門清單、以及學生的時間安排。Priority是按照比對規則所确定的學生優先度。
部門類主要屬性有學号、姓名、部門人數上限、部門時間安排部門所需興趣标簽等。
比對算法設計（思想/流程等）
比對的過程主要是兩次篩選。
第一次從學生入手，第二次從部門開始。比對規則主要是首先确定學生優先度。這裡按照每一位學生的績點成績從高到低依次排列。然後再根據學生所申請部門逐個進行比對。按照部門要求進行篩選。篩選過程主要是，對于選擇該部門的學生，首先要滿足至少出現一次與部門事務安排時間相符合，即確定該名學生至少能夠有時間參加部門活動。然後對于符合時間要求的學生，還要視其興趣情況而定。
分為兩種情況。
- 對于滿足興趣至少一種符合該部門要求的學生，可以加入該部門
- 為了保證部門能夠最大限度收到成員，對于興趣沒有一項滿足該部門的學生，并不直接淘汰，而是将其加入部門的候選成員隊列，當部門完成對所有學生的篩選過後，如果有部門還未收滿成員，則可以從候選名單中依次選入部門直到部門人數達到上限。（這裡仍然保證了候選成員依舊按照績點成績為優先級）。
兩次選擇過程結束後，則完成了這次比對。
第一次篩選
第二次篩選
測試資料如何生成？
根據
輸入的資料，另外寫生成程式随機實作
寫了個生成程式，部分函數實作如下
string tags[10] = { "writing", "management", "dancing", "singing", "running","photography", "painting", "broadcast", "edit", "contact"........};
vector<string>departments;//部門數組
/**
* \brief 生成範圍内随機數
* \param m 範圍最小值
* \param n 範圍最大值
* \return 範圍内随機數
*/
int rand_int(int m, int n)
{
const auto result = rand() % (n - m + 1) + m;
return result;
}
/**
* \brief 生成随機小數
* \param min 随機下限
* \param max 随機上限
* \return 生成的範圍内随機浮點數
*/
double rand_double(int min, int max)
{// 計算 0，1之間的随機小數,得到的值域近似為(0,1)
const auto m1 = double(rand() % 101) / 101;
//将 區間變為(min+1,max)
min++;
//計算 min+1,max 之間的随機整數，得到的值域為[min+1,max]
auto m2 = double((rand() % (max - min + 1)) + min);
//令值域為[min,max-1]
m2 = m2 - 1;
return m1 + m2; //傳回值域為(min,max),為所求随機浮點數
}
/**
* \brief 生成随機部門名
* \return 部門名
*/
string rand_depname()
{
string result = "XXXXXXXX";
for (auto i = 0; i < result.size(); i++)
{
result[i] = char(rand_int('A', 'z'));
if (result[i] > 'Z' && result[i] < 'a')
{
result[i] += 6;
}
}
departments.push_back(result);
/*cout << departments.back() << endl;
Sleep(1500);*/
return result;
}
string rand_charactertics()
{
const auto flag = rand_int(0, 9);
return tags[flag];
}
/**
* \brief 得到部門标簽字元串
* \return 傳回部門标簽
*/
string rand_deptags()
{
const auto interest_number = rand_int(1, 3);
int flag[10] = { 0 };
auto order = rand_int(0, 9);
string result = "[";
flag[order] = 1;
result = result + "\"" + tags[order] + "\"";
for (auto i = 1; i < interest_number; i++)
{
result = result + ",\"";
while (flag[order])
{
order = rand_int(0, 9);
}
result = result + tags[order] + "\"";
flag[order] = true;
}
result = result + "]";
return result;
}
/**
* \brief 姓名
* \return 姓名
*/
string rand_stuname()
{
return get_name();
}
/**
* \brief 生成随機部門字元串
* \return 申請的部門清單
*/
string rand_applies()
{
const auto apply_number = rand_int(1, 5);//申請的部門數
bool flag[100] = { false };//部門是否已申請的标志
auto order = rand_int(0, departments.size()-1);//申請的部門的序号
auto result = "[\"" + departments.at(order) + "\"";//申請的部門名
flag[order] = true;
for (auto i = 1; i < apply_number; i++)
{
result = result + ",\"";
while (flag[order])
{
order = rand_int(0, departments.size()-1);
}
result = result + departments.at(order) + "\"";
flag[order] = true;
}
result += "]";
return result;
}
完全就是文本文檔的生成方法啊！是不是會被打！
如何評價自己的比對算法？
對于這個算法，大體上還是實作了我們一開始的想法。
首先，對于學生優先度按照績點确立。主要是利用了快速排序算法，這個算法在資料結構課上學習過了，用起來還是比較順手的，而且在大量資料的情況下還是可以比較穩定的，算法複雜度在nlogn。
對于第一次篩選的過程，采用了笨辦法。即一次次去周遊通路每個學生的申請清單每次通路學生申請的時候還都要通路部門名稱，這個部分有太多的重複操作，且耗時最大，沒有能夠做到相應的精簡。在最壞的情況下這個算法複雜度達到了n的三次方。
對于第二次篩選的過程，在快排之後記錄每個學生的優先度并作為其成員。第二次篩選是針對未收滿的部門，時間主要花費在對每個部門的周遊以及未滿部門成員隊列的操作，最壞情況下複雜度達到n的平方。
關鍵代碼解釋
快排
這個快排算法主要思想就是分塊排序。首先選取最左端學生的績點作為關鍵字。周遊這個塊，當通路到績點大于關鍵字的學生，将其與原來的最左端所處的位置調換位置。這樣每次分塊都實作了标記的那個學生前面的都是大于他的績點的學生，後面都是績點小于他的學生，實作了塊内的相對有序。然後将塊逐漸變小最後實作整個塊的相對降序。
int par(int l, int r)
{
const double key = student_s[l].getgpa();
Student temp;
auto i = l, j = r;
while (i < j)
{
while (i < j&&student_s[j].getgpa() <= key)
j--;
temp = student_s[j];
student_s[j] = student_s[i];
student_s[i] = temp;
while (i < j&&student_s[i].getgpa() >= key)
i++;
if (i == j)
{
return i;
}
temp = student_s[j];
student_s[j] = student_s[i];
student_s[i] = temp;
}
}
void quicksort(int l, int r)
{
if (l < r)
{
const auto i = par(l, r);
quicksort(l, i - 1);
quicksort(i + 1, r);
}
}
第一次篩選代碼
//周遊學生和部門
for (auto i = 0; i < students_number; i++)
{
while (!student_s[i].apply.empty())
{//申請隊列為空說明完成比對退出
for (auto j = 0; j < department_number; j++)
{
if (student_s[i].apply.empty())
break;
if (student_s[i].apply.front() == department_d[j].getDname())
{//如果學生申請清單與目前部門名稱比對
if (department_d[j].member.size() < department_d[j].getlimit() && Issuit(student_s[i], department_d[j]))
{ //如果部門成員數量沒有達到上限
if (Istags(student_s[i], department_d[j]))
{//加入該成員
department_d[j].member.push(student_s[i].getSname());
student_s[i].Setp();//學生參加部門數+1
}
else
department_d[j].bPush(student_s[i]);
}
if (!student_s[i].apply.empty())student_s[i].apply.pop();//無論是否學生能加入部門，都要講該部門從申請清單推出 ，確定循環可以終止
}
}
}
}
第二次篩選算法
for (int i = 0; i < department_number; i++)
{
while (!department_d[i].bEmpty())
{
if (department_d[i].getlimit() > department_d[i].member.size())
{
const int snub = department_d[i].bFront().getpr();//用于記錄候選成員的優先值
department_d[i].member.push(student_s[snub].getSname());
student_s[snub].Setp();
department_d[i].bPop();//候選加入推出
}
if (department_d[i].getlimit() == department_d[i].member.size())break;
}
}
運作及測試結果展示
說明：（有關測試時間的代碼在上傳源碼裡沒有）
在解決方案配置為debug時消耗有一定的時間，資料5000-100的時候達到20S。
但是在release下，資料5000-100不需1S！
神奇
完整測試資料連結
- 輸入情況
{
"departments":
[
{
"department_no":"FZU_1905",
"department_name":"jRaDYxXL",
"member_limit": 14,
"tags":["painting","singing","photography"],
"event_schedules":["Fri.21:00-22:00"]
},
……
]
"students":
[
{
"student_no":"161708261",
"student_name":"Jorge Wagner",
"student_GPA":2.02,
"apply_departments":["tXZDfoaP"],
"tags":["contact"],
"available_schedules":["Mon.19:00-20:00","Thu.20:00 - 21:00","Fri.21:00-22:00","Set.21:00-22:00","Tue.20:00 - 21:00"……]
},
……
]
}
- 測試200位同學，20個部門的情況
{
"matched_department_view":
[
{
"department_name":"jRaDYxXL",
"members":["Dale Butler","Aaron Ellis","Randall White","Janice Webb","Dorothy Reyes","Julia Ross","Keith Allen","Josephine Weaver","Warren Hudson","Rita Franklin","JeanneJames Wallace","Willie Torres","Justin Clark","Jesus Ferguson"]
},
……
],
"matched_student_view":
[
{
"student_name":"Dale Butler",
"departments":["qlEFHBVr","jRaDYxXL","aBHXcebW"]
},
……
],
"standalone_departments":
[
"tXZDfoaP",
"rlYJPezy",
"xdaEEMyr",
"IqExCZha"
]
"standalone_students"：
[
"Irene Lee",
"George Gonzalez",
"Melissa Torres",
……
]
- 測試500位同學，30個部門的情況
{
"matched_department_view":
[
{
"department_name":"FPfjMnLY",
"members":["Leonard Washington","Michael Richardson","Eddie Lawson"]
},
……
]
"matched_student_view":
[
{
"student_name":"Crystal Rose",
"departments":["ZbkWhWSe"]
},
……
]
"standalone_departments":
[
"qZkKNLiV",
"vWYCXFXb",
"RIGouufg"
]
"standalone_students"：
[
"Judy Cox",
"Phyllis Stephens",
"Kenneth Nichols",
……
]
- 測試1000位同學，50個部門的情況
{
"matched_department_view":
[
{
"department_name":"LdatYlty",
"members":["Tina Freeman","Lawrence Green","Roger Hudson","Sheila Kelly"]
},
……
]
"matched_student_view":
[
{
"student_name":"kexiao Spencer",
"departments":["YXfRAPLx","fodAHEeT","wftWyfnN"]
},
……
]
"standalone_departments":
[
"ivylCYEl",
"uaUeeadc"
]
"standalone_students"：
[
"Eugene Murray",
"Jesus Carter",
……
]
- 測試5000位同學，100個部門的情況
{
"matched_department_view":
[
{
"department_name":"YBsdwiIm",
"members":["Manuel Lane","Sharon Ferguson","Sherry Dixon","Sylvia Berry","Pauline Carter","Patrick Reyes","Dean Lawrence","Carol Hudson","Sandra Walker","Joyce Price","Leroy Palmer"]
},
……
]
"matched_student_view":
[
{
"student_name":"Melvin Graham",
"departments":["XJaukdbN","LRnecZhP","fXZlYqbb","ftvNpJfw","DEcLDigr"]
},
……
]
"standalone_departments":
[
"cktIToQc",
"JWGXzbhE",
"ofVXRuMX",
"nxongGef",
"SiEuaziE"
]
"standalone_students"：
[
"Rodney Perkins",
"Raymond Duncan",
"Audrey Grant",
……
]
效能分析
從上圖來看，最耗時間的是就是花在了快排上面，然後是讀入資料。
很奇怪最耗時間的部分居然不是在比對而是在排序上面，那麼這排序是多耗時間啊。
快排用在了給學生按照績點排序上，如果不按照績點排序，純粹按照最原始的順序來的話，想必會省下很多時間來做其他的運算。
之後是讀入檔案資訊，我們采用的方法是将檔案内容讀入字元串，再将字元串做成JSON變量。可是檔案本身就是JSON，這樣的轉化無形之種就導緻了多餘的時間消耗。
遇到的困難及解決方法
遇到的困難主要有兩點。第一點就是對于學生按照績點進行排序。第二點就是對于學生申請與部門名稱的對應。
- 首先最直覺的是兩次循環兩次周遊，但是太過于麻煩。然後嘗試冒泡排序算法。但是冒泡排序複雜度仍然過高。于是使用快速排序算法解決這個問題。
- 嘗試過使用哈希函數。但是由于哈希函數的制定不過完善，容易出現不同名字出現相同哈希值的情況，這時候就出現了巨大的bug是以對這一部分還需要後續對哈希更深入的了解與學習解決這個問題。
收獲就是複習了算法課學習的内容，加深了快速排序算法的印象，也複習了像queue這類容器的使用，算是對C++基礎内容的鞏固吧。
對隊友的評價
- 優點和值得學習的地方
- 說了就做，完成及時
- 其實編碼能力不錯嘛
- 缺點和需要改進的地方
- 編碼風格，說了前花括号要放到下一行還是沒有換，if/while/for之後一定要要花括号就算是一行的代碼還是沒有遵守。
- 函數名和變量名盡量取得有意義一點吧，n1/n2什麼的……
- 注釋注釋！
- （都是編碼風格太難改了）
PSP
| PSP2.1 | Personal Software Process Stages | 預估耗時（分鐘） | 實際耗時（分鐘） |
|---|---|---|---|
| Planning | 計劃 | 5 | |
| · Estimate | · 估計這個任務需要多少時間 | ||
| Development | 開發 | 205+∞ | 305+∞ |
| · Analysis | · 需求分析 (包括學習新技術) | 60 | |
| · Design Spec | · 生成設計文檔 | 30 | 20 |
| · Design Review | · 設計複審 (和同僚稽核設計文檔) | 10 | |
| · Coding Standard | · 代碼規範 (為目前的開發制定合适的規範) | ||
| · Design | · 具體設計 | 120 | |
| · Coding | · 具體編碼 | +∞ | |
| · Code Review | · 代碼複審 | 45 | |
| · Test | · 測試（自我測試，修改代碼，送出修改） | ||
| Reporting | 報告 | 105 | 140 |
| · Test Report | · 測試報告 | ||
| · Size Measurement | · 計算工作量 | 15 | |
| · Postmortem & Process Improvement Plan | · 事後總結, 并提出過程改進計劃 | 75 | |
| 合計 | 315+∞ | 495+∞ |
學習進度條
| 第 N 周 | 新增代碼（行） | 累計代碼（行） | 學習耗時(小時) | 累計學習耗時（小時） | 重要成長 |
|---|---|---|---|---|---|
| 第 0 周 | 192 | 31 | 複習C++文法、學習VS2017操作、了解回溯 | ||
| 第 1 周 | 7 | 38 | 原型設計、合作探讨、學習需求分析 | ||
| 第 2 周 | 2 | 42 | 團隊作業、NABCD | ||
| 第 3/4 周 | 309 | 501 | 13 | 55 | JSON、檔案操作.國慶 |
| 第 5 周 | 176 | 677 | 12 | 67 | 配和隊友輸入輸出 |