# 2016q1 Homework1 (phonebook)
contributed by <`kylingithub`>

## Reviewed by <`snoopy831002`>
* 建議可以每個版本git commit一次
* 建議可以補上使用perf找熱點，因為如果hash function沒有經過特殊處理 append()應該會比opt版本還要慢，因為要進行hash(可以使用perf看出來)

## 環境設置
* 使用光碟安裝lubuntu16.04 於筆電，與win10共存
* UEFI開機
第一次安裝時，出現無法安裝的情況，推測是win10預設為UEFI開機模式。因此進入BIOS關閉UEFI-->Disable，但這樣一來win10就無法正常使用。
參考[]
重新安裝一次即可成功。
* 輸入法
系統預設的語言包是簡單的注音，就算安裝新酷音選字的選單也會顯示黑屏，無法正常使用。
因此參考[]將系統的顯示語言改成ibus後，安裝新酷音即可正常使用。
* 音效卡
想要一邊看教學影片一邊實做練習時，發現影片竟然沒有聲音！
推測是驅動程式的問題，參考[]，進入alsa
但仍無法正常使用，因此去尋找其他的Driver
參考[音效程式安裝](https://askubuntu.com/questions/774458/installed-lubuntu-16-04-version-no-audio-now/775588#775588?newreg=0b982e1478f44c51b9e6d119d66fa1b7)，將系統內建的ALSA解除安裝，並裝上pavucontrol，即可聽到聲音，即可順利進行。
---
## C語言的複習
1. 觀看[你所不知道的C語言：指標篇](http://hackfoldr.org/dykc/s0rlzR8wVtm)
2. 陣列
* 陣列的參數傳遞：C語言只能傳遞指標,無法傳遞陣列的內容。
* [Pointer 觀念整理](http://zer931.pixnet.net/blog/post/36928945-c-c%2B%2B%E4%B9%8B%E6%8C%87%E6%A8%99-(pointer)%EF%BC%8C%E5%8F%83%E8%80%83-(reference)-%E8%A7%80%E5%BF%B5%E6%95%B4%E7%90%86)
3. Pointer 實驗
* 以下為測試程式碼

#include <stdlib.h>
#include <stdio.h>

int b =2048;
void testfunc(int** ptrptr){
    printf("In function Before : ptrptr = %d , *ptrptr = %d , **ptrptr = %d \n\n",ptrptr,*ptrptr,**ptrptr);
    *ptrptr= &b;
    printf("Do : *ptrptr= &b;\n");
    
}

int main(){
    int a =5270;
    int* ptrA = &a;
    int* ptrptrA = &ptrA;
    printf("Before\n");  
    printf("a = %d, &a = %d, ptrA=%d, &ptrA = %d,*ptrA = %d \n",a,&a,ptrA,&ptrA,*ptrA);
    printf("&*ptrA = %d, *&ptrA = %d, ptrptrA = %d \n",&*ptrA,*&ptrA,ptrptrA);
    printf("b = %d, &b = %d \n\n",b,&b);

    testfunc(ptrptrA);
    printf("After\n");
    printf("a = %d, &a = %d, ptrA=%d, &ptrA = %d,*ptrA = %d \n",a,&a,ptrA,&ptrA,*ptrA);
    printf("&*ptrA = %d, *&ptrA = %d, ptrptrA = %d \n",&*ptrA,*&ptrA,ptrptrA);
    printf("ptrptrA = %d \n",ptrptrA);
    printf("b = %d, &b = %d \n",b,&b);
    return 0;
}

* 結果顯示
* 概念探討
* pointer of A 就是紀錄 A的記憶體位置(或者說 A的門牌號碼)的純量。
* \*ptrA 的 \* 表示一個運算符號，意義為ptrA指向的值。
* 根據上述的實驗與概念，將其繪製成圖表顯示，總算對指標有點感覺，在使用指標的指標也有多了一些些的理解。

---
## 工具學習
1. [Makefile]
* [Makefile的使用](http://tetralet.luna.com.tw/?op=ViewArticle&articleId=185)
* [gcc與Makefile](http://jayextmemo.blogspot.tw/2015/01/linux-gcc-makefile-2.html)
2. [GDB](http://v.im.cyut.edu.tw/~ckhung/b/c/gdb.php)
3. [Git](https://github.com/doggy8088/Learn-Git-in-30-days)
---
## Phone Book
要增加效能，首先先參考[programming small](https://hackmd.io/s/S1rbwmZ6)的方式，簡化了資料結構，以及使用Hash Function

* 作業目標
* 減少cache-miss。
* 加快程式運作速度。
* 原理分析
* 造成cache-miss最主要的原因是，cache中沒有程式所需要的資料，因此需要往下一層cache或memory查找資料。
* 增加cache中實用資料的比率，可降低cache-miss。
1. 簡化資料結構，去掉不必要的資訊，可以減少程式執行時對cache的負擔。
2. 使用Hash Table，可以加快程式查詢電話簿的時間，增加執行效率。
* 程式設計
* 新增另外一個main_opt.c，並更改Makefile。
* main_opt.c中會建立HashTable，並且在append()與findName()中，只需要輸入字串，就可以直接新增或是查找，不需要丟入entry*。
* append() 輸入名字字串，即直接丟進HashTable，若HashTable中有物件，也會將存在Table的物件向後移，並將新增的物件放在HashTable的第一個位置。
* findName() 回傳一個entry* 表示有找到，回傳NULL，表示並沒有找到。
* [程式碼](https://github.com/kylingithub/phonebook)

void append(char lastName[])
{
    /* allocate memory for the new entry and put lastName */
    int index = hash(lastName);
    entry* e = (entry *) malloc(sizeof(entry));
    strcpy(e->lastName, lastName);

    //insert to hash table
    e->pNext = hashtable[index];
    hashtable[index] = e;

}

entry *findName(char lastname[])
{
    int index = hash(lastname);
    entry* e = hashtable[index];
    while (e != NULL) {
        if (strcasecmp(lastname, e->lastName) == 0)
            return e;
        e= e->pNext;
    }
    return NULL;
}

* 效能分析

* 原生版本

* 優化版本
cache-miss cache-reference 都減少許多。
* 執行時間的比較
因為使用HashTable查找，查詢時間趨近於0，比起原本依序查找要快上許多。

可以看到不僅是findName()，append()的時間也減少許多，推測是因為我減少了append輸入的參數量。
* 問題討論
1.為何輸出HashTable的size，會顯示8bytes?
* 可以理解HashTable這個pointer of pointer的大小為8bytes。
* 但我想知道HashTable的陣列大小，卻不知要如何顯示？

---
## 參考資料
* [音效程式安裝](https://askubuntu.com/questions/774458/installed-lubuntu-16-04-version-no-audio-now/775588#775588?newreg=0b982e1478f44c51b9e6d119d66fa1b7)