2018q1 Homework1 (phonebook)

contributed by <rex662624>

Reviewed by `ryanpatiency`

There are so many git commit message start with "Formatted" which should change to "Format" according to the rule list in the link given by the homework
The smaz algorithm is cool, could you illustrate how you implement it in hackmd?

Reviewed by `e94046165`

在實作 hash search 時挑選了多個 hash function 比較 performance。但可能因著搜尋的 lastName 設定成 'zyxels'這個在字典檔末端的單字（根據生成 hashtable 的機制，會在該對應 index 串列的前端）因此不同的 hash function 下的效能差不多。
承上，建議可以搜尋不同的目標，以平均的效能作比較。或乾脆將各個 hash function 轉換後的 data distribution 呈現出來，能更客觀的比較不同 hash function 的效能差異。

推上 GitHub 前請記得$make clean，不要把執行檔及 output 檔推上去

參考【譯】如何撰寫Git提交訊息撰寫 commit message
課程助教

好的，已修正 Makefile
rex662624

398674b commit message 標題第一個字應為大寫，且應敘述對 Makefile 做了怎樣的修改

好的
rex662624

系統環境

$lscpu

Architecture:           x86_64
CPU 作業模式：            32-bit, 64-bit
Byte Order:             Little Endian
CPU(s):                 4
On-line CPU(s) list:    0-3
每核心執行緒數：           1
每通訊端核心數：           4
Socket(s):              1
NUMA 節點：              1
供應商識別號：             GenuineIntel
CPU 家族：               6
型號：                   94
Model name:             Intel(R) Core(TM) i5-6300HQ CPU @ 2.30GHz
製程：                   3
CPU MHz：               2300.000
CPU max MHz:            3200.0000
CPU min MHz:            800.0000
BogoMIPS:               4608.00
虛擬：                   VT-x
L1d 快取：               32K
L1i 快取：               32K
L2 快取：                256K
L3 快取：                6144K
NUMA node0 CPU(s):      0-3

案例探討 : phonebook

1.縮減 entry size

中英文字間請記得空白
課程助教

已修正

我們在找電話簿時，因為是藉由 last name 來尋找，所以其它的資訊其實並不需要一起放到 cache 中，所以透過縮減 cache line 的方式，能夠降低其 cache miss rate 。所以將其他暫時不需要用到的資訊放在另一個重新宣告的 structure 中，並在原來的 struct 用指標指向這些 detail information 。

請修正你的用語「其它的資訊其實並不需要一起放到 cache 中」這不精確，首先是「放到 cache」這句話就不對，因為 cache 是依據 locality of reference 而被「更新」，並非主動「放到」哪裡去。軟體開發者要考慮到硬體的特性，讓 cache 的效益得以發揮 (回顧 Memory hierarchy)，在實驗前後，你應該要能透過自己的估算，得知下方修改的效能並且充分解釋。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

好的，謝謝老師。
原本的 struct size = 136 bytes ，而我的開發環境的 layer1 cache 是 32KB ，而因為 cache 的 spatial locality 特性，導致存取 structure 某一成員時，整個 structure 的資料都會更新到 cache中，因此最多只能放 32 * 1024 / 136 = 240.94 筆資料。而修改過後的 struct size = 32 bytes ，因此能放 1024 筆資料， cache miss rate 也會大幅降低。
rex662624






















typedef struct __PHONE_BOOK_ENTRY {
    char lastName[MAX_LAST_NAME_SIZE];
    struct __PHONE_BOOK_ENTRY_DETAIL *pDetail;
    struct __PHONE_BOOK_ENTRY *pNext;
} entry;

//1.縮減struct __PHONE_BOOK_ENTRY 的成員,使cache miss 降低

typedef struct __PHONE_BOOK_ENTRY_DETAIL {
    char firstName[16];
    char email[16];
    char phone[10];
    char cell[10];
    char addr1[16];
    char addr2[16];
    char city[16];
    char state[2];
    char zip[5];
} detail;

entry *findName(char lastName[], entry *pHead);
entry *append(char lastName[], entry *e);

以下比較：上圖是原始版本的程式，下圖是修改後的版本，可以發現 cache miss rate 大幅降低，從90％左右下降到60％左右。但節省時間的同時，也犧牲一小部份 memory 空間，因為縮減的版本多另外宣告一個指標指向 detail 。

