開發紀錄 HW3

作業要求

  • Question #2, #3, #4, #5, #6, #27
  • 在 GitHub 上 fork quiz,然後逐一修改每個目錄裡面的檔案
  • 對於 Question #2, #3, … #6 都需要實做遞迴和非遞迴的版本
  • 要一併準備測試資料
  • 除了修改程式,也要編輯 Hackpad 下方「+作業區」,增添開發紀錄和 GitHub 連結
  • 額外要求觀賞電影《進擊的鼓手》,思考這 4 週以來,課程給你的衝擊 (若你沒衝擊的話,可以退選了),在自己的 Hackpad 紀錄心得,特別是對於追求卓越這件事
  • 應該要有完整的測試程式,並測試各項邊界狀況
  • 執行時間分析
  • 記憶體需求分析
  • cache miss 分析
  • 時間複雜度分析
  • 善用 assert
  • 提供遞迴與非遞迴的版本
 

Question 2

想法
  • 用遞迴或是迴圈的方式,逐一比較大小
 
Recursive
char smallest_character(char str[], char c, int ptr)
{
    if(str[ptr]=='\0')        return str[0];
    if(str[ptr]>c) return str[ptr];
    else {
        return smallest_character(str,c,ptr+1);
    }
}
Iterative
char smallest_character(char str[], char c)
{
    int i=0;
    while(str[i]!='\0') {
        if(str[i]>c)
            return str[i];
        i++;
    }
    return str[0];
}
 
分析
Performance counter stats for './recursive' (5 runs):
 
             2,083      cache-misses              #   17.545 % of all cache refs      ( +- 27.91% )
            11,874      cache-references                                              ( +-  2.27% )
           501,946      instructions              #    0.73  insns per cycle          ( +-  0.66% )
           687,433      cycles                                                        ( +-  3.96% )