# 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 的效能差異。
>1. 推上 GitHub 前請記得`$make clean`，不要把執行檔及 output 檔推上去
>2. 參考 [【譯】如何撰寫Git提交訊息](https://xiwan.io/archive/how-to-write-a-git-commit-message.html) 撰寫 commit message
>[color=red][name=課程助教]
>
>>好的，已修正 Makefile
>>[color=#bba9f2][name=rex662624]
>>
> [398674b](https://github.com/rex662624/phonebook/commit/398674b1b347be093c8924ead781d3dd70d8990f) commit message 標題第一個字應為大寫，且應敘述對 Makefile 做了怎樣的修改
>
>>好的
>>[color=#bba9f2][name=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
>中英文字間請記得空白
>[color=red][name=課程助教]
>
>>已修正
>>[color=#bba9f2]
我們在找電話簿時，因為是藉由 last name 來尋找，所以其它的資訊其實並不需要一起放到 cache 中，所以透過縮減 cache line 的方式，能夠降低其 cache miss rate 。所以將其他暫時不需要用到的資訊放在另一個重新宣告的 structure 中，並在原來的 struct 用指標指向這些 detail information 。
:::danger
請修正你的用語「其它的資訊其實並不需要一起放到 cache 中」這不==精確==，首先是「放到 cache」這句話就不對，因為 cache 是依據 [locality of reference](https://en.wikipedia.org/wiki/Locality_of_reference) 而被「更新」，並非主動「放到」哪裡去。軟體開發者要考慮到硬體的特性，讓 cache 的==效益==得以發揮 (回顧 [Memory hierarchy](https://en.wikipedia.org/wiki/Memory_hierarchy))，在實驗前後，你應該要能透過自己的估算，得知下方修改的效能並且充分解釋。
:notes: 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 也會大幅降低。
>[color=#bba9f2][name=rex662624]
```clike=
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](https://github.com/workfunction/phonebook)，導入了hash的機制。
hash 是透過 hash function ，將輸入的key由 hash function 轉換成一個 index ，而這個產生出的 index ，就決定此data要串在哪個 bucket 後面(我理解為放在某個抽屜裡面)。而如何讓輸入的 data 盡量能 uniform 分佈，也決定著 hash function 效率。
>能否進一步說明："如何讓輸入的data盡量能uniform分佈，也決定著hash function效率。"？
>
>資料的分佈應是源於 hash function 影響，參考 [hash function 觀念和實務](https://hackmd.io/s/HJln3jU_e#) 的 hash distribution
>[color=red][name=課程助教]
>
>>這部份是我打錯了。應該如助教所說，key 輸入到 hash function 後會對應產生一個 index，這個 index 就是 key 應該插入的 bucket 編號，因此是 hash function 決定著資料的分佈情形。而我的原意是指，使用 hash 這個方法的效率，決定於資料是否 uniform distributed(而這部份又由hash function決定) 。因為若是所有的 key 都串在同一個 bucket 中，跟原來的linked list 是無異的。
>>[color=#bba9f2][name=rex662624]
>>
>了解，那請指出你所使用的 hash function 為何？並補上原因，也可以再接著比較使用不同 hash function 的結果
>[color=red][name=課程助教]
>
>>請見以下的4.不同hash function的比較
>>[color=#bba9f2] [name=rex662624]
一般的hash 會有 collision 的情況，就是一個抽屜只能放一個人，這裡用的方法是每個抽屜都是一個 linked list ，所以要找人只要翻這個抽屜，從頭翻到尾，沒有就代表電話簿中根本沒有。
```clike=
/*
要找的人先透過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](https://hackmd.io/s/Sk-qaWiYl#)，導入了binary search tree的機制。
本來的 binary search tree 需要透過比較的方式，才能找到到底要在 tree 的哪個位置，根據那位同學提供的資訊，需要透過`strcasecmp()` byte-by-byte comparsion 的方式實做，透過 lastname 的字元相減找出孰大孰小。
而這裡利用了 word.txt 本來就是排序好的，串進linked list自然也是排序好的，因此只需透過 [Sorted Linked List to Balanced BST](http://www.geeksforgeeks.org/sorted-linked-list-to-balanced-bst/)就能建立好 tree 。
```clike=
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](https://github.com/workfunction/phonebook) 同學的function 。而遺憾的是我沒有在網路找到這是哪個演算法，這位同學在當初修課的學期還是用hackpad，所以看不到開發紀錄。
```clike=
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 而使用了減法而非加法。
因為無法確定到底是什麼演算法，所以我去找了是否有更加有效率的演算法，並與這個演算法加以做比較
:::info
上面的 hash function 在教科書裡頭可見，不要第一個時間只想要去 Google 搜尋
:notes: jserv
:::
>好的，謝謝老師。
>[color=#bba9f2][name=rex662624]
* [BKDRHASH](http://blog.csdn.net/wanglx_/article/details/40400693)
```clike=
unsigned int seed = 31;
unsigned int hash = 0;
while(*name)
hash = hash * seed + (*name++);
return (hash % MOD);
```
* [djb2](http://www.cse.yorku.ca/~oz/hash.html)
```clike=
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](https://github.com/rex662624/phonebook/blob/master/phonebook_hash.c)上決定註解掉另外兩個function並留下 bkdrhash 。
### 5.使用memory pool
參考 [ierosodin](https://hackmd.io/s/SJ4uqs9Yx#) 。 memory pool 主要的精神是預先要好需要的記憶體空間，而之後就跟這塊空間要就好，不用每次都再跟系統要，這樣每次都是一次的時間浪費。
```clike=
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;為什麼不會取到一個字串的指標？
>>[color=purple][name=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](https://hackmd.io/s/Skwp-alOg#)跟[Makefile](https://hackmd.io/s/SySTMXPvl#)的語法算是我比較不熟的部份，雖然 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 做不同的排列組合。且不一定要按照字母排列整齊也可以有很多相同的名字出現。
:::success
既然已經發現上面四個顯著的問題，針對真實應用場景，重新設計實驗並且重新評估！
:notes: 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](https://hackmd.io/s/SyOQgOQa#%E4%BD%BF%E7%94%A8%E5%AD%97%E4%B8%B2%E5%A3%93%E7%B8%AE%E6%B3%95) 引入字串壓縮的演算法。在這裡我也是用 [SMAZ](https://github.com/antirez/smaz) 演算法。
根據原作者github上的[ readme ](https://github.com/antirez/smaz/blob/master/README)，這個演算法也並非能使所有的 string 被壓縮。這個演算法有利於沒有數字的字串。例如 "the" 能被壓縮為 1 byte 。但是 "not-a-g00d-Exampl333" 反而會使儲存空間增長15%。
:::warning
注意：原本的輸入資料本來就不適合文字型態的壓縮，改用其他資料輸入再測試，這是故意要引導學生思考的議題之一。
:notes: 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% )
```
:::warning
append 之後立刻 find 的情境和真實世界的應用截然不同，你應該嘗試切割 append 和 find 兩個不同的操作，分別用 perf 分析，注意輸入資料的影響
:notes: 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 年秋季期班中報告](https://hackmd.io/s/BJl6pFyzf) 。
模糊查詢 (Fuzzy Searching) 是當使用者輸入一個關鍵字時，搜尋引擎不僅查詢所輸入的關鍵字，同時也自動去查詢與所輸入關鍵字意義相同的字詞。
而這裡我採用的是 [ Wagner–Fischer algorithm ](https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm)，這種演算法是去計算將一字串轉換成另一個字串所需之編輯次數。而編輯可分為插入、刪除以及取代三種操作。
例如：
apple 和 opple，distance 為 1，因為需要把 a ==取代==成 o
apple 和 applepie，distance 為 3 ，因為需要==插入== p,i,e 三個字元
相對的 applepie 和 apple，distance也為3，因為需要==刪除== pie。
```clike=
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 。
### [因為自動飲料機而延畢的那一年](http://opass.logdown.com/posts/1273243-the-story-of-auto-beverage-machine-1)心得與啟發
看了交大學長的這篇心得分享後，佩服之餘同時也覺得有點惶恐，因為裡面說到的"資工系的學生不會寫程式"，不禁讓我反思，我們在學校學的種種知識，究竟會不會跟產業脫節，又或者更準確的說，我們是否能像作者一樣做出這種真的能賣出銷售的產品，把在學校所學的知識應用到市場層面。
作者找到了兩個志同道合的好友參與這項專案，用三人團隊做出了這個自動飲料機。而貫通整篇文章的中心思想就是---遇到困難仍然勇往直前。許多不同領域的學生要做到整合，勢必資訊領域的學生也要懂機械，機械領域的學生也要略知資訊，才能知道甚麼可行，什麼不可行。因此製作過程中一定會遇到許多困難，而支撐他們的，是靠對這件事的熱情，與心中的夢想。
最後，這件發明也因為作者去當兵，乏於維護而無法送進飲料店。但我覺得他們也沒有失敗。或者說，花時間去提升自己，增強自己的競爭力，不管市場採不採納，永遠稱不上是失敗。因為就算沒有成功打入市場，他們也贏得了經驗。
這個世界比任何人都殘酷，也比任何人都公平，犧牲了多少就會得到多少(節錄自文章中)。我認為不僅僅是指他們做專案的過程付出很多，光是有個夢想，敢開始去接專案或發明東西，我認為就是跨出了一大步，這也是現在大部分的學生都沒有的。而我們這些只有課內科目要學習的學生，就更沒有理由偷懶了。畢竟人不付出犧牲，就得不到任何回報，一棵樹要長得更高，接受更多的光明，那麼它的根就必須更深入黑暗。
Sign in with Wallet
Connect another wallet