$sudo perf stat --repeat 10 -e cache-misses,cache-references,instructions,cycles ./phonebook_orig

 Performance counter stats for './phonebook_orig' (50 runs):

         2,248,323      cache-misses              #   87.100 % of all cache refs      ( +-  0.11% )
         2,581,318      cache-references                                              ( +-  0.08% )
       224,046,318      instructions              #    1.49  insn per cycle           ( +-  0.03% )
       150,404,357      cycles                                                        ( +-  0.11% )

       0.053928188 seconds time elapsed                                          ( +-  0.42% )

$sudo perf stat --repeat 10 -e cache-misses,cache-reference,instructions,cycles ./phonebook_opt

 Performance counter stats for './phonebook_opt' (10 runs):

           767,154      cache-misses              #   65.794 % of all cache refs      ( +-  0.37% )
         1,165,995      cache-references                                              ( +-  0.38% )
       204,809,130      instructions              #    1.91  insn per cycle           ( +-  0.05% )
       107,501,380      cycles                                                        ( +-  0.34% )

       0.040579466 seconds time elapsed                                          ( +-  5.21% )

2.引入 hash function

參考 workfunction，導入了hash的機制。

hash 是透過 hash function ，將輸入的key由 hash function 轉換成一個 index ，而這個產生出的 index ，就決定此data要串在哪個 bucket 後面(我理解為放在某個抽屜裡面)。而如何讓輸入的 data 盡量能 uniform 分佈，也決定著 hash function 效率。

能否進一步說明："如何讓輸入的data盡量能uniform分佈，也決定著hash function效率。"？

資料的分佈應是源於 hash function 影響，參考 hash function 觀念和實務的 hash distribution
課程助教

這部份是我打錯了。應該如助教所說，key 輸入到 hash function 後會對應產生一個 index，這個 index 就是 key 應該插入的 bucket 編號，因此是 hash function 決定著資料的分佈情形。而我的原意是指，使用 hash 這個方法的效率，決定於資料是否 uniform distributed(而這部份又由hash function決定) 。因為若是所有的 key 都串在同一個 bucket 中，跟原來的linked list 是無異的。
rex662624

了解，那請指出你所使用的 hash function 為何？並補上原因，也可以再接著比較使用不同 hash function 的結果
課程助教

請見以下的4.不同hash function的比較
rex662624

一般的hash 會有 collision 的情況，就是一個抽屜只能放一個人，這裡用的方法是每個抽屜都是一個 linked list ，所以要找人只要翻這個抽屜，從頭翻到尾，沒有就代表電話簿中根本沒有。



















































/*
要找的人先透過hash function看它應該收在哪個抽屜裡，如果那個抽屜裡從頭到尾都沒有表示電話簿裡根本沒有
*/
entry *findName(char lastname[], entry *table[])
{
    unsigned nHash = hash(lastname);
    entry *pHead = table[nHash];
    while (pHead != NULL) {
        if (strcasecmp(lastname, pHead->lastName) == 0)
            return pHead;
        pHead = pHead->pNext;
    }
    return NULL;
}
/*
經由hash function算出的index收到正確的抽屜裡（串到table[index]中）
*/
void append(char lastName[], entry *table[])
{
    unsigned nHash = hash(lastName);
    entry *e = (entry *) malloc(sizeof(entry));
    e -> pNext = table[nHash];
    if(!table[nHash]) {
        table[nHash] = e;
    } else {
        table[nHash] -> pNext = e;
    }
    strcpy(e -> lastName, lastName);
}
/*
hash function
*/
unsigned hash(char name[])
{
    unsigned sum;
    int i;
    for (sum = 1, i = 0; i < 16 && name[i] > 0; i++) {
        sum = sum * name[i] - i * name [i];
    }
    return sum % MOD;
}
/*
一開始就要把bucket準備好,table[0]代表第0個bucket,這裡的mod是30000代表30000個bucket
*/
void initTable(entry *table[])
{
    for(int i = 0; i < MOD; i++) {
        table[i]=NULL;
    }
}

以下觀察到，用縮減的 structure 加上 hash table ，能使 cache miss rate 下降到23％。

$sudo perf stat --repeat 50 -e cache-misses,cache-reference,instructions,cycles ./phonebook_hash

 Performance counter stats for './phonebook_hash' (10 runs):

         669,030      cache-misses              #   23.385 % of all cache refs      ( +-  0.94% )
       2,860,982      cache-references                                              ( +-  0.29% )
     280,249,904      instructions              #    2.03  insn per cycle           ( +-  0.04% )
     138,206,762      cycles                                                        ( +-  0.31% )

     0.08275015 seconds time elapsed                                          ( +- 34.96% )

