2021q1 Homework1 (quiz1)

contributed by < AmyLin0210 >

tags: 2021q1 Linux

2021q1 第一周測驗題

解釋程式運作原理

list_add_node_t

static inline void list_add_node_t(node_t **list, node_t *node_t) {
    node_t->next = *list;
    *list = node_t;
}

將 list 接到 node_t 的後方，並將 node_t 變成新的 list head

list_concat

static inline void list_concat(node_t **left, node_t *right) {
    while (*left)
        left = &((*left)->next);
    *left = right;
}

在第二及第三行的迴圈中做的事情為，找到 left 最後方 node 的 next，並使 *left 指向那個位置

在第四行的地方，將 *left 指向 right，使得 left 與 right 連接起

當遇到 *left 指向 NULL 的狀況時，指標的指標優勢便體現出來

• 當 *left 指向 NULL 時，會直接跳出迴圈，故指標位置示意圖如下

• 在 *left = right 中直接將 *left 指向 right

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 ?  &right: &left, n);
    }

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

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

使用 quick sort 會取出一個作為比較的 pivot 值，
在這段程式碼中，將 list 的第一個 node 做為 pivot 取下，
並以他的 value 當接下來的比較基準。

在 list_add_node_t(n->value > value ? AAA : BBB, n) 中，

• 如果 n 的值比較大，將它與 right 進行連接，
• 如果 n 的值比較小，將它與 left 進行連接。

反覆對 right 與 left 這兩條 linked list 做 quick sort，
全部排序完後做將左右兩條串連起來。

• list_concat(&result, left)
  由 list_concat 的函式介紹中，可以發現若第一個參數的值指向 NULL，透過函式執行後，會直接將第一個函式的值指向第二個參數的位置。

• list_concat(&result, pivot)
  將原先的 left 與 pivot 連起

• list_concat(&result, right)
  最後再將 right 連上

測試程式中 random 結果相仿問題

有什麼證據可說明「rand() 函式使用的是亂數表」呢？工程人員說話要精準確實。
:notes: jserv

The rand function computes a sequence of pseudo-random integers in the range 0 to
RAND_MAX.
以上節錄自 ISO/IEC 9899 (a.k.a C99 Standard) 中的 7.20.2.1，由此可知 rand 函式使用了 pseudo-random integers

若按照題目給的程式碼修改編譯執行，由於 rand() 函式使用的是 pseudo-random integers，在程式執行時沒有給定不同的亂數種子，因此導致執行後結果相仿。

NOT IN ORDER : 359 966 105 115 81 255 74 236 809 205 186 939 498 763 483 326 124 706 84 1016
IN ORDER : 74 81 84 105 115 124 186 205 236 255 326 359 483 498 706 763 809 939 966 1016

在這裡我的改進方式是，加入亂數種子 srand((unsigned int)time(NULL))。
由於 time(NULL) 會回傳目前時間距離 (00:00:00 UTC, January 1, 1970) 這個時間點的秒數，所以使得程式執行後的結果不同。

非遞迴方式

參考 Optimized QuickSort — C Implementation (Non-Recursive)。

doubly-linked list

由於此連結中使用到儲存數列的資料型態為陣列，會有從陣列最後方反過來尋找比對的狀況，所以我改變我的資料型態為 doubly-linked list。

變更資料結構會造成不相容 (incompatibility)，你需要考慮到這部分的衝擊。
:notes: jserv

typedef struct __node {                   
    int value;
    struct __node *next;
    struct __node *prev;
} node_t;

我的 quick sort 程式碼：

void quicksort(node_t *head, node_t *tail, int length)
{
    if (!head)
        return;
    
    node_t *beg[length], *end[length], *L, *R;
    int i=0, piv;

    beg[0] = head;
    end[0] = tail;

    while (i >= 0) {
        L = beg[i];
        R = end[i];

        if( L != R && L && R) {
            piv = beg[i]->value;
            while (L != R) {
                while ( R->value >= piv && L != R )
                    R = R->prev;
                if (L != R) {
                    L->value = R->value;
                    L = L->next;
                } 
                while ( L->value <= piv && L != R )
                    L = L->next;
                if (L != R) {
                    R->value = L->value;
                    R->prev;
                }
            }
            L->value = piv;
            beg[i+1] = L->next;
            end[i+1] = end[i];
            end[i++] = L;
        } else {
            i--;
        }
    }
}

傳入的三個參數分別為

• head : 此 linked list 的最前端
• tail : 此 linked list 的最末端
• length : 此 linked list 共有多少數

運作邏輯:

1. 每一對的 beg 與 end 會分別對應到要比較的數列最前方與最後方，並取 beg 的值作為 piv。

2. 從 R 的地方開始向左方比較，找到第一個比 piv 值小的

3. 將 L 的數值代換成剛剛找到的比 piv 小的數 ( R 的數值 )，並將 L 向右位移一個位置

4. 從 L 的地方開始向右方比較，找到第一個比 piv 值大的數值

5. 將 R 的數值代換成剛剛找到的比 piv 大的數 ( L 的數值 )，並將 R 向左位移一個位置

6. 重複步驟 2~5 直到 L 與 R 重疊

7. 將重疊處的數值換為 piv

8. 將最左邊的數丟為下次的比較起始位置，將重疊位置丟為下次比較的最終位置

9. 將重疊部份右移一位的數丟為下次的比較起始位置，將最右端位置丟為下次比較的最終位置

10. 重複進行 1~9 直到排序完成

TODO:

1. 加上時間和空間複雜度的分析
2. 說明 Optimized QuickSort — C Implementation (Non-Recursive) 指出進一步的效能提升機會
3. 避免修改為 doubly-linked list，沿用原本的 singly-linked list 設定

