Embedded2015-Autumn Homework 3
 

Source Code

 

Week2 Exam Program

Question 2
給定已排序的字串以及一個要搜索的字元,回傳字串中比字元大的最小字元。若這種字元不存在則回傳字串中最小的字元。
 
  • 遞迴
由於字串已經排序過,我們只要找到一個比搜索字元還要大的字元就可以馬上做回傳。想到自己第一次實做的時候,還走訪了整個陣列就覺得很蠢...原本我希望能只用一個Function就能實現,但是這種作法沒辦法達到「如果搜尋對象不存在,則回傳陣列最小值」這個條件。最後不得已加了offset這個參數,用來追蹤整個陣列的長度。然後為了維持跟迭代版本有一樣的界面,另外寫了一個sc_recursive()然後用smallest_charcter()去驅動他。
 
  • 非遞迴
我的作法同遞迴版本從頭循序訪問到字串尾端。
但這題我有上網偷看一下人家的解法,由於此字串已經排序過,所以可以用binary search的方式做搜尋。
字串量目前很小,所以速度上感受不出來,但是當數據量變多後肯定是網路上的解法會快很多。我猜這才是這個面試題想要考的東西。
 
  • 分析
由於題目的字串太小,所以我另外用python寫了一個可以產生重複排序字元的script
以下的結果是由2600000個字元測試所得到
cache miss的部份兩種實做結果沒有很大的差異。
 
上次的測試功能寫的不夠好,
參考吳佳容同學的共筆後,將程式修改成從command line接收字串與字元,可以比較動態的測試程式。
Makefile:
GENARTE_STR := perl genRndStr.pl
STRING_LENGTH = 100 1000 10000 100000
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\
            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: $(EXEC)
        $(foreach exec, $^, $(foreach len, $(STRING_LENGTH), $(foreach char, $(CHAR), ./$(exec) $(GENARTE_STR) $(len) $(char);)))
GENARATE_STR是用來執行一條perl script的變數
這個perl script會接收一個長度做參數後,回傳一個排序過的亂數字元陣列。
my @chars = ("A".."Z", "a".."z");
my $string;
$string .= $chars[rand @chars] for 1..$ARGV[0];
print join('',sort(split(//,$string))) ."\n";
然後Makefile會從"A"到"z",循環的測試不同長度的字串以及不同的實做,最後產生執行時間的紀錄檔。
 
上圖是字元陣列長度100000下,不同實做的結果。
可以看到recursive版本的實做隨著搜尋字元的大小而逐漸增長。
Binary search的iterative版本就算在這麼龐大的資料量下也可以讓搜尋時間壓的很低
另外,線性的iterative搜尋沒有預期中的逐漸增加搜尋時間,目前還在思考可能的問題點。
上圖是iterative下不同陣列長度的線性與二元搜尋的比較
可以看到Binary Search的時間穩定的落在0.01ms以下,而Linear Search的執行時間則膨脹的非常快。
 
Question 3
給定一棵二元樹,將他展開成一個鍊結串列。