2021q1 Homework1 (quiz1)

contributed by < YOYOPIG >

tags: linux2021

TODO list

• 重新回答第 1 周測驗題並解釋原理
• Graphviz 畫出 list
• Pseudorandom number generator
• Optimized QuickSort
• linux-list
• A Comparative Study of Linked List Sorting Algorithms

程式運作原理

由各 function 名稱不難看出，這支程式主要是在實作對 Singly linked list 的 quick sort 演算法。有了大致的認知後，從 main function 開始 trace code。

main

int main(int argc, char **argv) {
    size_t count = 20;

    node_t *list = NULL;
    while (count--)
        list = list_make_node_t(list, random() % 1024);

    list_display(list);
    quicksort(&list);
    list_display(list);

    if (!list_is_ordered(list))
        return EXIT_FAILURE;

    list_free(&list);
    return EXIT_SUCCESS;
}     

main function 做的事相當簡單，先隨機產生給定數量(20)的 nodes，印出之後做 sort，再印出排序完的 list。最後，檢查排序是否成功並 free 掉資源。

quicksort

void quicksort(node_t **list)
{
    if (!*list)
        return;

    node_t *pivot = *list;
    int value = pivot->value;
    node_t *p = pivot->next;
    pivot->next = NULL;

    node_t *left = NULL, *right = NULL;
    while (p) {
        node_t *n = p;
        p = p->next;
        list_add_node_t(n->value > value ? AAA : BBB, n);
    }

    quicksort(&left);
    quicksort(&right);

    node_t *result = NULL;
    list_concat(&result, left);
    CCC;
    *list = result;
}

這支程式最主要的程式碼，我們可以看到有許多行被挖空了

只好一步一步慢慢來

首先是 Edge case 的檢查，如果傳入的值為 NULL，則直接 return，作為後續 recursive call 的中斷點。程式碼如下：

    if (!*list)
        return;

接著，取出 quick sort 演算法中的 pivot node，切開 next 指標。

    node_t *pivot = *list;
    int value = pivot->value;
    node_t *p = pivot->next;
    pivot->next = NULL;

一個一個 traverse 剩下的 nodes，比較它們的值和 pivot 的大小，分成兩堆。較大的那堆應該位在 pivot 的右邊，小的那堆位於 pivot 的左邊。因此，我們可以完成程式碼的填空，AAA應為(e) &right，BBB應為(c) &left。完整結果如下：

    node_t *left = NULL, *right = NULL;
    while (p) {
        node_t *n = p;
        p = p->next;
        list_add_node_t(n->value > value ? &right : &left, n);
    }

透過 Recursive call 分別對左堆及右堆作排序，最後依照排序好的左堆-> pivot ->排序好的右堆這樣的順序，即可完成對整個 list 的排序。因此，我們可以知道CCC應該要選(b) list_concat(&result, pivot); list_concat(&result, right)。完整結果如下：

    quicksort(&left);
    quicksort(&right);

    node_t *result = NULL;
    list_concat(&result, left);
    list_concat(&result, pivot);
    list_concat(&result, right);
    *list = result;

list_concat

static inline void list_concat(node_t **left, node_t *right) {
    while (*left)
        LLL;
    *left = right;
}

透過程式名稱不難猜出他的功用應該是把兩個 list 串接起來。我們只要找到 left list 的最後一個 node，把該 node 的 next 指向 right list 的 head 即可。因此這裡LLL應該要選(c) left = &((*left)->next)

Pseudo Random generator

根據 GNU C Library 文件說明，要修正輸出結果相仿的問題，可以透過給定不同的 seed value來達成。最常見的作法，便是使用執行程式當下的時間作為選擇 seed 的依據。

int getRandom() {
    srand(time(NULL)); 
    return rand();
}

Optimized quicksort

在這份實作中，利用了 recursive 的形式。儘管程式可讀性不錯，但在反覆的 function call 時，效能相對較差，且需要存大量的資料進 stack，資料量大時可能會有 overflow 的可能。因此，這篇文章指出，可以試著改寫成 iterative 的形式。參考該篇文章的範例程式，改寫成下面這樣：

node_t *getNode(node_t *head, int cnt) {
    node_t *cur = head;
    while(cnt>0)
    {
        cur = cur->next;
        cnt--;
    }
    return cur;
}

void quickSort(node_t *head, int elements) {

  #define  MAX_LEVELS  1000

  int  piv, beg[MAX_LEVELS], end[MAX_LEVELS], i=0, L, R ;
  node_t *pivot;

  beg[0]=0; 
  end[0]=elements;
  while (i>=0) {
    L=beg[i];
    R=end[i]-1;
    if (L<R) {
      pivot=getNode(head, L); 
      if (i==MAX_LEVELS-1) 
        return;
      while (L<R) {
        while (getNode(head, R)->value>=pivot->value && L<R) 
            R--; 
        if (L<R) 
        {
            getNode(head, L)->value=getNode(head, R)->value;
            L++;
        }
        while (getNode(head, L)->value<=pivot->value && L<R) 
            L++; 
        if (L<R) 
        {
            getNode(head, R)->value=getNode(head, L)->value;
            R--;
        }    
      }
      getNode(head, L)->value=pivot->value;
      beg[i+1]=L+1; 
      end[i+1]=end[i]; 
      end[i++]=L; 
    }
    else
      i--;
  }
  return; 
}

注意，這份程式尚未優化完全，getNode 真的是個爛到爆的寫法

主要是先搞懂 iterative 的邏輯(Recursive在可讀性上真的完勝)，附上網站截下原作者的說明圖以供參考

進一步優化的方法可以考慮 pointer to pointer、用 array 存取每個 item 的位置等。若 data structure 改為 doubly linked list，在尋找 node 的過程或許也會比較輕鬆，視真實使用情境(資料種類、資料量等)再選擇適合的優化。