---
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

可讀性增加

* 例子

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迴圈中

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)

COLOR_OFF=$'\033[0m'
COLOR_GREEN=$'\e[0;32m'
COLOR_RED=$'\e[0;31m'

echo -e "${COLOR_RED}Hello${COLOR_OFF}"

> 更改顏色最後都要還原(`COLOR_OFF`)

#### array & 變數

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)

        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
* 固定字串長度

* 字串的長度(len)要行數(line)夠大才有影響力

* 固定字串行數

* 字串的行數(line)是影響時間的**主要因素**。

* 整體來說，在輸入(Input)及輸出(Output)的部分佔整體的比例較大
* 可以發現很明顯的趨勢: 隨著行數的增加，整體的時間皆會成長
* 可以發現輸入(紅色)、輸出(黃色)在`(100, 100000)`相較於`(100, 500000)`成長了5倍，相同的情況也可在`(500, 100000), (500, 500000)`以及`(1000, 100000), (1000, 500000)`觀察到。

---

### Iterator
* 固定字串長度
* 在行數(line)很大時字串長度(len)增長500，時間增加約6~7秒

* 固定字串行數
* 行數(line)至100000以上，才有比較明顯的成長

* input隨著行數(line)在整體來說是比其他兩個部分還要高許多，而sorting的部分行數(line)、長度(len)多或是少，似乎沒有明顯的起伏，output的部分起伏稍微多一些。

* 這邊觀察到`(100,500000), (500,500000), (1000,500000)`，這三個部分來說，雖然字串長度差距只有約1000。input卻明顯多了差距到10秒，但output可能只有3秒不到，而sorting完全沒什麼動靜

### Simple

* 固定字串長度
* 字串長度(len)增長500，時間增加約6~7秒

* 固定字串行數
* 行數(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

* input_line.png

#### sort

* `std::sort()`的時間複雜度為$O(nlogn)$，是使用quick-sort實作

* 三者時間複雜度皆為$O(nlogn)$，最差為$O(m*nlogn)$。

* 很明顯sorting時間都沒有超過兩秒，時間算是蠻快的，而alternative時作為字元陣列，simple與iterator是用string-vector實作，圖形上來看幾乎是重疊的

* sort_len.png
* sort_line.png

#### output

* 時間複雜度三者為$O(MN)$

* 輸出時間明顯可看出alternative花的時間較Iterator、Simple多。因為iterator、simple輸出的使用string-vector做輸出，而alternative是用char-vector，但alternative要花較多的時間才能輸出完成

* outlen_len.png
* outlen_line.png

#### total

* 整體時間Alternative時間最久，從輸入輸出來看，很明顯是因為字元的vector速度拖慢了效率，iterator與simple使用getline實作，時間就快了許多
* 從`(100,500000)`來看，alternative的時間約是simple與iterator的兩倍左右，而在`(1000,500000)`，alternative的時間是iterator跟simple的三倍左右

* total_len.png

* total_line.png