HW3
wiki:2015q3 Homework #3
作業區+共筆
 

作業要求

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

ASSERT

assert() 原型定義在 assert.h,接受一個表達式作為參數,當表達式為 false 時,會向 stderr 送出錯誤訊息,並調用 abort() 中止程式。
 

Q2

  • Given a sorted character array and a character, return the smallest character that is strictly larger than the search character.
基本解法:從字串頭搜尋到字串尾,時間複雜度O(n)
Performance counter stats for './iterative' (10 runs):
           687,731      cycles                     ( +-  1.99% )
           484,077      instructions              #    0.70  insns per cycle          ( +-  0.64% )
             1,158      cache-misses                                                  ( +- 39.27% )
 
  •        0.002492723 seconds time elapsed                                          ( +- 43.97% )
Performance counter stats for './recursive' (10 runs):
 
           667,642      cycles                     ( +-  2.78% )
           477,136      instructions              #    0.71  insns per cycle          ( +-  0.57% )
               791      cache-misses                                                  ( +- 37.40% )
 
  •        0.000749755 seconds time elapsed                                          ( +-  8.75% )
先看到上面的結果,遞迴版本的cycles、cache-misses都較少於iterative版本
因為題目的給定的是排序過的array,所以可以使用二分搜尋法的方式去找
 
參考:
+永勁的bitwise操作
  • 用每個位元來表示每個英文字母有無出現
  • Builtin GCC Functions: