---
tags: ryanpatiency
---
# 2018q1 Homework 3 ( List )
contributed by <`ryanpatiency`>
### 實作測試程式,批次建立包含若干大小的 linked list,隨機放入數值為介於 1 到 365 之間 (包含) 的節點 (代表 [day number](https://www.epochconverter.com/daynumbers)) ,至少應該涵蓋 10^1^, 10^2^, 10^3^, ... 10^6^ 等數量,透過前述的 insert, quick, merge sort 進行排序,分析執行時間並解讀其行為
看到這麼小的上限,我忍不住做了一個 counting sort
> Counting sort 是典型空間換時間的演算法,您現在很明確的測試出了效率上的差異,那要不要也比對一下空間上的消耗差異呢?
[name=BodomMoon]
* 檢驗的程式碼:
```clike=
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
#include "../include/list.h"
#include "../private/common.h"
#include "insert-sort.c"
#include "merge-sort.c"
#include "quick-sort.c"
#include "counting-sort.c"
#define SIZE 15
long listsort_time(int *a,
struct listitem *item,
int size,
void (*fn)(struct list_head *))
{
for (int i = 1; i < size; i++) {
item[i].i = a[i];
}
struct timespec ts1, ts2;
long diff;
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &ts1);
fn(&item->list);
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &ts2);
diff = 1000000000 * (ts2.tv_sec - ts1.tv_sec) + (ts2.tv_nsec - ts1.tv_nsec);
return diff;
}
int main()
{
int *a;
struct listitem *items;
printf("input \tinsert_sort \tqsort \tmerge_sort \tcounting_sort \n");
for (int i = 0; i < SIZE; i++) {
int array_size = 1 << i;
a = malloc(sizeof(int) * array_size);
items = malloc(sizeof(struct listitem) * array_size);
INIT_LIST_HEAD(&(items->list));
for (int i = 1; i < array_size; i++) {
a[i] = rand() % 366;
list_add(&(items[i].list), &(items->list));
}
printf("%d\t", array_size);
printf("%ld\t", listsort_time(a, items, array_size, insert_sort));
printf("%ld\t", listsort_time(a, items, array_size, quick_sort));
printf("%ld\t", listsort_time(a, items, array_size, merge_sort));
printf("%ld\n", listsort_time(a, items, array_size, counting_sort));
free(items);
free(a);
}
}
```
* 執行結果:
![](https://docs.google.com/spreadsheets/d/e/2PACX-1vR-xZkBXAdMU-u0MueKYZedYmqF_Rhypdcn1PhXV2D-Ev9kcS7kuFaKADg84BMghoWQS_A3aimdOYZ5/pubchart?oid=484534055&format=image)
去掉 insertion sort: ( too slow )
![](https://i.imgur.com/esmOLft.png)
去掉 qsort
![](https://i.imgur.com/y3FuwvJ.png)
### 承上,設計 deduplication 程式,將上述輸入中的數值挑出重複的節點並與刪除,透過統計分析,解讀執行時間分佈,以及探討 [data deduplication](https://en.wikipedia.org/wiki/Data_deduplication) 的效益
* 我的做圖
![](https://i.imgur.com/LHIuQIc.png)
轉換成時間分佈
![](https://i.imgur.com/s4I8w6Z.png)