看過來

初來乍到者,請參閱這篇「緣起」。它是總索引!

2017年6月26日 星期一

[Rust] 單元測試與效能基準測試 (benchmark) :以某遞迴問題為例

這是在 PTT C/C++ 板上面看到的問題 (https://www.ptt.cc/bbs/C_and_CPP/M.1498011747.A.BC3.html),摘錄問題描述如下:

輸入       得到
(n) -> 1 (n-1)(n-1)

例如
(0) -> 0
(1) -> 100
(2) -> 1100100
(3) -> 111001001100100

或者把定義的部份寫成

f(0) = "0"
f(n) = "1" ++ f(n-1) ++ f(n-1)

(假設 ++ 是字串接合運算符號)

自問題描述可以看出這是遞迴定義。怎麼說?因為第 n 個結果是利用第 n - 1 個結果組合而成。

這樣的問題可以用直覺遞迴來解,也可以寫成迴圈來解,也可以用動態規劃來解。

在實作完上述的演算法後,可以利用自動測試來測試演算法的實作是否沒問題。而為了比較這些實作之間在各種場合下的優劣,可以利用效能基準測試(benchmark)來互相比較。

非常幸運的是,Rust 的基本開發工具裡面已經包含了這些工具。單元測試的部份,可以在第二版的 Rust 程式書找到:https://doc.rust-lang.org/book/second-edition/ch11-00-testing.html 。至於只在 nightly 才有的效能基準測試,則在第一版的書裡面 https://doc.rust-lang.org/1.4.0/book/benchmark-tests.html

千秋所做的程式碼在 https://gitlab.com/chiakikame/rust-recurse-algorithm-fun 可以找到。因為千秋也在學習中,歡迎諸位大德不吝指教以及討論。