2018q1 Homework 3 ( List )

contributed by <ryanpatiency>

實作測試程式，批次建立包含若干大小的 linked list，隨機放入數值為介於 1 到 365 之間 (包含) 的節點 (代表 day number) ，至少應該涵蓋 10¹, 10², 10³, … 10⁶ 等數量，透過前述的 insert, quick, merge sort 進行排序，分析執行時間並解讀其行為

看到這麼小的上限，我忍不住做了一個 counting sort

Counting sort 是典型空間換時間的演算法，您現在很明確的測試出了效率上的差異，那要不要也比對一下空間上的消耗差異呢？
BodomMoon

• 檢驗的程式碼：

#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);
    }
}

• 執行結果：
  
  去掉 insertion sort: ( too slow )
  
  去掉 qsort
  

承上，設計 deduplication 程式，將上述輸入中的數值挑出重複的節點並與刪除，透過統計分析，解讀執行時間分佈，以及探討 data deduplication 的效益

• 我的做圖
  

  轉換成時間分佈