2016q3 Homework 1 (phonebook)

contributed by <ElfayR>

Reviewed by Quexint

• Binary Search Tree 在 Worst Case 下插入是
  $O(n)$，也就是一條鏈的情形。算起來會是
  $O(n^2)$.
• Balanced BST 有比 RB-Tree, AVL-Tree 好寫的資料結構：Treap，可參考。

開發紀錄

系統環境

• AMD Athlon™ 64 X2 Dual Core Processor 4400+
• Core: 2
• Memory: 3GB ram
• L1d cache： 64K
• L1i cache： 64K
• L2 cache： 512K

環境架設

• 下載 lubuntu iso檔。

• 因無光碟機，搜尋iso to usb 的程式來製作開機安裝光碟
  使用rufus製做成功並安裝。

• SSH key設定參考gihub上的說明 gen SSH key並設定。

• 因安裝的lubuntu無中文輸入法花了點時間設定 參考這篇 和安裝 gcin
  sudo apt-get install gcin 安裝完執行會Coredump 重開機後可正常執行。

• 截圖程式 lubuntu 本身的截圖已足夠使用需求，不過求順手還是找了另外一款程式，參考聯結安裝 shutter。

• 修改 git 預設的編輯器 （預設安裝 GNU nano）
  git config --global core.editor "vim"
export GIT_EDITOR=vim

改進想法

Binary search tree

• 首先想利用Binary search tree 來加速。 一開始使用Recursive 的版本反而花費很長的時間在append 上面。
• 改寫成 non-recursive 版本一樣花費很長時間。原因判斷因為每次append的時候都需要從root開始找尋insert的位置變成insert的時間複雜度為n x O(log(n))和原本的演算法0(1)相差很大。

elfay@elfay:~/github/phonebook$ ./phonebook_orig
size of entry : 136 bytes
execution time of append() : 0.000151 sec
execution time of findName() : 0.000006 sec

• 搜尋時間差不多但是append時間多花了10倍

elfay@elfay:~/github/phonebook$ ./phonebook_opt 
size of entry : 144 bytes
execution time of append() : 0.001496 sec
execution time of findName() : 0.000006 sec

• 跑100次的效能分析
  
• 電話簿資料分析： 因資料採用是Sorting過後的排序，但在binary search tree中反而容易造成worse case在insert的時候（因資料傾斜）。
• 改善想法: 如何加速 append() -> 改為 balance seatch tree
• key 字串壓縮，還是可以轉換成獨一的數值來加速比較。

未來工作

• 改善 binary search tree 演算法。
• 繼續採用其他方法來減少 cache miss (hash / entry reduce)。

tags: ElfayR