HW3
 
Q2:
iterative:
char smallest_character(char str[], char c){
        int size;
        for(size=0; str[size]!=127; size++)
                if(str[size] > c)
                        return str[size];
        return str[0];
}
recursive:
char smallest_character(char str[], char c, int index){
        if(str[index]!=127){
                if(str[index] > c)
                        return str[index];
                return smallest_character(str, c, (index+1));
        }
        return str[0];
}
 
效能分析:

iterative (5)
recursive (5)
iterative (300)
recursive (300)
execution time (sec)
0.000000
0.000000
0.000001
0.000003
cache-misses times
676
692
535
1300
cache-references times
12,580
12,790
11,572
11,640
cache-misses ratio
5.374%
5.410%
4.623%
11.168%
cycles
571,947
579,292
577,785
569,366
instructions
475,761
481,069
484,790
490,003
note: 括號內為array裡的char數量
除了cache miss比較明顯增加之外,實在是看不出甚麼差別R
另外,使用optimized compilation之後,更是沒差別了...
 
Q3:
iterative:
void flatten(TreeNode *root){
        TreeNode *tmp;
        while(root){
                if(root->left){
                        tmp = root->left;
                        while(tmp->right) tmp=tmp->right;
                        tmp->right = root->right;
                        root->right = root->left;
                        root->left = NULL;
                }
                root = root->right;
        }
}
recursive: