Homework 3
 
實做 Week #2 程式題目,解釋其運作原理 (至少 3 題,限定 C99 或以上的規格)
Question #2, #3, #4, #5, #6, #27
 

Question #2

Recursive
char smallest_character(char str[], char c, int l)
{
    if(c < str[l-1])
        return smallest_character_r(str,c,l-1);
    if(l == strlen(str) || l == 0)
         return str[0];
    return str[l];
}
Hint: 這個程式有哪些邊界條件需要檢查?
 
執行perf計算時間及cache miss
execution time of smallest_character() : 0.000007 sec
 
Performance counter stats for './recursive' (5 runs):
2,267            cache-misses              #   18.547 % of all cache refs      ( +- 47.52% )
12,221           cache-references                                              ( +-  2.54% )
10,804           L1-dcache-load-misses                                         ( +-  3.39% )
4,800            L1-dcache-store-misses                                        ( +-  1.16% )
<not counted>    L1-dcache-prefetch-misses
<not counted>    L1-icache-load-misses    
 
0.002304504 seconds time elapsed                                               ( +- 79.43% )
 
Iterative
char smallest_character(char str[], char c)
{
    for(int i=0; i<strlen(str); i++)
    {
        if(c < str[i])
            return str[i];
    }
    return str[0];
}
 
執行perf計算時間及cache miss
execution time of smallest_character() : 0.000022 sec
 
 Performance counter stats for './iterative' (5 runs):
1,238            cache-misses              #    9.828 % of all cache refs      ( +- 63.14% )
12,597           cache-references                                              ( +-  1.96% )
11,107           L1-dcache-load-misses                                         ( +-  2.11% )
4,910            L1-dcache-store-misses                                        ( +-  1.33% )
<not counted>    L1-dcache-prefetch-misses