owned this note
owned this note
Published
Linked with GitHub
---
title: 1072STL HW01 - Writing a Test Plan for the First STL Program
---
# 1072STL HW01 - Writing a Test Plan for the First STL Program
###### tags: `泛型` `C++` `作業` `2019`
[toc]
## 組員
* 406262163 黃品翰
* 406262515 鍾秉桓
* [github repo](https://github.com/roy4801/107_Gernic_Programming)
---
## 實作
本次實作了兩個header file:`rand.h`,`calcTime.h`
* 技術
* 編譯使用 `make`, `shell script`
* 繪圖分析 `gnuplot`
```
+--------+ +---------+ +-------------+
| gen.sh +--------->+ plot.sh +--------->+ gen_xlsx.py |
+-+------+ +-----+---+ +----+--------+
| | |
| +----------+ +----v----+ |
+--->+ gen_test | | gnuplot | | +--------+
| +----+-----+ +---------+ +--->+ xlsx |
| | +------------+ +--------+
| v | |
| +----+----+ +-----+-----+ +--v-+
+--->+ main +-->+result_data| |pngs|
+---------+ +-----------+ +----+
```
* 流程
* `gen.sh`編譯並執行 `gen_test` 產生測資 導到 `main` 中產生結果資料
* `plot.sh` 使用結果資料使用`gnuplot`依據`*.gp`畫出結果圖
* `gen_xlsx.py` 產生excel
* 發展
* 可以使用`CI/CD`來達到一`commit`就自動run script,產生結果
* 現在必須手動執行
### 細節
* [`rand.h`](https://github.com/roy4801/107_Gernic_Programming/blob/master/samplecode/rand.h)隨機字串生成(生測資用)
* `init_rand()`
* `srand` 初始化`random seed`
* `rand_int()`
* 給定範圍,回傳隨機產生數字
* `rand_str()`
* 給定長度,回傳隨機字串
* `gen_str_to_file()`
* 產生測資檔案
* [`calcTime.h`](https://github.com/roy4801/107_Gernic_Programming/blob/master/samplecode/calcTime.h)計算時間
* `_timeStart()`
* 計時開始
* `_timeEnd()`
* 計時結束
* `_getTick()`
* 取得每個tick
* `_getSec()`
* 取得秒數
* `gen_test`給定參數就能生測資的程式
* 利用剛才的`<rand.h>`寫入`testcase.txt`
---
### 使用shell-script自動化
* Compile`main.cpp`, `gen_test.cpp`
* 清空輸出的檔案
* 利用for迴圈,將測資寫入`gnu.txt`,準備生成給`gnuplot`
#### function
可讀性增加
* 例子
```bash=
function nl_gnu()
{
echo "Testing len : ${M[$len]} line:${N[$line]}"
echo -n $alpht | awk '{printf("%c",$1)}' >> gnu.txt
echo -n " " >> gnu.txt
((alpht++))
./gen_test ${M[$len]} ${N[$line]}
./main < testcase.txt
echo >> gnu.txt
info "Completed."
# echo >> gnu.txt
}
```
* 放到for迴圈中
```bash=
for line in `seq 0 5`;
do
for len in 0 1 2
do
# gnu-testcase
nl_gnu;
done
done
```
#### ANSI escape codes
終端的文字能有顏色變化
[顏色大全](https://stackoverflow.com/questions/5947742/how-to-change-the-output-color-of-echo-in-linux)
```bash=
COLOR_OFF=$'\033[0m'
COLOR_GREEN=$'\e[0;32m'
COLOR_RED=$'\e[0;31m'
echo -e "${COLOR_RED}Hello${COLOR_OFF}"
```
> 更改顏色最後都要還原(`COLOR_OFF`)
#### array & 變數
```bash=
N=("1000" "5000" "10000" "50000" "100000" "500000")
M=("100", "500", "1000")
alpht=65
```
---
### gnuplot
很棒的畫圖程式
詳見這篇↓
* https://hackmd.io/rnqgmxmNSNWKgzf718RKGw
---
### makefile
短短語句,批次執行
`make`用於編譯程式的工具,使用者只要寫一個(或多個)makefile,便可用`make`依照`makefile`所訂出之相依關係去執行。
> `make`不只可以拿來編譯,只要是有相依關係的事,它都可以執行
> (沒有相依關係也可,但殺雞焉用牛刀)
:::danger
WINDOWS 沒有`make`,參考解決方案:
1. 安裝`gnu-win32`,有make.exe
[參考](https://stackoverflow.com/questions/2532234/how-to-run-a-makefile-in-windows)
2. 使用msys2安裝
`pacman -sS make`
:::
* 舉例
* 起因 : 每次上傳`github`都要清除測資檔案或其他檔案
* [makefile:Line 25](https://github.com/roy4801/107_Gernic_Programming/blob/master/samplecode/makefile)
```bash=25
clean:
rm -f Alternative/main Alternative/gen_test
rm -f Iterator/main Iterator/gen_test
rm -f Simple/main Simple/gen_test
rm -f Iterator/*.exe Alternative/*.exe Simple/*.exe
rm -f Iterator/*.txt Alternative/*.txt Simple/*.txt
rm -f result/Iterator/*.png result/Alternative/*.png result/Simple/*.png
rm -f result/Iterator/*.txt result/Alternative/*.txt result/Simple/*.txt
```
* 利用 : `make <Name>`
* `make clean`,清理所有不想上傳的檔案
---
### python with xlsx
https://openpyxl.readthedocs.io/en/latest/
---
## 圖形分析
### Alternative
* 固定字串長度
![](https://i.imgur.com/g4qqaYx.png)
* 字串的長度(len)要行數(line)夠大才有影響力
* 固定字串行數
![](https://i.imgur.com/ZuSugMr.png)
* 字串的行數(line)是影響時間的**主要因素**。
* 整體來說,在輸入(Input)及輸出(Output)的部分佔整體的比例較大
* 可以發現很明顯的趨勢: 隨著行數的增加,整體的時間皆會成長
* 可以發現輸入(紅色)、輸出(黃色)在`(100, 100000)`相較於`(100, 500000)`成長了5倍,相同的情況也可在`(500, 100000), (500, 500000)`以及`(1000, 100000), (1000, 500000)`觀察到。
---
### Iterator
* 固定字串長度
![](https://i.imgur.com/6O2LvgO.png)
* 在行數(line)很大時字串長度(len)增長500,時間增加約6~7秒
* 固定字串行數
![](https://i.imgur.com/lGexw6v.png)
* 行數(line)至100000以上,才有比較明顯的成長
* input隨著行數(line)在整體來說是比其他兩個部分還要高許多,而sorting的部分行數(line)、長度(len)多或是少,似乎沒有明顯的起伏,output的部分起伏稍微多一些。
* 這邊觀察到`(100,500000), (500,500000), (1000,500000)`,這三個部分來說,雖然字串長度差距只有約1000。input卻明顯多了差距到10秒,但output可能只有3秒不到,而sorting完全沒什麼動靜
### Simple
* 固定字串長度
![](https://i.imgur.com/apJvocd.png)
* 字串長度(len)增長500,時間增加約6~7秒
* 固定字串行數
![](https://i.imgur.com/vlI1avw.png)
* 行數(line)至100000以上,才有比較明顯的成長
* 基本上與iterator是差不多的,因為在實作上面也是類似的,輸入只是一個差在只記頭尾的iterator,一個是使用getline,輸出都是用copy到output_stream的方式,因此圖形幾乎與iterator相同
---
### 三種方法比較
#### input
* 時間複雜度三者為$O(MN)$
* Alternative是使用`getchar()的方式`,一個一個字元做讀取,過程中不斷地將字元push_back至vector裡面,會不斷一直改變vector大小,花費的時間才會相較其他兩個方式高
* Iterator、Simple是getline抓取字串,將字串頭尾存入vector中,因此,時間花得比較少
* input_len.png
![](https://i.imgur.com/PNvCjJN.png)
* input_line.png
![](https://i.imgur.com/ykZl6vk.png)
#### sort
* `std::sort()`的時間複雜度為$O(nlogn)$,是使用quick-sort實作
* 三者時間複雜度皆為$O(nlogn)$,最差為$O(m*nlogn)$。
* 很明顯sorting時間都沒有超過兩秒,時間算是蠻快的,而alternative時作為字元陣列,simple與iterator是用string-vector實作,圖形上來看幾乎是重疊的
* sort_len.png
![](https://i.imgur.com/UeqIT8u.png)
* sort_line.png
![](https://i.imgur.com/NWvRgAl.png)
#### output
* 時間複雜度三者為$O(MN)$
* 輸出時間明顯可看出alternative花的時間較Iterator、Simple多。因為iterator、simple輸出的使用string-vector做輸出,而alternative是用char-vector,但alternative要花較多的時間才能輸出完成
* outlen_len.png
![](https://i.imgur.com/GVNk5Zm.png)
* outlen_line.png
![](https://i.imgur.com/CauNROa.png)
#### total
* 整體時間Alternative時間最久,從輸入輸出來看,很明顯是因為字元的vector速度拖慢了效率,iterator與simple使用getline實作,時間就快了許多
* 從`(100,500000)`來看,alternative的時間約是simple與iterator的兩倍左右,而在`(1000,500000)`,alternative的時間是iterator跟simple的三倍左右
* total_len.png
![](https://i.imgur.com/S3CeAPz.png)
* total_line.png
![](https://i.imgur.com/XzhIRql.png)