3.引入 binary search tree

參考 ryanwang522，導入了binary search tree的機制。

本來的 binary search tree 需要透過比較的方式，才能找到到底要在 tree 的哪個位置，根據那位同學提供的資訊，需要透過strcasecmp() byte-by-byte comparsion 的方式實做，透過 lastname 的字元相減找出孰大孰小。

而這裡利用了 word.txt 本來就是排序好的，串進linked list自然也是排序好的，因此只需透過 Sorted Linked List to Balanced BST就能建立好 tree 。





























































int Length(entry *head)//用來算list總長度
{
    int count = 0;
    entry *current = head;

    while (current != NULL) {
        count++;
        current = current -> pNext;
    }

    return count;
}
//因為word.txt檔裡面的文件都是已經排序好的 所以用Sorted Linked List to Balanced BST ,
//而不用去byte-by-byte comparsion
//length第一次進入function時＝list總長度
treeNode *BuildBST(entry **headRef, int length)
{
    if (length <= 0)
        return NULL;

    treeNode *left = BuildBST(headRef, length/2);
    treeNode *root = (treeNode *) malloc(sizeof(treeNode));
    root->entry = *headRef;
    root->left = left;

    *headRef = (*headRef)->pNext;

    root->right = BuildBST(headRef, length - (length / 2 + 1));

    return root;
}

entry *findName(char lastName[], treeNode *root)
{
    treeNode *current = root;
    int result;

    while (current != NULL && (result = strcasecmp(lastName, current->entry->lastName)) != 0) {
        if (result < 0)
            current = current -> left;
        else
            current = current -> right;
    }

    if (root)
        return (current->entry);
    else
        return NULL;
}

entry *append(char lastName[], entry *e)
{
    e->pNext = (entry *) malloc(sizeof(entry));
    e->detail = NULL;
    e = e -> pNext;
    strcpy(e->lastName, lastName);
    e->pNext = NULL;

    return e;
}

以下可以觀察到， miss rate 又回到跟1.只用縮減的 struct 相同的水準。甚至還更高了一點。推測是因為這裡的append()還是用原來的所以 cache miss 會和原來的水準相同。而後面 append 完，有 sorted linked list 之後的 build bst 等動作又把 miss rate 又拉高了一點。

 Performance counter stats for './phonebook_bst' (50 runs):

         1,453,831      cache-misses              #   69.532 % of all cache refs      ( +-  0.23% )
         2,090,874      cache-references                                              ( +-  0.27% )
       285,552,313      instructions              #    1.97  insn per cycle           ( +-  0.03% )
       145,025,841      cycles                                                        ( +-  0.32% )

       0.053175113 seconds time elapsed                                          ( +-  2.78% )

4.不同hash function的比較

首先，助教問到了我原本的 hash function 為何。我在當初是參考 workfunction 同學的function 。而遺憾的是我沒有在網路找到這是哪個演算法，這位同學在當初修課的學期還是用hackpad，所以看不到開發紀錄。






    unsigned sum;
    int i;
    for (sum = 1, i = 0; i < 16 && name[i] > 0; i++) {
        sum = sum * name[i] - i * name [i];
    }
    return sum % MOD;

但這個寫法，看起來也並未空穴來風(或許只是我沒有在網路上找到)。因為 sum * name[i] 這裡，考慮到了hash function需要的雪崩機制，讓 last name 只要有一個字元改變，就會對應到不同的index。而後面的減法，可能是為了增加變異性，而且不讓它 overflow 而使用了減法而非加法。

因為無法確定到底是什麼演算法，所以我去找了是否有更加有效率的演算法，並與這個演算法加以做比較

上面的 hash function 在教科書裡頭可見，不要第一個時間只想要去 Google 搜尋

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

好的，謝謝老師。
rex662624

BKDRHASH






    unsigned int seed = 31;
    unsigned int hash = 0;
    while(*name)
        hash = hash * seed + (*name++);

    return (hash % MOD);

djb2







    unsigned long hash = 5381;
    int c;
    while (c = *name++)
        hash = ((hash << 5) + hash) + c; // hash * 33 + c 

    return (hash%MOD);

