# 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(tm) 64 X2 Dual Core Processor 4400+
* Core: 2
* Memory: 3GB ram
* L1d cache： 64K
* L1i cache： 64K
* L2 cache： 512K

### 環境架設
* 下載 [lubuntu](http://lubuntu.net/) iso檔。
* 因無光碟機，搜尋iso to usb 的程式來製作開機安裝光碟
使用[rufus](https://rufus.akeo.ie/?locale=zh_TW)製做成功並安裝。
* SSH key設定參考gihub上的說明 [gen SSH key](https://help.github.com/articles/generating-a-new-ssh-key-and-adding-it-to-the-ssh-agent/#platform-linux)並設定。

* 因安裝的lubuntu無中文輸入法花了點時間設定 [參考這篇](https://www.ubuntu-tw.org/modules/newbb/viewtopic.php?post_id=212374) 和安裝 gcin
`sudo apt-get install gcin` 安裝完執行會Coredump 重開機後可正常執行。

* 截圖程式 lubuntu 本身的截圖已足夠使用需求，不過求順手還是找了另外一款程式，參考聯結安裝 [shutter](https://blog.gtwang.org/linux/linux-screenshot-program-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`