# 2016q3 Homework1 (phonebook)
contributed by <`Quexint`>
## 報告
### 大綱
- [作業須知](https://hackmd.io/s/S1RVdgza)
### 環境
- OS: Arch Linux 4.7.4-1-ARCH
- CPU: Intel(R) Core(TM)2 Quad CPU @ 2.40GHz
- MEM: 4G
- GCC: 6.2.1
### 規格
給定 N 筆字串，然後給定 Q 筆搜索，求搜索時間最短。
$N \leq 500000$
$Q \leq 500000$
$L_i \leq 16$
### 實驗
對於每種版本，記錄執行 100 次實驗的時間。
每次實驗 N 為 349990，Q 為 3499。
### 比較
- `Trie` 的建構時間是 `Linked-List` 的 5 倍左右。
- `Trie` 的搜索時間是 `Linked-List` 的 12000 倍左右。(27.397376:0.002337, $O(NL):O(L)$)
## 開發記錄
### `v1.0` Structure Compression
根據影片中的提示，先對 structure 做瘦身。
```c
typedef struct __PHONE_BOOK_ENTRY {
char lastName[MAX_LAST_NAME_SIZE];
struct __CONTENT_ENTRY *contentPtr;
struct __PHONE_BOOK_ENTRY *pNext;
} entry;
typedef struct __CONTENT_ENTRY {
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];
} content;
```
```c
entry *append(char lastName[], entry *e)
{
e->pNext = (entry *)malloc(sizeof(entry));
e = e->pNext;
e->contentPtr = (content *)malloc(sizeof(content));
strcpy(e->lastName, lastName);
e->pNext = NULL;
return e;
}
```
發現沒比較好，而且 `append` 因為 `malloc` 兩次變慢了。
結論：因為沒有做到多次的資料搬移，所以用指標取代的效益沒有出現。
#### `v1.1` `append` 加速
對 `append` 做瘦身：一次 `malloc` 好所需的大小再切割為兩塊。
```c
entry *append(char lastName[], entry *e)
{
e->pNext = (entry *)malloc(sizeof(entry) + sizeof(content));
e = e->pNext;
e->contentPtr = (content *)(((uint8_t*)e) + sizeof(entry));
strcpy(e->lastName, lastName);
e->pNext = NULL;
return e;
}
```
結論：`append` 的速度跟之前差不多了。
### `v2a` Memory Comparison
想法：將 char 的 16 次比較降為 int 的 4次比較。
避免 `'\0'` 之後的雜訊，再 `mallc` 前，先清空記憶體。
```c
memset(e->lastName, 0, sizeof(char) * MAX_LAST_NAME_SIZE);
strcpy(e->lastName, lastName);
```
考慮到 branch prediction，放棄使用`if(a[0]==b[0] && a[1]==b[1]...)`，而改用`memcmp`。
結論：沒差。
### `v2b` Trie
先重構 `main.c,phonebook_orig.{h,c}` 將 initial, free 寫成函式.
將 Key (lastName) 建構一顆 Trie，而 Value 則是 Sturct content。
結論：建構超慢(0.29xxx)，搜索超快(0.0000)，重構測試加多單一測試時的搜索次
數。
### 重構實驗
- 把 I/O 時間提出，純測 `append` 的時間。
```c
for(n = 0; fgets(last_name_record[n], sizeof(char) * MAX_LAST_NAME_SIZE, fp); n++) {
i = 0;
while(last_name_record[n][i] != '\0')
i++;
last_name_record[n][i - 1] = '\0';
}
```
```c
clock_gettime(CLOCK_REALTIME, &start);
for(i = 0; i < n; i++)
e = append(last_name_record[i], e);
clock_gettime(CLOCK_REALTIME, &end);
```
- 將搜索次數提高到 1% * 資料數
```c
int test_num = max(n / 100, 1);
int *test_array = (int *) malloc(sizeof(int) * test_num);
for(i = 0; i < test_num; i++)
test_array[i] = rand() % n;
```
```c
clock_gettime(CLOCK_REALTIME, &start);
for(i = 0; i < test_num; i++)
assert(NULL != findName(last_name_record[test_array[i]], e));
clock_gettime(CLOCK_REALTIME, &end);
```
結論：測的出 Trie 的效益，但單一測試的 orig 會跑很久。
```
size of entry : 136 bytes
execution time of append() : 0.052206 sec
execution time of findName() : 27.529620 sec
```
```
size of entry : 216 bytes
execution time of append() : 0.255502 sec
execution time of findName() : 0.002327 sec
```
單一測試下，Linked-List / Trie 的搜索時間複雜度為：
Linked-List: O(L) * O(N)
Trie: O(L)
Sign in with Wallet
Connect another wallet