# 資料結構效能比較
程式碼github連結：https://github.com/Darth-Phoenix/HW2-Data_Structure
## 測試環境
| 作業系統 | CPU | RAM |
| :--------- | :------------------------------------------------------- | :------ |
| Windows 10 | Intel(R) Core(TM) i5-1035G1 <br />CPU @ 1.00GHz 1.19 GHz | 12.0 GB |
## 資料集(-d N, -q M)
### 1.建立隨機亂數(-d N)
#### 概念：
為了達到不重複的測資，這裡用交換法，類似於洗牌的概念。先把一個陣列的值設定成跟他的索引值相同(a[0]=0, a[1]=1...)，接著如果要產生n個不重複的亂數，我就把陣列的前n項個別跟陣列裡面隨機一個值交換。交換完以後陣列前n項就是所需不重複的隨機亂數。
下面的程式亂數只取0~1e8，因為使用這種方法如果亂數的範圍有n個值，就要開一個大小為n的陣列，因此如果取亂數的範圍越大，相對就要付出越多的空間。我的電腦如果取0~int最大值就會產生segmentation fault，所以就取到1e8。
#### 程式碼：
```c
#define MAX_NUM 100000000
int a[MAX_NUM];
int *rand_data(int n){
for (int i=0; i<MAX_NUM; i++){
a[i]=i;
}
srand(time(NULL));
int *list, num, temp;
list=(int*)malloc(sizeof(int)*n);
for (int i=0; i<n; i++){
num=rand()%MAX_NUM;
temp=a[num];
a[num]=a[i];
a[i]=temp;
}
for (int i=0; i<n; i++){
list[i]=a[i];
}
return list;
}
```
### 2. 查詢資料(-q M)
#### 概念：
同樣是用交換法，但這次是針對索引值交換。如果有n筆資料，要產生m筆，就是產生0~n-1的陣列，然後針對前m筆做隨機交換。最後回傳陣列的前m項即為欲查詢資料集的"索引值"。把前面建立的隨機亂數陣列對回傳的索引值陣列加上中括號查詢即能得到欲查詢的值。
#### 程式碼：
```c
#define MAX_NUM 100000000
int a[MAX_NUM];
int *rand_index(int n, int m){
for (int i=0; i<n; i++){
a[i]=i;
}
srand(time(NULL));
int *list, num, temp;
list=(int*)malloc(sizeof(int)*m);
for (int i=0; i<m; i++){
num=rand()%n;
temp=a[num];
a[num]=a[i];
a[i]=temp;
}
for (int i=0; i<m; i++){
list[i]=a[i];
}
return list;
}
```
## 資料結構
### Array
#### 1.建立
```c
int arr[1000000];
void arr_insert(int key, int idx){
arr[idx]=key;
return;
}
void arr_build(int n, int *num){
for (int i=0; i<n; i++){
arr_insert(num[i], i);
}
}
```
(1)因為測資最多查詢1e6，陣列大小設定為1e6。
(2)變數idx為每次輸入資料的索引值，每次輸入就讓idx加1。
(3)如此就可以高效率的讓數字一個一個填入陣列不用從頭開始尋找空位。
#### 2.查詢
```c
void arr_search(int key){
int idx=0;
while(arr[idx]!=key){
idx++;
}
return;
}
```
(1)未經過處理的array就只能使用linear search，從頭開始尋找目標值。
(2)搜尋到目標值以後則回傳，否則每次while迴圈中idx增加1後尋找下一格。
(3)因為從資料集的設計是一定找得到查詢的值，所以不用判定如果arr[idx]是空的。
### Array with Binary Search
#### 1.建立
```c
int bs_arr[1000000];
int cmp(const void *p, const void *q){
return *(int*)p > *(int*)q;
}
void bs_insert(int key, int idx){
bs_arr[idx]=key;
return;
}
void bs_build(int n, int *num){
for (int i=0; i<n; i++){
bs_insert(num[i], i);
}
qsort(bs_arr, n, sizeof(int), cmp);
}
}
```
(1)建立陣列方法和上面相同。
(2)在輸入結束後先使用qsort排序它，就可以支援binary search。
#### 2.查詢
```C
void bs_search(int key){
int upper=size;
int lower=0;
int mid;
while(upper-lower!=1){
mid=(upper+lower)/2;
if (key > bs_arr[mid]){
lower=mid;
}
else if (key < bs_arr[mid]){
upper=mid;
}
else return;
}
return;
}
```
(1)上界設定為size，size即為資料數量，即為-d N中的N；下界則設定為0。
(2)取出搜索範圍中點的元素。
(3)若小於則將左邊邊界改為中點右側，若大於則將右邊邊界改為中點左側。
(4)重覆(3)，若搜索目標和中點相等則回傳。
### Linked List
#### 1.設定節點
```c
struct lnode{
int data;
struct lnode *next;
}*LL=NULL, *prev=NULL;
```
(1)LL表示Linked List的開頭。
(2)prev則是用來記錄Linked List的尾端，用來方便輸入。
#### 2.建立
```c
void ll_insert(int key){
struct lnode *p;
p=(struct lnode*)malloc(sizeof(struct lnode));
p->data=key;
p->next=NULL;
if (LL==NULL){
LL=p;
prev=p;
return;
}
prev->next=p;
prev=p;
return;
}
```
(1)先建立(struct)一個新的節點用在後面輸入。
(2)如果Linked List是空的(NULL)，把開頭跟結尾都設定成新的節點後回傳。
(3)如果不是空的只要在prev後面連結新的節點，並更新prev的位置。
#### 3.查詢
```c
void ll_search(int key){
struct lnode *q=LL;
while(q->data!=key){
q=q->next;
}
return;
}
```
(1)Linked List沒經過處理一樣也只能用Linear Search從頭開始找。
(2)目標元素跟目前節點的data一樣的話回傳，否則搜尋下一個節點。
(3)因為從資料集的設計是一定找得到查詢的值，所以不用判定如果走到空節點。
### Binary Search Tree
#### 1. 設定節點
```c
struct tnode{
int data;
struct tnode *l_child;
struct tnode *r_child;
}*BST=NULL;
```
(1)一個節點建立(struct)一個數值、一個左節點、一個右節點。
(2)BST表示binary search tree的開頭。
#### 2.建立
```c
void bst_insert(int key){
struct tnode *p, *q=BST, *parent;
p=(struct tnode*)malloc(sizeof(struct tnode));
p->data=key, p->l_child=p->r_child=NULL;
if (BST==NULL){
BST=p;
return;
}
while (q!=NULL){
parent=q;
if (key > q->data) q=q->r_child;
else q=q->l_child;
}
if (key > parent->data){
parent->r_child=p;
return;
}
parent->l_child=p;
return;
}
```
(1)如果BST還是空的(NULL)，就建立(struct)一個新的節點並回傳它。
(2)如果大於所在節點就往它的右節點走訪，如果小於所在節點就往它的左節點走訪。
(3)重複(2)直到走訪到一個空節點(NULL)，並連結新的節點到上一個走訪的節點。
#### 3. 查詢
```c
void bst_search(int key){
struct tnode *q=BST;
while (q->data!=key){
if (key > q->data){
q=q->r_child;
}
else {
q=q->l_child;
}
}
return;
}
```
(1)如果大於所在節點就往它的右節點走訪，如果小於所在節點就往它的左節點走訪。
(2)如果查詢的值(key)等於所在節點的值(data)則回傳。
(3)因為從資料集的設計是一定找得到查詢的值，所以不用判定如果走到空節點。
### Hash
#### 1.設定節點
```c
#define TABLE_SIZE 100000
struct hnode{
int data;
struct hnode *next;
}*hash[TABLE_SIZE], *last[TABLE_SIZE];
```
(1)在Hash Table中對每一個Hash Value開一個linked list，就相當於開一個陣列的linked list。
(2)hash陣列記錄每個linked list開頭，last則記錄每個linked list中的尾端，方便輸入用。
(3)這邊實作TABLE_SIZE設定為1e5，如果設為1e6會跑比較快但是耗比較多記憶體。
#### 2.建立
```C
void hash_insert(int key, int idx){
struct hnode *p=(struct hnode*)malloc(sizeof(struct hnode));
p->data=key, p->next=NULL;
if (hash[idx]==NULL){
hash[idx]=p;
last[idx]=p;
return;
}
last[idx]->next=p;
last[idx]=p;
return;
}
void hash_build(int n, int *num){
for (int i=0; i<TABLE_SIZE; i++) hash[i]=NULL;
for (int i=0; i<n; i++){
int idx=num[i]%TABLE_SIZE;
hash_search(num[i], idx);
}
}
```
(1)先初始化hash陣列，last不用初始化因為last不會用於判斷，只需紀錄。
(2)變數idx先是用來計算hash value，然後插入對應hash value之linked list中。
(3)插入方法則和上面linked list實作相同，每次插入用linked list中的尾端(last)連結即可。
#### 3.查詢
```c
void hash_search(int key, int idx){
struct hnode *q=hash[idx];
while(q->data!=key){
q=q->next;
}
return;
}
void hash_query(int n, int *num){
int idx;
for (int i=0; i<n; i++){
idx=num[i]%TABLE_SIZE;
hash_search(num[i], idx);
}
}
```
(1)一樣用idx計算hash value，然後找尋對應hash value之linked list。
(2)每個linked list一樣只能使用linear search，找到就回傳，否則走訪下一個節點。
## 實作結果
### 1. 執行時間
#### A. 插入1e4筆、查詢1e3筆
| 資料結構 | 建立時間 | 查詢時間 |
| ------------------------ | -------- | -------- |
| Array | 33 us | 11891 us |
| Array with Binary Search | 1003 us | 108 us |
| Linked List | 222 us | 8786 us |
| Binary Search Tree | 1419 us | 168 us |
| Hash | 518 us | 13 us |
#### B. 插入1e4筆、查詢1e4筆
| 資料結構 | 建立時間 | 查詢時間 |
| ------------------------ | -------- | --------- |
| Array | 60 us | 105693 us |
| Array with Binary Search | 1314 us | 1307 us |
| Linked List | 276 us | 101529 us |
| Binary Search Tree | 1889 us | 1502 us |
| Hash | 393 us | 150 us |
#### C. 插入1e5筆、查詢1e3筆
| 資料結構 | 建立時間 | 查詢時間 |
| ------------------------ | -------- | --------- |
| Array | 682 us | 117833 us |
| Array with Binary Search | 13251 us | 161 us |
| Linked List | 3219 us | 115397 us |
| Binary Search Tree | 36339 us | 479 us |
| Hash | 5426 us | 68 us |
#### D. 插入1e5筆、查詢1e4筆
| 資料結構 | 建立時間 | 查詢時間 |
| ------------------------ | -------- | ---------- |
| Array | 438 us | 1063080 us |
| Array with Binary Search | 12332 us | 1629 us |
| Linked List | 2586 us | 933677 us |
| Binary Search Tree | 32839 us | 3295 us |
| Hash | 4006 us | 325 us |
#### E. 插入1e5筆、查詢1e5筆
| 資料結構 | 建立時間 | 查詢時間 |
| ------------------------ | -------- | ----------- |
| Array | 429 us | 10618021 us |
| Array with Binary Search | 13302 us | 14970 us |
| Linked List | 3975 us | 9299990 us |
| Binary Search Tree | 32082 us | 30979 us |
| Hash | 4558 us | 2862 us |
#### F. 插入1e6筆、查詢1e3筆
| 資料結構 | 建立時間 | 查詢時間 |
| ------------------------ | --------- | ---------- |
| Array | 5578 us | 1088790 us |
| Array with Binary Search | 146361 us | 396 us |
| Linked List | 40273 us | 1529951 us |
| Binary Search Tree | 705044 us | 820 us |
| Hash | 66371 us | 514 us |
#### G. 插入1e6筆、查詢1e4筆
| 資料結構 | 建立時間 | 查詢時間 |
| ------------------------ | --------- | ----------- |
| Array | 5221 us | 11076196 us |
| Array with Binary Search | 150832 us | 3302 us |
| Linked List | 30835 us | 15006188 us |
| Binary Search Tree | 648440 us | 9271 us |
| Hash | 64742 us | 5256 us |
#### H. 插入1e6筆、查詢1e5筆
| 資料結構 | 建立時間 | 查詢時間 |
| ------------------------ | --------- | ------------ |
| Array | 4556 us | 105890041 us |
| Array with Binary Search | 184692 us | 28297 us |
| Linked List | 33139 us | 153069209 us |
| Binary Search Tree | 692931 us | 84406 us |
| Hash | 66376 us | 42916 us |
### 2.時間複雜度
| 資料結構 | 建立n筆資料(Average) | 建立n筆資料(Worst Case) | 查詢1筆資料(Average Case) | 查詢1筆資料(Worst Case) |
| ------------------------ | -------------------- | ----------------------- | ------------------------- | ----------------------- |
| Array | O(n) | O(n) | O(n) | O(n) |
| Array with Binary Search | O(n logn) | O(n logn) | O(log n) | O(log n) |
| Linked List | O(n) | O(n) | O(n) | O(n) |
| Binary Search Tree | O(n logn) | O(n²) | O(log n) | O(n) |
| Hash | O(n) | O(n) | O(1) | O(n) |
說明：
(1) Binary Search Tree的Worst Case會發生在當每個節點都只有一個節點，也就是極度不平衡的樹。這時建立資料變成像個linked list一樣，且每次都要從頭找直到有空位才插入；搜尋效率也跟Linked List一樣是Linear Search。
(2) Hash查詢的時間複雜度會取決於陣列每個Linked List的長度，而Worst Case會發生在所有元素的Hash Value相同時，會在陣列的同一個索引值建出一個長度為n的Linked List，此時查詢效率就退化成Linear Search一樣了。
### 3.建立時間分析
#### 1.建立資料時間比較
Binary Search Tree > Array with Binary Search > Hash > Linked List > Array
這個關係其原理大概可以從上面時間複雜度的表格推得。雖然說Binary Search Tree和 Array with Binary Search建立時間比較久，但畢竟建立n筆資料的時間複雜度都是O(n logn)，所以建立時間也都不會太久。除此之外還可以發現Linked List > Array、Binary Search Tree > Array with Binary Search，其中動態記憶體配置的效能通常會略差於陣列，但優點是較容易控管記憶體。至於Hash比較特別，會和Hash Table大小相關，如果變更table size大小，上面這個關係有可能會不成立。
#### 2.建立時間與資料數關係
Array, Linked List, Hash建立n筆資料的時間複雜度為O(n)，所以當建立資料變為10倍，建立時間也大概變成10倍。而Binary Search Tree和Array with Binary Search的時間複雜度都是O(n logn)，所以時間的增加幅度就會比較大一點。值得一提的是Hash的建立時間除了與資料數量相關還會受Table Size影響，這在後面查詢時間分析會再提到。
### 4.查詢時間分析
#### 1.查詢資料時間比較
Linked List >= Array >> Binary Search Tree > Array with Binary Search
Linked List和Array都是採用linear search，因此當資料量大時，它們的查詢時間會遠大於其他方法。除此之外還可以發現Linked List > Array、Binary Search Tree > Array with Binary Search，其中動態記憶體配置的效能通常會略差於陣列，但優點是較容易控管記憶體。而Hash的查詢時間受建立資料數量和Hash Table大小影響，因此在這裡沒能找出一個大概的關係。
#### 2.建立資料數相同、查詢資料數不同
對照A, B、C,D,E、以及F,G,H可以發現當資料數相同，每當查詢資料數變為10倍，查詢時間也變為10倍。這其實不難想像，用同一個方法做同樣的事，做10遍的時間平均就是做一遍的10倍。
#### 3.建立資料數不同、查詢資料數相同
這項分析跟時間複雜度有密切的相關，也就是輸入值與處理時間的成長關係。
對照A,C,F、B,D,G、E,H，我們大概可以發現以下一些關聯：
(1)Array以及linked list的查詢時間大約都是變成10倍，其他的變動則不大。這和它們查詢一筆資料的時間複雜度O(n)有密切的相關，因為他們都是採用linear search。
(2)Array with Binary Seach以及Binary Search Tree查詢一筆資料的時間複雜度為O(log n)，因此時間增加幅度較小。
(3)Hash的查詢時間則跟建立資料數以及Hash Table大小建立資料數有關係。
- 跟建立資料數的關係（以下以table大小=1e5為例，即為我程式中的實作）：
當建立資料數是1e4以及1e5時，平均下來在陣列第一格就可以解決，不太需要用到linking的部分，因此這時查詢一筆資料的時間複雜度會比較接近O(1)，因此建立資料數1e4到1e5的查詢時間增加不多。但是當建立資料是1e6時，陣列中平均一個元素就會有10個link，這時查詢一筆資料的時間複雜度就會比較接近O(n)，因此建立資料數1e5到1e6的查詢時間大概就增加了10倍。
- 跟Hash Table大小的關係：
| Table大小 | 1e3 | 1e4 | 1e5 | 1e6 | 1e7 | 1e8 |
| ------------- | ---------- | --------- | -------- | --------- | --------- | --------- |
| 建立1e6筆時間 | 33749 us | 50784 us | 81348 us | 101174 us | 147846 us | 364619 us |
| 查詢1e5筆時間 | 4100571 us | 464278 us | 44218 us | 6420 us | 4661 us | 6414 us |
- Hash的建立方法因為是有紀錄每個節點的尾端，所以建立一筆的時間複雜度是O(1)。但會造成table大小越大，建立時間還是比較長的原因我猜測是array的大小比較大時，呼叫陣列比較大的元素就會花比較多時間。
- Hash的查詢方法是先找到陣列的索引值再從linked list從頭開始linear search，因此查詢時間大約和linked長度成正比。當table大小為1e3，平均陣列一個元素有1000個link，當大小為1e4，平均陣列一個元素有100個link，因此時間大約變成1/10。但當table大小比較大像是1e6~1e8，因為平均陣列一個元素都小於1個，因此不太需要linking，此時查詢一個資料的時間複雜度接近O(1)，因此1e6~1e8的查詢時間差不多。
- 雖然1e6~1e8的查詢時間都很短，但相對就要耗比較多記憶體。
## 總結
先不提Hash，在Array, Array with Binary Search, Linked List, Binary Search當中，Array和Linked List建立比較快、查詢比較慢，Binary Search和Array with Binary Search則是建立比較慢、查詢比較快。但因為Array和Linked List都是採用Linear Search，查詢一筆資料的時間複雜度是O(n)；Binary Search和Array with Binary Search建立或查詢一筆資料的時間複雜度都是O(log n)，因此Array和Linked List的整體效能還是遠差於Binary Search和Array with Binary Search。除此之外，Linked List和Binary Search Tree都是動態記憶體配置，比較能省空間，但缺點是linking的關係速度會比較慢一點。至於Hash，有很大一部分取決於設定是Hash Table大小還有建立資料數量，通常Table大小越大，查詢時間越快，但建立時間較久且耗費記憶體。因此如果Table大小設定妥當，可以在執行時間和耗費記憶體之間、還有建立與查詢資料間取得平衡。最後，每一種資料結構都還是有它的優缺點，主要還是要取決於程式中的用途。當對記憶體、速度、建立及查詢的需求不同時，可能就會適合使用不同的資料結構。
## 參考資料
https://www.techiedelight.com/insertion-in-bst/
https://www.sanfoundry.com/c-program-implement-hash-tables-chaining-with-singly-linked-lists/
https://www.itread01.com/content/1542417260.html
https://medium.com/omarelgabrys-blog/data-structures-a-quick-comparison-6689d725b3b0
https://medium.com/@maggieliao.cm04g/%E8%B3%87%E7%B5%90%E8%88%87%E6%BC%94%E7%AE%97%E6%B3%95%E7%AD%86%E8%A8%98-1-linked-list-%E8%88%87-array-%E6%96%BCo-n-%E4%B9%8B%E5%B7%AE%E7%95%B0%E6%AF%94%E8%BC%83-badbf08b17ce
Sign in with Wallet
Connect another wallet