三者的效能比較圖(hash table size 固定皆為1024)，可以看出findname()三者相去不遠，而append()的部份則是 bkdrhash 和 djb2 較好一些，因此在我的github上決定註解掉另外兩個function並留下 bkdrhash 。

5.使用memory pool

參考 ierosodin 。 memory pool 主要的精神是預先要好需要的記憶體空間，而之後就跟這塊空間要就好，不用每次都再跟系統要，這樣每次都是一次的時間浪費。




























memory_pool *pool_init(int size)
{
    memory_pool *pool = (memory_pool *) malloc(sizeof(memory_pool));

    pool->begin = pool->next = (char *) calloc(1, size);
    pool->end = pool->begin + size;

    return pool;
}

void *pool_alloc(memory_pool *pool, int size)
{
    if (pool->end - pool->next < size)
        return NULL;

    void *result = pool->next;
    pool->next += size;

    return result;
}

void pool_free(memory_pool *pool)
{

    free(pool->begin);
    free(pool);

}

想要詢問為何是pool->next = (char *) calloc(1, size)
這樣void *result = pool->next;為什麼不會取到一個字串的指標？
vulxj0j8j8

 Performance counter stats for './phonebook_memorypool' (10 runs):

           531,157      cache-misses              #   63.950 % of all cache refs      ( +-  0.95% )
           830,580      cache-references                                              ( +-  0.32% )
       143,551,632      instructions              #    1.77  insn per cycle           ( +-  0.11% )
        81,228,557      cycles                                                        ( +-  0.14% )

       0.031117136 seconds time elapsed                                          ( +-  5.37% )

以上的 code ，首先 pool_init 就先要好了全部的空間，而後面的 pool_alloc 和 pool_free 就取代了 malloc() 和free() ，只是從這塊預先要好的空間切一塊給 request 者。
因為只用了縮減的structure，所以cache miss維持60%左右。

用gnuplot比較以上四者與original版本效能

gnuplot跟Makefile的語法算是我比較不熟的部份，雖然 Makefile 以前有接觸過，但是 CFLAGS 和宣告 marco 的方法是第一次接觸，因此把連結存起來以便複習。

下圖是四種不同方式實做的比較。

分析
- append()
  
  optimized (只用縮減的 struct )所花的時間，比 original 低了一點我想是因為 cache miss rate 降低，所以 cpu 不需要等待從 memory 一路傳上來到 L1 的 i/o 時間，所以所花時間較少。
  而 hash function 因為需要先用 function 算出正確的 bucket ，再插進linked list 之中，所以相比會多花一點時間。
  bst 則是需要找出此時 last name 應該放的位置，所以也不會達到省時效果。
  memory pool append的時間則較為降低，因為先要好了一塊memory pool就不用每次都去跟系統要求。
- findname()
  
  original 版本的時間複雜度是O(n)，而調整成 BST 後時間複雜度為 O(logn)。
  hash function 若有 n 個 table entry ，在其 uniform distributed 的狀狀下，只要找 350000/n 次。
  而memory pool只用了縮減structure，所以與縮減structure相同。

問題探討

本例選用的 dataset (也就是輸入電話簿的姓名) 是否存在問題？
有。電話簿裡有 aaaa 等現實中不會出現的姓名。而且裡面的名字完全沒有重複。若是要考慮姓名重複的問題，可能要再請使用者給多一點資訊，因為 last name 是可能一模一樣的。此外，在 phonebook_orig.h 裡面宣告了 MAX_LAST_NAME_SIZE 為16，但怎能保證一定在16個字元之內？而且若是電話簿裡都是 Ken Tom 等名字較短者，也會出現 memory 浪費。
有代表性嗎？跟真實英文姓氏差異大嗎？
沒有太大的代表性。因為如果剛才所說，有 aaaa 等名字，與現實差異較大。
資料難道「數大就是美」嗎？
不一定。資料大量雖然能確保分析正確度提高，也能考慮到各種 boundary condition ，但是這也代表著若要從其中找出一個 case 如同大海撈針。因此需要周延的分類規劃，並用合適的資料結構儲存。
如果我們要建立符合真實電話簿情境的輸入，該怎麼作？
利用現有英文名字做輸入，也可以把 first name，last name 做不同的排列組合。且不一定要按照字母排列整齊也可以有很多相同的名字出現。

既然已經發現上面四個顯著的問題，針對真實應用場景，重新設計實驗並且重新評估！

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

