Week#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 (含) 之前
Github
  • remember to use:
  • astyle --style=kr --indent=spaces=4 --indent-switches --suffix=none *.[ch] 
 

關於Drop Cache

  • 之前一直都是用echo "echo 1 > /proc/sys/vm/drop_caches" | sudo sh來清理cache
  • 剛才做quiz#4時突然想到好像echo的數字可以有1、2、3,於是乎都試了一下。驚奇地發現用3所耗費的時間比用1耗費的時間要多出1/4:
echo "echo 3 > /proc/sys/vm/drop_caches" | sudo sh
perf stat -r 100 -e cache-misses,cache-references,L1-dcache-load-misses,L1-dcache-store-misses,L1-dcache-prefetch-misses,L1-icache-load-misses ./recursive
Performance counter stats for './recursive' (100 runs):
       44      cache-misses              #    0.490 % of all cache refs      ( +-  8.59% )
       0.000430226 seconds time elapsed                                          ( +- 33.97% )
       
echo "echo 1 > /proc/sys/vm/drop_caches" | sudo sh
perf stat -r 100 -e cache-misses,cache-references,L1-dcache-load-misses,L1-dcache-store-misses,L1-dcache-prefetch-misses,L1-icache-load-misses ./recursive
 Performance counter stats for './recursive' (100 runs):
      39      cache-misses              #    0.447 % of all cache refs      ( +-  9.38% )
       0.000327662 seconds time elapsed                                          ( +-  3.46% )
  • 於是查了一下:
  • echo 1 > /proc/sys/vm/drop_caches:To free pagecache
  • echo 2 > /proc/sys/vm/drop_caches:To free dentries and inodes
  • echo 3 > /proc/sys/vm/drop_caches:To free pagecache, dentries and inodes
  • 關於上述三個名詞的解釋
  • 所以用3多清除了dentries和inodes,相比1多花費的時間,就是讀當前目錄找到該執行所花的時間
  •  
 

#2 

Question:
Given a sorted character array and a character, return the smallest character that is strictly larger than the search character. If no such character exists, return the smallest character in the array. For example:
Input: ['c', 'f', 'j', 'p', 'v'], 'a'     
Output: 'c'