Hw3 開發紀錄
 
 
 

Q2

 
這個題目相較其他題是比較容易實做的。function 的  prototype 是:
 
char smallest_char( char str[], char c); 陣列對於 C 語言來說,其實是一個連續的記憶體。由於 C string 有 '\0' 可以標記出字串的結尾。因此不用傳入大小就可以找出停止處。但是對於現在的 prototype 形式,他是傳入 character array, 但是卻沒有輸入 size,因此不知道結尾。在不更變 prototype 的情況下,我預設傳入的 character array 其實是一個 C string。
 
在這題實作了 iterative 以及 recursive 兩種版本。一開始認為 character 的長度不超過 26。(因為在 sorted list,英文字母不重複的情況下)但是,經由 Question #2 的最後一個 input 範例可以看到是有重複字母出現的情形。不會出現  ['c', 'c', 'k']。因此,我認為必須要處理重複字元的情況,就像是把 "hello world" 做排序之後,會有重複的字元。
 
iterative
 perf stat -r 100 -e cache-misses,cache-references,instructions,cycles ./iterative  
 Performance counter stats for './iterative' (100 runs):
 
             1,857      cache-misses              #    8.484 % of all cache refs      ( +-  9.50% )
            21,890      cache-references                                              ( +-  0.82% )
           443,555      instructions              #    0.86  insns per cycle          ( +-  0.19% )
           513,767      cycles                     ( +-  1.43% )
 
       0.000488248 seconds time elapsed                                          ( +-  2.96% )
 
 
 
recursive
perf stat -r 100 -e cache-misses,cache-references,instructions,cycles ./recursive  
 Performance counter stats for './recursive' (100 runs):
 
        Performance counter stats for './recursive' (100 runs):
 
             1,888      cache-misses              #    8.789 % of all cache refs      ( +-  9.04% )
            21,483      cache-references                                              ( +-  0.56% )
           443,719      instructions              #    0.87  insns per cycle          ( +-  0.17% )
           511,969      cycles                     ( +-  2.11% )
 
       0.000517909 seconds time elapsed                                          ( +-  3.01% )
 
 
unit test
除了實作程式之外,我設計了一個 function 以及 test case 來檢測這兩個程式是不是符合要求。
 
分別使用兩種 string:
  • char str[] = "cfjpv";
  • char str2[] = "aabceeffffggwzzz";
 
unit_test function 的第一個參數是要被測試的 function,  因此使用 function pointer 作為傳入參數。因為 iterative, recursive 兩種處理函式的介面都相同,只有內部實做不一樣,於是可以這樣使用。第二個參數是預期的結果,第三個參數以及第四個參數是測試 function 的參數。在這部份,有些人可能會設計為 void * ,讓它指向任意型別,要使用的時候,在利用 casting 轉型後取出要的資訊即可,像是 pthread : int pthread_create(pthread_t *thread, const pthread_attr_t *attr,
                          void *(*start_routine) (void *), void *arg);