第二周修改

針對問題探討做進一步修正

把word.txt裡面的名字打亂。
因為原本的名字都是按照字母順序排列，因此不符合現實狀況，於是用sort -R words.txt > word2.txt 把名字順序打亂。
以下是我用original，optimized(縮減的struct)，hash+縮減struct，memorypool+縮減struct四者的比較。而因為我的binary search tree是用針對sorted資料的演算法，因此不適用，先不做比較。
可以發現，跟一開始排序好的效能相比，append()改變沒有很大，因為還是要一個個的插入list當中，不會有太大改變。但是find的部份，卻有一些差異。
在original，optimated，memorypool的部份，find()效率都有顯著的提昇。這是因為三人的append都是根據word.txt順序做linked list，而測試資料是"zyxel"，這在原本的word.txt中是在很後面的名字。而在打亂過後，有很大的機率比原來還前面，因此找到的時間會更快。而我的hash的append，機制是串在第一個，也就是head的後面，因此find()也符合效率變差。因為原來的"zyxel"很晚進來，表示插在很前面。而打亂過後的則變得比較後面。

加入壓縮字串的演算法

參考 jkrvivian 引入字串壓縮的演算法。在這裡我也是用 SMAZ 演算法。
根據原作者github上的 readme ，這個演算法也並非能使所有的 string 被壓縮。這個演算法有利於沒有數字的字串。例如 "the" 能被壓縮為 1 byte 。但是 "not-a-g00d-Exampl333" 反而會使儲存空間增長15%。

注意：原本的輸入資料本來就不適合文字型態的壓縮，改用其他資料輸入再測試，這是故意要引導學生思考的議題之一。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

從以下圖可以發現， append 的時間增長許多，因為 append() 裡面，每次都要壓縮過才能串進去 list 中。而 find() 時間與 opt 版本相近。

cache miss rate 的部份，與opt比起來其實沒有太大的突破(約降低1%~3%)。推測應該是因為有些字串經過 smaz function 之後反而變大了，而有些順利壓縮，消長之下， cache 中能放的資料數量與原來差不多。

 Performance counter stats for './phonebook_smaz' (100 runs):

           759,771      cache-misses              #   62.661 % of all cache refs      ( +-  0.47% )
         1,212,508      cache-references                                              ( +-  0.57% )
       720,472,381      instructions              #    1.65  insn per cycle           ( +-  0.00% )
       436,993,090      cycles                                                        ( +-  0.06% )

       0.146145906 seconds time elapsed                                          ( +-  0.44% )

append 之後立刻 find 的情境和真實世界的應用截然不同，你應該嘗試切割 append 和 find 兩個不同的操作，分別用 perf 分析，注意輸入資料的影響

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

補充

在經過多次測試不同的資料，例如我測試了 dictionary/ 內的 all-names.txt 。還有自己做了一個測試檔，裡面都是放 "the" 這個字串，並在最後一行放 "apple" ，讓程式去尋找最後一行的 "apple" ，但都未見 cache miss 有所顯著降低。因此我推測如果 MAX_LAST_NAME_SIZE 給的是固定值 16 ，不管裡面的字串再如何壓縮，每筆資料存取時被更新到 cache 中仍然是整個 structure 的 32 byte 。因此我想存放 lastname 的 array 應該要改成動態宣告，這樣才能減小 struct size ，才能發揮壓縮字串演算法的最大效益。

另外我也透過sudo perf record -F100000 -e cache-misses:u,cache-references,instructions,cycles ./phonebook_smaz , sudo perf report發現了，多次測試中， cache miss rate 除了 findname() 時常高居第一， append() 中呼叫的壓縮字串函式 compress() 有時也會在前幾名。而 cyles 跟 instruction 的部份，compress() 則是永遠在第一名。因此若根據現實狀況，雖然在存入電話簿的時候要先壓縮字串，可能會花多餘的時間，但是 findname() 的時間會因為cache miss降低而變快。

fuzzy search

參考 2017 年秋季期班中報告。

模糊查詢 (Fuzzy Searching) 是當使用者輸入一個關鍵字時，搜尋引擎不僅查詢所輸入的關鍵字，同時也自動去查詢與所輸入關鍵字意義相同的字詞。
而這裡我採用的是 Wagner–Fischer algorithm ，這種演算法是去計算將一字串轉換成另一個字串所需之編輯次數。而編輯可分為插入、刪除以及取代三種操作。

