第二次作業——個人項目實戰
标簽（空格分隔）： 軟工實踐
github的傳送門:work2、work2-附加題2
題目的傳送門
上次作業的評分總結
一、解題思路
看到題目的一反應就是:在不考慮效率的前提下,這題搜尋是一定可以做的。
但是有要求:
25分為正确性評分，正确性測試中輸入範圍限制在 1-1000，要求程式在 60 s 内給出結果，逾時則認定運作結果無效。
10分為性能評分，性能測試中輸入範圍限制在 10000-1000000，沒有時間的最小要求限制。
是以普通的搜尋應該是不行的,但是思考一下,如果使用回朔法(暴力+剪枝)效果怎麼樣呢？因為回溯的時間複雜度比較玄學,我不敢下定論,
思考了一會後,我覺得,數獨應該是一個比較成熟的項目,應該可以比較容易的找到與其生成方法的相關資料。
百度了之後,發現提到的數獨生成算法,大部分都是用類似'換行換列'之類的思想:先預處理生成或者直接手動輸入一個數獨,然後進行交換,這樣子就可以生成新的數獨.
好像很有道理的樣子,是以我決定,搜尋和上面提到的這個算法都實作一下,比比效率和實作的難易程度(這個時候我把自己坑到了,我一直以為數獨是同行同列不能重複數字,沒有注意到同九宮格也不能重複數字,也沒有仔細看題,是以一開始的思路也是錯的,但是誤打誤撞還真分析了出了點東西)。
為了展現随機性,我使用随機排列函數random_shuffle來随機第一行的數字1~9的填放方法。
那麼問題來了,這樣子的随機對搜尋來說,搜尋的起點變了,但搜尋的終點(如果需要全部搜尋完畢的話)是不會變的,是以會造成搜尋到的方法數變小,那麼會不會出現比作業需求的方案數少的情況呢?
從數獨-- 一個高效率生成數獨的算法中我得知,數獨方案數約有6.67×10的21次方種,是以,第一排的随機,即使最壞情況下:生成的第一排的排列為1~9的逆序:
9 8 7 6 5 4 3 2 1
但即使如此,方案數最壞情況下是:上述的數字除以9的階乘,回溯能查詢到的方案數依然遠大于于題目的需求。
而'換行換列'的方法,更不會局限于此。
搜尋的方法很簡單:把9*9的方格用081來标号,暴力的從1081依次填入19,(08事先填好了),每填一個數字前先判斷一下填入目前的數字是否滿足填入規則:不能與已經填入的格子的數字産生沖突,如果可行,就選擇下一個格子繼續填,不行就放棄這個方案,很裸的暴力,思考量很小。
關于'換行換列':由于本人的不認真查閱資料和閱讀,我隻看見了這一句話沒認真思考便動手碰起了鍵盤
于是我産生了一個看上去比較WS的算法，思路如下，我先寫一個數獨出來，用二維數組A表示，然後再生成一個亂序的1-9一維數組，用一維數組b表示。
--from 數獨-- 一個高效率生成數獨的算法
我是想先生成一個數獨,再用用了全排列函數,想通過全排列函數來生成新的排列來達到生成新數獨的目的。
(當然...後面發現我這樣子想實際上是錯的= =...）
二、設計實作
1、函數設計
設想用一個函數solve()來全局的處理,期間調用一個init()函數來初始化所有需要用到的變量,然後通過dfs()函數來進行回溯和搜尋操作,并且在dfs()函數中來輸出方案。
形式如下:
void solve()
{
init();
.......
dfs(10); //回溯,暴搜+剪枝
}
dfs()函數需要完成三個功能:遞歸、剪枝、方案的輸出。
其中剪枝又有兩種:無效方案的去除以及搜尋了足夠多(滿足輸入需求)的方案後的剪枝。
void dfs(int t)
{
if (flag) return;
if (t>81)
{
....//輸出方案
if 輸出了n個方案 flag = true;
return;
}
rep(i, 1, 10) //目前選擇可以放的數字
{
if 不滿足條件 continue;
.....//遞歸
}
}
2、類設計
類的設計我一開始沒有考慮到,因為我的函數關系相對比較簡單,直接寫即可。
後來加上了一個 generator類,把上述函數封裝了起來,然後給solve()函數傳遞一個參數n,表示方案數,這樣子就可以不受main的輸入方式(XX.exe -c num or 直接運作exe輸入)的幹擾。
三、代碼說明
1.随機排列的實作
題目的輸出要求是:
随機生成N個不重複的已解答完畢的數獨棋盤.
随機如何展現?(我覺得實際上肯定沒有随機這個測試點),輸入同一個N如何讓輸出的答案不完全相同呢?單純的搜尋是做不到的。做法就是用随機函數來實作。但是C++的STL有封裝了類似的功能,就是用
random_shuffle(begin(),end())
來将其中的元素随機打亂順序。
//初始化1~9
rep(i, 0, 10) ways[1][i] = i + '0';
//尾号48，48%9+1 = 4,第一個位置要是4
swap(ways[1][1], ways[1][4]);
//實作随機全排列,随機的關鍵
random_shuffle(ways[1] + 2, ways[1] + 10);
2.搜尋過程
搜尋的需要三組标記:行标記、列标記、九宮格标記,表示某行、列..哪些數字已經使用過了。
int x = (t - 1) / 9 + 1; //目前搜尋到哪個格子
int y = (t - 1) % 9 + 1;
int p = belong[x][y]; //目前格子屬于哪一個九宮格
rep(i, 1, 10) //目前選擇可以放的數字
{
//目前行、列、九宮格中使用過
if (row[x][i] || col[y][i] || vis[p][i]) continue;
//标記
row[x][i] = col[y][i] = vis[p][i] = true;
ways[x][y] = i + '0';
//下一個格子
dfs(t + 1);
//去标記
row[x][i] = col[y][i] = vis[p][i] = false;
}
3.輸出方式
經過優化後的輸出方式,有一點巧妙,用puts()輸出,用字元串表示方案,一個方案一次輸出,可以快很多
預處理部分
//預處理出輸出格式
cnt = 0;
rep(i, 1, 10)
{
//一個數字,一個空格
rep(i, 1, 9) put[cnt++] = 'X', put[cnt++] = ' ';
//行末無空格
put[cnt++] = 'X'; put[cnt++] = '\n';
}
put[--cnt] = '\0';//最後一行後無'\n';
實際輸出部分
if (ans++) puts(""); //兩個方案之間有空格
cnt = 0; //初始化
rep(i, 1, 10) rep(j, 1, 10) //for循環周遊每個格子
{
//兩個數字之間的空格還是換行已經預處理過了
put[cnt++] = ways[i][j], ++cnt;
}
puts(put); //輸出
四、測試運作
測試資料主要從極端資料考慮:錯誤輸入、0處理、極限資料三個角度入手,并且自己手寫了一個check函數要進行正确性的驗證
check函數主要實作如下:
bool check()
{
bool col[10][10] = {false};
bool row[10][10] = {false};
bool vis[10][10] = {false};
string s = "";
rep(i,1,10) rep(j,1,10)
{
int num = a[i][j];
s += (char)(num+'0');
int t = belong[i][j];
if(vis[t][num]||col[i][num]||row[j][num]) return false;
vis[t][num] = col[i][num] = row[j][num] = true;
}
if(mp[s]) return false; //是不是輸入有重複
mp[s]++;
return true;
}
N = 1
N = abc
N = 1000000,注意檔案輸出大小
N = 0,輸出為空檔案
改進的過程以及性能分析
初始版本的分析
一開始的時候,我的輸出是這樣子的:
if(t>81)//輸出方案
{
if(ans) puts(""); //兩個方案之間有空格
++ans;
rep(i,1,10) rep(j,1,10)
printf("%d%c",ways[i][j]," \n"[j==9]); //兩個數字之間有空格
if(ans>=n) flag = true;
return ;
}
粗略自己先計算一下:
10W跑了大概20+s,難道是回溯太慢了?
寫一下'換行換列'的方法:
void f(int (*a)[10])
{
int b[10] = {0,1,2,3,4,5,6,7,8,9};
do
{
if(n<=0)break;
if(flag) puts("");
else flag = true;
rep(i,1,10) rep(j,1,10)
printf("%d%c",a[i][b[j]]," \n"[j==9]);
n--;
}while(next_permutation(b+1,b+10));
}
再跑一下:
exm???還是20+s?這個就很不科學了,這個的複雜度應該很低才對啊？難道是全排列函數next_permutation跑得很慢？？？
于是我寫了一個測試：
int a[] = {0,1,2,3,4,5,6,7,8,9};
int n;
cin >> n;
while(n--)
{
rep(i,1,10) printf("%d ",a[i]);printf("\n");
next_permutation(a+1,a+10);
}
測試如下:
10W次的全排列居然要3、4s?這個就特别不科學了.....這個時候,我大概知道問題出在哪裡了...
突然就回憶起了今年多校10的那道毒瘤題= =....1000W級别的輸入,6秒的限制,卡fread才能過....
然後..我打開了vs的性能分析并且調試,這次改用N = 100W的輸入
雖然我第一次弄這個性能分析,看的不是很懂,但是我還是很容易就看出來了,這幾張圖都指出了一個很明顯的一點:printf()函數以及其的調用占了很大的時間比。
結合一下耗時,好了,該甩鍋的都甩鍋把,算法實際上這題占的耗時比例并不高,最大的耗時來源是在輸出方式上。
改進一
于是乎,我就先用putchar()進行了二次嘗試.輸出由int轉換為char,并且用putchar()。
if(ans) puts(""); //兩個方案之間有空格
++ans;
rep(i,1,10)
{
rep(j,1,9)
putchar(ways[i][j]),putchar(' '); //兩個數字之間有空格
putchar(ways[i][9]);puts("");
}
直接上100W,進行粗略估計
效果顯著啊
改進二
然後接下來的嘗試是用puts()一次性輸出一個方案,即最終版本采用了這個方法。
再次直接上100W
果然,更加進一步的進行了優化
用vs性能分析檢視
輸出隻占了5.8%,dfs()本身成了耗時最大的函數。
改進三
模拟緩沖區,用puts()一次性輸出多個方案(附加題中使用)。
答案檢查以及修改
單元測試
将自己寫的check函數封裝成check類,寫入單元測試的項目中去,經過某犇犇的指點,得知了可以用檔案的輸入輸出的方法,先将自己的generator類輸出的答案輸出到檔案中去,然後再關閉輸出通道,同時打開該檔案的讀入,這樣子就可以實作check。
check主要代碼如下:
bool CHECK::check(int k)
{
init();
int cas = 0;
bool f = true;
while (~scanf("%d",&a[1][1]))
{
++cas;
rep(i, 1, 10)
{
if (i == 1) rep(j, 2, 10) scanf("%d", &a[i][j]);
else rep(j, 1, 10) scanf("%d", &a[i][j]);
}
//judge用于檢測生成的數獨是不是正确,前面有帖寫過代碼
if (!judge()) f = false;
}
if (cas != k) f = false; //是不是檔案中産生了k個數獨
return f;
}
單元測試代碼:
TEST_METHOD(TestMethod2)
{
// TODO: 在此輸入測試代碼
generator g;
freopen("sudoku.txt", "w", stdout);//讀出檔案
g.solve(10000); //生成數獨
fclose(stdout); //關閉讀出檔案
freopen("sudoku.txt", "r", stdin);//讀入檔案
CHECK h;
Assert::IsTrue(h.check(10000));
}
進行測試的資料為:0、100、1000、10000、1000000,運作測試結果如下:
ZeroTest 未通過?查了一下,發現是因為,n = 0時,沒有東西輸出,這樣子sudoku.txt就相當于沒有重新整理,保留的是上一次運作的測試的輸出結果。
是以隻需加一句:
if(n==0) puts("");
代碼覆寫率檢查
vs 2015 企業版直接使用代碼覆寫率檢查
發現generator類中有未覆寫到的段,點選檢查
發現是重載的構造函數未使用到,新增測試點:
generator g(5);
g.check(100);
結果如下:
注:judge中未覆寫的片段為傳回值為false時候的片段。
附加題二
随機生成N個 不重複 的 有唯一解 的數獨棋盤。挖空處用數字0表示，每個數獨棋盤中至少要有 30 個以上的0。輸出格式見下輸出示例，輸出需要到檔案sudoku.txt中。
解題思路**
初始版本
在第一題的基礎上,每生成一個數獨,就随機挖掉35個空,生成5個滿足條件挖空的數獨,并且每挖一次空,都進行check(檢視挖掉一個空後,對該數獨進行填空,檢視是不是有唯一解)。
性能分析如下:
100W資料耗時大約:39s
改進版本
對初始版本進行性能分析後,發現,GetPoint()函數占用率十分的高,這個函數的作用是:**對目前數獨再挖一個空,并且滿足填空後數獨是唯一解**
在初始版本的基礎上,增加了随機函數的随機性功能,從原來的每挖一個坑就進行一個check,改成先預随機挖掉30個空,然後進行check,如果不滿足條件,再重新生成30個空,之後每挖一個空,進行一次check.
100W資料大約耗時17s
最終版本
做完第二個版本後,總是在想，能不能跑的更快一點呢?突然就來了靈感,想到:如果一個數獨挖了40個空是滿足唯一解的,那麼從中任意選31個,那麼新的數獨也是唯一解的,然後算一下C(40,31) = 273438880,大于100W,是以,我的做法是:
先用改進版的方法生成一個挖了40個空的數獨,然後從用回溯的方法,選擇挖空數大于31的數獨。
100W資料大約耗時2s
遇到的困難及解決方法
沒有及時的記錄,是以記得不全。
1、vs使用生疏,代碼分析規則不了解
問題描述
vs已經很久沒有使用了,先用dev C++ 寫完初稿後,一開始不知道如何在vs上建立項目,如何使用那些性能分析之類的。
dev C++的代碼弄到vs上不能直接運作,如freopen會報錯。
做過哪些嘗試
找部落格查詢、找其他同學互相幫助一起解決。
是否解決
解決了,通過查詢部落格可以解決大部分問題.和其他同學探讨也解決了一些
有何收獲
vs用更加熟悉了。
2、代碼覆寫率 不知道如何下手
vs 專業版沒有代碼覆寫率的功能,仔細閱讀了作業要求後發現,居然,你們居然偷偷的在代碼覆寫率前面加了插件兩個字。
然後...我是把這個留到了最後來做的..離deadline only 2 天。
1、安裝插件 opencppcoverage,然後發現安裝這個插件後還要安裝Jenkins,然後。。Jenkins..好麻煩啊= =....我的8080端口已經有其他東西了..然後..感覺在2天之内是不可能完成的任務。
2、安裝vs 2015 企業版,在舍棄了1的方案後,我決定解除安裝了我的vs 專業版.因為vs解除安裝是一件很麻煩的事情,很可能失敗,但是我居然安裝成功了....
解決了。
對代碼覆寫率功能有了更深入的了解.也知道了一些開源的插件。
執行力 、 泛泛而談 的了解
執行力我覺得是和個人的養成習慣有關,有的人有類似拖延症的毛病,做事情永遠是能推遲就推遲。這就導緻了,在deadline臨界點,是趕工or缺交。
從某種意義上,對一件事情的重視(重要)程度,也可以在個人的執行力上展現。
也。
我習慣性的把一個大的問題分成很多個小問題,分散成很多很多個時間片去做。
其實說到底,都是意志力的問題。關鍵在于自己想不想做,願不願意花時間去做而已。
就比如..我實際上是對于作業是不拒絕的,但是我不喜歡寫部落格之類的.我喜歡慢慢玩,慢慢做,東西一點一點的來做,是以經常都是理論上我作業做完了,但是由于部落格之類偏理論性的東西不愛做,實際上我做一件事情(完全做完)依然會拖延到很遲。
泛泛而談,我也會這樣子做,我覺得泛泛而談有時候挺有好處的,給自己靈活變動的時間,誰都難免以外的時候突然到來,比如:今天下午我要和隊友訓練acm5小時,突然來了一個通知,今天下午補課,是以呢？為什麼我訂的目标不是:盡可能的用剩下空閑的時間就來訓練。,或者說,自己發現有了更好的計劃,覺得新的時間調整更加的合理，既然如此,為什麼不給自己事先就預留一些靈活的使用時間,想做什麼工作就做什麼。
還有就是,自己本身做具體規劃的時間的比較少,本身就模棱兩可不知道如何規劃比較好,特别是我這種有時候會較真的人,說着做2小時,突然發現某個奇怪的問題,你可能就載進去做别人看起來沒有意義的事情,這樣子就讓時間規劃變得沒有意義,但是我卻會覺得樂在其中.
關于經驗方面的泛泛而談,我也就不太了解,可能是出于謙虛的說話,或者本身沒有什麼成績可說？一般人在介紹自己如果不是給專業人人士說的話,說一堆具體的還不如一句'經驗豐富'。
不過,當然,不能全部都是泛泛而談,因為泛泛而談很多時候會讓你缺乏執行力,結合了自身情況,我發現自己在晚自習的時候經常容易走神,為了盡可能的減少這個情況,我給自己定下了目标:一小時隻能動一次手機且不能超過15min、每天晚上堅持晚自習，等等,制定具體的目标可以給人一種'緊張'或者說是'重視'的效果,讓自己更加有計劃,不會處于'茫然'的狀态,很多人可能因為沒有具體的計劃就白白浪費了一天。
| PSP2.1 | Personal Software Process Stages | 預估耗時（分鐘） | 實際耗時（分鐘） |
|---|---|---|---|
| Planning | 計劃 | 5 | |
| · Estimate | · 估計這個任務需要多少時間 | ||
| Development | 開發 | 890 | 1020 |
| · Analysis | · 需求分析 (包括學習新技術) | 180 | 420 |
| · Design Spec | · 生成設計文檔 | 120 | 90 |
| · Design Review | · 設計複審 (和同僚稽核設計文檔) | 60 | 20 |
| · Coding Standard | · 代碼規範 (為目前的開發制定合适的規範) | 30 | |
| · Design | · 具體設計 | 10 | |
| · Coding | · 具體編碼 | 240 | |
| · Code Review | · 代碼複審 | ||
| · Test | · 測試（自我測試，修改代碼，送出修改） | 360 | |
| Reporting | 報告 | 575 | |
| · Test Report | · 測試報告 | ||
| · Size Measurement | · 計算工作量 | ||
| · Postmortem & Process Improvement Plan | · 事後總結, 并提出過程改進計劃 | 480 | |
| 合計 | 1725 | 1600 |
|第N周 | 新增代碼 (行)|累計代碼(行)|本周學習耗時(小時)|累計學習耗時(小時)|重要成長|
|-------------------------|----------------|-----------------------------------------|------------------|------------------|
|0 | 1000 | 1000| 40 | 40 |vs的使用,項目建立、性能分析等|
|N | | | | |