開發紀錄
2015q3 Homework3 Due: 2015/10/17
實做並驗證 Week #2 程式題目
都需要實做遞迴和非遞迴的版本,要一併準備測試資料
 

Q2

Given a sorted character array and a character, return the smallest character that is strictly larger than the search character.
目前在研究Makefile,讓它可以在執行的時候直接輸入array 和 character。參考資料
$(foreach   <var>,<list>,<text>)→這個函數是用來做循環用的
修改Makefile
ARRAY = "adgjmpsvz"
CHAR := a b c d e f g h i j k l m n o p q r s t u v w x y z
run_iterative:
        $(foreach var,$(CHAR),./iterative $(ARRAY) $(var) ;)
 
run_recursive:
        $(foreach var,$(CHAR),./recursive $(ARRAY) $(var) ;)
這樣執行的時候argv[1] = "adgjmpsvz", argv[2] = a, b, ..., or z循環
perf stat -r 1000 -e cache-misses,cache-references,L1-dcache-load-misses,L1-dcache-store-misses,L1-dcache-prefetch-misses,L1-icache-load-misses make run_iterative 
            31,984      cache-misses              #    4.457 % of all cache refs      ( +-  0.51% )
           717,652      cache-references                                              ( +-  0.14% )
           602,345      L1-dcache-load-misses                                         ( +-  0.03% )
           253,568      L1-dcache-store-misses                                        ( +-  0.02% )
           261,428      L1-dcache-prefetch-misses                                     ( +-  0.03% )
           564,265      L1-icache-load-misses                                         ( +-  0.10% )
 
       0.014549120 seconds time elapsed                                          ( +-  0.46% )
 
perf stat -r 1000 -e cache-misses,cache-references,L1-dcache-load-misses,L1-dcache-store-misses,L1-dcache-prefetch-misses,L1-icache-load-misses make run_recursive 
 Performance counter stats for 'make run_recursive' (1000 runs):
            32,697      cache-misses              #    4.478 % of all cache refs      ( +-  0.50% )
           730,227      cache-references                                              ( +-  0.13% )
           598,049      L1-dcache-load-misses                                         ( +-  0.02% )
           252,348      L1-dcache-store-misses                                        ( +-  0.02% )
           258,530      L1-dcache-prefetch-misses                                     ( +-  0.03% )
           567,473      L1-icache-load-misses                                         ( +-  0.11% )
 
       0.015166053 seconds time elapsed                                          ( +-  0.48% )
 
gnuplot> plot "iterative.txt", "recursive.txt" 

iterative
recursive
平均時間
8.79762E-06
8.76358E-06
 
 
 

Q3

Give a binary tree, flatten it to a linked list in-place.
由題目給的例子可以發現就是依照preorder的順序,依序接在前個節點的右節點
perf stat -r 1000 -e cache-misses,cache-references,L1-dcache-load-misses,L1-dcache-store-misses,L1-dcache-prefetch-misses,L1-icache-load-misses ./iterative