例如：
apple 和 opple，distance 為 1，因為需要把 a 取代成 o
apple 和 applepie，distance 為 3 ，因為需要插入 p,i,e 三個字元
相對的 applepie 和 apple，distance也為3，因為需要刪除 pie。

























int wagnerFischer(const char *s, const char *t)
{
    int len_s = strlen(s), len_t = strlen(t);
    int distance[len_s + 1][len_t + 1];

    for (int i = 0; i <= len_s; i++) {
        distance[i][0] = i;
    }
    for (int j = 0; j <= len_t; j++) {
        distance[0][j] = j;
    }

    for (int j = 1; j <= len_t; j++) {
        for (int i = 1; i <= len_s; i++) {
            if (s[i - 1] == t[j - 1])
                distance[i][j] = distance[i - 1][j - 1];
            else
                distance[i][j] = min(
                                     distance[i-1][j] + 1,
                                     distance[i][j-1] + 1,
                                     distance[i-1][j-1] + 1);
        }
    }
    return distance[len_s][len_t];
}

在我 github 的程式中，fuzzy search 是單獨出來的，也就是輸入 sudo make plot 不會執行和輸出圖。但是 main 和 make 還是與其他功能共用同一檔案。因為 fuzzy search 我設計成動態查詢，也就是執行後，會先問使用者想找哪個 last name ，再輸出所有相似結果。
在我的程式中，我的 SIMILARITY 變數是設 2 ，也就是只有 distance<=2 的字串會輸出。

以下為範例輸出

$./phonebook_fuzzy 
size of entry : 32 bytes
please enter the last name you want search: zyexl
-------------------
gyel
lyel
nyel
wyex
yeal
yeel
yell
yexal
zeal
zell
zexpl
ziehl
zoeal
zoel
zygal
zyxel
Sorry, not found
execution time of append() : 0.039075 sec
execution time of findName() : 0.160346 sec

zyexl 是輸入的字串。而橫線下方會輸出與此字串相近的字。因為最後沒有找到，所以會輸出 Sorry, not found 。

因為自動飲料機而延畢的那一年心得與啟發

看了交大學長的這篇心得分享後，佩服之餘同時也覺得有點惶恐，因為裡面說到的"資工系的學生不會寫程式"，不禁讓我反思，我們在學校學的種種知識，究竟會不會跟產業脫節，又或者更準確的說，我們是否能像作者一樣做出這種真的能賣出銷售的產品，把在學校所學的知識應用到市場層面。

作者找到了兩個志同道合的好友參與這項專案，用三人團隊做出了這個自動飲料機。而貫通整篇文章的中心思想就是–-遇到困難仍然勇往直前。許多不同領域的學生要做到整合，勢必資訊領域的學生也要懂機械，機械領域的學生也要略知資訊，才能知道甚麼可行，什麼不可行。因此製作過程中一定會遇到許多困難，而支撐他們的，是靠對這件事的熱情，與心中的夢想。

最後，這件發明也因為作者去當兵，乏於維護而無法送進飲料店。但我覺得他們也沒有失敗。或者說，花時間去提升自己，增強自己的競爭力，不管市場採不採納，永遠稱不上是失敗。因為就算沒有成功打入市場，他們也贏得了經驗。

這個世界比任何人都殘酷，也比任何人都公平，犧牲了多少就會得到多少(節錄自文章中)。我認為不僅僅是指他們做專案的過程付出很多，光是有個夢想，敢開始去接專案或發明東西，我認為就是跨出了一大步，這也是現在大部分的學生都沒有的。而我們這些只有課內科目要學習的學生，就更沒有理由偷懶了。畢竟人不付出犧牲，就得不到任何回報，一棵樹要長得更高，接受更多的光明，那麼它的根就必須更深入黑暗。

2018q1 Homework1 (phonebook)

Reviewed by ryanpatiency

Reviewed by e94046165

系統環境

案例探討 : phonebook

1.縮減 entry size

2.引入 hash function

3.引入 binary search tree

4.不同hash function的比較

5.使用memory pool

用gnuplot比較以上四者與original版本效能

問題探討

第二周修改

針對問題探討做進一步修正

加入壓縮字串的演算法

補充

fuzzy search

因為自動飲料機而延畢的那一年心得與啟發

Reviewed by `ryanpatiency`

Reviewed by `e94046165`