Homework 3

Q2: Find the miniest character!!

[ iterative ]
 
 Performance counter stats for './iterative' (10 runs):
    821    cache-misses    #    6.209 % of all cache refs ( +- 63.53% )
    13219    cache-references    ( +-  3.92% )
    0.763544    cpu-clock (msec)    ( +-  8.35% )
    13113    L1-dcache-load-misses    ( +-  2.16% )
    5116    L1-dcache-store-misses    ( +-  1.70% )
 
    0.066155528 seconds time elapsed    ( +- 98.00% )
 
為了重新貼一次performance就重新跑了一次程式!結果竟然發現iteraive version的cash-misses減低好多!回想一下才發現昨天測試時iterative version好像忘記先清cach...
 
[ recursive ]
char find_miniest_ch (char *s, char c, int p)
{
    if ((*(s + p)) == '\0') {
        return (*s);
    }   
    if ((*s+p) == c) {
        if (*(s+p+1) != '\0')
            return *(s+p+1);
    } else {
        p++;
        return find_miniest_ch(s, c, p); 
    }   
    return 0;
}
 
Performance counter stats for './recursive' (10 runs):
    723      cache-misses    #    5.509 % of all cache refs ( +- 56.07% )
    13127    cache-references    ( +-  2.40% )
    0.756036    cpu-clock (msec)    ( +-  6.02% )
    13157    L1-dcache-load-misses    ( +-  1.42% )
    5105    L1-dcache-store-misses    ( +-  0.99% )
 
    0.084588630 seconds time elapsed    ( +- 98.46% )
 
recursive的cache misses好低!自己也嚇到了!個人猜測可能是跟recurseive version在function裡面都是用指標操作有關係!
 
 

Q3 Flatten the tree!

[ recursive ]
void flatten(node * root)
{
    if (root == NULL)
        return;