:notes: jserv

singly-linked list (array 思維)

在最初改動時，由於整體思路仍無法突破 array 的思維，所以程式碼十分冗長，需要用多個變數來存取每個階段的資訊。

邏輯如下：

1. 每一對的 beg 與 end 會分別對應到要比較的數列最前方與最後方，並取 beg 的值作為 piv。

2. 從最左方的地方開始向右方比較，找到第一個比 piv 值大的

3. 將比 piovt 大的值移到 tail 後方，並把 cur 位移一格

4. 重複步驟2與步驟3，直到 cur 與 tail 重疊

5. 將 piv 與 cur 指向的值做比較

   • 假設 cur 指向的值比 piv 大，cur 所在的位置會是比較的起始位置
   • 假設 cur 指向的值比 piv 小，cur 所在的位置會是比較的結束位置

void quicksort(node_t *head, int length)
{
    if (!head)
        return;

    node_t *beg[length], *end[length], **tmp, **cur, *tail, *temp;
    node_t *cur_beg, *cur_end;
    int i=0, piv;

    /* find the tail of this liked list */
    tail = head;
    while (tail->next)
        tail = tail->next;
    beg[0] = head;
    end[0] = tail;

    while (i >= 0) {
        cur_beg = beg[i];
        cur_end = end[i];
        cur = &cur_beg;
        tail = cur_end;
        beg[i+1] = *cur;

        if( cur_beg != cur_end && cur_beg && cur_end) {
            piv = cur_beg->value;
            while (*cur != cur_end) {
                /**
                 * if the current node value is larger than value of pivot,
                 * move it to the tail.
                 **/
                while (*cur != cur_end && (*cur)->value <= piv) {
                    end[i] = *cur;
                    cur = &((*cur)->next);
                }
                if (*cur == cur_end)
                    break;

                temp = tail->next;
                tail->next = *cur;
                *cur = (*cur)->next;
                tail = tail->next;
                tail->next = temp;
            }

            /**
             * Now we have a sorted linked.
             * The right side of current node is larger than the pivot,
             * and the left side of current node is less than the pivot.
             * However we have not processed current node yet.
             * There are two condition need to be thought about:
             * 
             * - If the value of current node is larger than the pivot,
             *   the linked list should be cutted as
             *   beg - the node before current node | current node - tail
             * 
             * - If the value of current node is less than the pivot,
             *   the linked list should be cutted as
             *   beg - current node | the node after current node - tail    
             */

            if ((*cur)->value > piv) {
                beg[i+1] = *cur;
                beg[i]->value = end[i]->value;
                end[i]->value = piv;
            }
            if ((*cur)->value <= piv) {
                if( tail == *cur) {
                    beg[i+1] = *cur;
                    beg[i]->value = tail->value;
                    tail->value = piv;
                }
                else {
                    end[i] = *cur;
                    beg[i+1] = (*cur)->next;
                    beg[i]->value = end[i]->value;
                    end[i]->value = piv;
                }

            }

            end[++i] = tail;
        } else {
            i--;
        }
    }
}

singly-linked list

在上面使用 array 思維但使用 linked list 實做時遇到很多例外要處理，意識到即使可以用 linked list 來實做類似 array 的內容，但是每種不同的資料型態適合的實做並不相同。

在實做我曾經遇到的 bug 為，若是有相同的數字需要排序，那我的程式會陷入無窮迴圈。
後來發現原因是我將 pivot 和與他的數字相同的 node 放在同一邊，根據 quick sort 的運作邏輯，它會將 node 與 pivot 比較並逐次拆解，直到只剩下最後一個 node ，再慢慢依序連接回去，若將 pivot 和與它相同優先序的 node 放在同邊的話，會導致永遠無法拆解至只剩下一個 node。

在這裡我將它改寫為以下程式碼：

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

    node_t *sorted = NULL;
    node_t *stack[MAX_LENGTH] = {NULL};
    int stack_count = 0;

    stack[stack_count] = *list;

    while (stack_count >= 0) {
        if (!stack[stack_count]->next) {
            list_add_node_t(&sorted, stack[stack_count]);
            stack_count--;
            continue;
        }

        node_t *left = NULL, *right = NULL, *tmp = stack[stack_count]->next;

        list_add_node_t(&right, stack[stack_count]);
        while (tmp) {
            node_t *n = tmp;
            tmp = tmp->next;
            list_add_node_t((n->value > stack[stack_count]->value)? &right:&left, n);
        }

        --stack_count;
        if (left)
            stack[++stack_count] = left;
        if (right)
            stack[++stack_count] = right;
    }

    *list = sorted;
}

最近在看 並行和多執行緒程式設計系列講座 的教材內容，當中提到 mutex 與 semaphores 時會特別解釋在不同的意境下，就會有相對合適的實做方式，經過這幾次對 quick sort 的實做後開始強烈的意識到，不同的意境需要搭配上不同實做的重要性。

在最初的實做儲存迭代資訊時，我所儲存的都是 linked list 中的某個位置，就如同儲存陣列的 index。陣列由於連續記憶體空間的特性可以快速存取特定 index 的數值，指標卻需要一個一個的走訪，尤其是在 singly-linked list 需要存取已經走訪過得 node 時，更是顯得不便。

在最後的版本中，利用了 linked-list 可以簡單的連接 node 的特性，將需要比較的數值拆做 left 與 right 兩條 linked-list，比起使用 index 比較的思維，這個版本明顯的清晰許多。

即使相同的功能可以使用不同的實做完成，但如果能夠清晰的了解資料結構與問題本身的特性，選擇了適合的實做，在寫程式碼的過程中可以減少處理例外的狀況，易讀性也會大大提昇。