Try   HackMD

2020q1 第 1 週隨堂測驗解題思路

contributed by < ryanwang522 >

完整測驗題目描述

測驗 1

定義了一個單向 linked list:

typedef struct __list {
    int data;
    struct __list *next;
} list;

在不存在環狀結構的狀況下，以下函式能夠對 linked list 元素從小到大排序:

list *sort(list *start) {
    if (!start || !start->next)
        return start;
    list *left = start;
    list *right = left->next;
    LL0; /* 待補 */

    left = sort(left);
    right = sort(right);

    for (list *merge = NULL; left || right; ) {
        if (!right || (left && left->data < right->data)) {
            if (!merge) {
                LL1; /* 待補 */
            } else {
                LL2; /* 待補 */
                merge = merge->next;
            }
            LL3;
        } else {
            if (!merge) {
                LL4; /* 待補 */
            } else {
                LL5; /* 待補 */
                merge = merge->next;
            }
            LL6;
        }
    }
    return start;
}

思考過程

理解 recursive function

  • 首先，可以看到 sort 是一個遞迴函式，這個遞迴的終止條件是：只要輸入的 linked list (以下簡稱 list) 為空或是只有一個元素，就返回自己。

    • 如果為空，return NULL，代表 empty list
    • 如果 start != NULL，且 start->next == NULL，代表只有一個元素存在在該 list，返回他自己。
    • 上述兩個 base case 回傳的都是一串排序好的 list（單一元素或空串列，本身就是排序好的）。

  • 注意 sort 這個函式一旦回傳，回傳的就是一串排序好的 list

    • 所以接下來看到 left 和 right，想到的是將 list 拆成兩個部分
    • 馬上聯想到 merge sort，但看一下後面的實作並沒有將 list 拆成等長的兩部分，感覺不是 不同於預期。

      理工人應避免在報告中提及「感覺」，這不是文學創作，是分析推論和系統開發!

      Image Not Showing Possible Reasons
      • The image file may be corrupted
      • The server hosting the image is unavailable
      • The image path is incorrect
      • The image format is not supported
      Learn More →
      jserv

      • 再從 LL0 的選項中看到 left->next = NULL;，如果是此選項的話就代表每次都把 list 最左邊的元素獨立出來，再分別對左右兩個 list 遞迴呼叫，先假設是這樣，繼續往下看。
      ​​​​LL0 => left->next = NULL
    • 接下來是對左右遞迴呼叫
      • 這裡比較好想的想法是假設輸入是一個長度為 2 的 list，left right 回傳後就分別指向 list 的第一個跟第二個元素。
      • 若是長度大於 2 的情況下，left 就指向由輸入 list 最左邊第一個元素所構成的 sublist，right 則指向由剩下的元素所構成的 sublist 的開頭，並且right = sort(right) 回傳後，right 就是 已經排序好的

  • 接者的問題就變成 – 要怎麼 combine left、right 兩個 sublist 成為一個一樣是由小到大的 list， 並且讓 start 指向該 sorted list 的開頭。

    • 想到這裡，合理猜測是 Insertion sort 的 linked list 版本
      • 每次都把 left 的單一個元素 insert 到 sorted right list 裡面，不一樣的是從右到左，而不是習慣的從左到右

分析 for-loop

  • left、right 分別指向左右兩個 sublist，且 right 是排序好的(right->data 是 right list 中的最小值)，從其各自所指向的值來看，根據三一律，以下分成三種情況討論，來推測實作應該長怎樣：

    • left->data < right->data

      • line12 的 if 敘述條件為真，並且一開始 merge 為 NULL –> 進入 LL1、LL3
      • 思考時間到！此時 list 有兩個元素而且已經知道 left 是最小了，所以～把要回傳的開頭 start 指向最小元素才是 LL1 合理的選項。加上 merge 為 NULL 才進來 LL1 的目的猜測是要初始化 merge，選擇
      • start = left;
      • [x]start = merge = left;
      • 針對 LL3，選項 (c) (d) 沒有意義，且 left 已經被 merge 所暫存，合理選擇

      left = left->next;

    • left->data = right->data

      • line12 的 if 敘述條件為 false，並且一開始 merge 為 NULL –> 進入 LL4、LL6
      • 此時左右的最小值相同，start 指向左右都是合理選項，先跳過

    • left->data > right->data

      • line12 的 if 敘述條件為 false，並且一開始 merge 為 NULL –> 進入 LL4、LL6
      • 此時 right 指向左右 list 中的最小，start 應該指向 right，和 LL1 同理，選擇
      • start = right;
      • start = merge = right;
      • 和 LL3 同理，選擇

      right = right->next;

  • 從上面 left->data < right->data 之後繼續推理，此時 left 為 NULL，merge 和 start 指向原本的左串列，right 依然指向右串列開頭 (注意left right 其中之一不為空，迴圈繼續)

    • 此時 line12 的 if 條件皆不成立 –> 進入 LL5 LL6
      • 因為原本左邊的值比右邊排序好的串列的最小（開頭）還要更小，所以這時應該把 merge 所指的 node 連接到 right 的開頭，因此選擇

      merge->next = right;

      • 並且執行 LL6 right = right->next
      • 在這之後 right 跟 merge 就會不斷右移直到 right 跑到最末端指向 NULL，此時 left right 都為空，跳出迴圈 return 排序好的串列給上一層呼叫。

  • 從上面 left->data >= right->data 之後繼續推理，此時 left 依然指向左元素，merge 和 start 指向原本的右串列的最小，right 指向右串列的下一個元素

    • 此時看 line12
      • 如果右邊串列還沒走到底，!right 為 false
        • if 後半部條件成立 (e.g. left:6, right:4->7) –> LL2 LL3
          • LL2 : 把 left 指到的 node 插在 merge 後 right 之前
          • LL3 : left 指向 NULL
        • if 後半部條件不成立 (e.g. 左元素已經放置完了，但 right 還沒走到底) –> 透過 LL5 LL6 持續平移直到 right 走到底
          • 這裡就是可以改善的地方！
      • 如果右邊串列走到底了（right 指到 NULL），!right 為真 –> LL2 LL3
        • LL2 : 把 left 指到的 node 插在 merge 後 right 之前
        • LL3 : left 指向 NULL

follow-up questions

解釋上述程式運作原理

list *sort(list *start) {
    if (!start || !start->next)
        return start;
    list *left = start;
    list *right = left->next;
    left->next = NULL; // partition input list into left and right sublist

    left = sort(left); // list of single element is already sorted
    right = sort(right); // sorted right sublist

    // insertion until the two sublists both been traversed
    // merge is always infront of the insertion position
    for (list *merge = NULL; left || right;) {
        // right list hasn't reach the end or
        // left node has found its position for inserting
        if (right == NULL || (left && left->data < right->data)) {
            if (!merge) {
                // start points to the node with min value
                // merge starts from min value
                start = merge = left; // LL1
            }
            else {
                // insert left node between merge and right point to
                merge->next = left; // LL2
                merge = merge->next; 
            }
            left = left->next; // LL3
        }
        else {
            if (!merge) {
                start = merge = right; // LL4
            } else {
                // shift until right == NULL or
                // inset merge(=left) in front of right when min is in left sublist
                // (LL1->LL5-> shift until right == NULL)
                merge->next = right; // LL5
                merge = merge->next;
            }
            right = right->next; // LL6
        }
    }
    return start;
}

擴充為 circular doubly-linked list 並重新實作對應的 sort

  • 定義 circular doubly-linked list 的節點資料結構
typedef struct __list {
    int data;
    struct __list *next;
    struct __list *prev;
} list;

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

  • 一些 utilization functions
/* push a new node to the head of the list */
void push(list **head_ref, int data) {
    list *new_head = malloc(sizeof(list));
    new_head->data = data;

    if (!*head_ref) {
        // the list is empty, create a single node
        new_head->next = new_head->prev = new_head;
        *head_ref = new_head;
        return;
    }

    list *last = (*head_ref)->prev;
    new_head->next = *head_ref;
    new_head->prev = last;
    last->next = (*head_ref)->prev = new_head;
    *head_ref = new_head;
    return;
}

void print(list *head, bool newline) {
    list *curr = head;
    if (!curr)
        printf("The linked list is empty!\n");

    while (curr->next != head) {
        printf("%d ", curr->data);
        curr = curr->next;
    }
    printf("%d ", curr->data);
    if (newline)
      printf("\n");
}

  • 要注意的是，新增一個新節點到一串 list 的最前面 (e.g. push) 跟插入一個新節點到一串 list 的中間 (e.g. insert)，兩著的實作是不一樣的

    • 在原本的版本中 LL2、LL5 其實是不同概念，只是實做起來剛好寫法相同

  • 根據原本的程式邏輯，實作 circular doubly-linked list 由右到左的 insertion sort

    • 想法相同，每一次呼叫都把長度 n 的 input 切成左右兩個 sublists 長度分別為 (1, n-1)。
    • 處理插入的邏輯也跟上述相同，但由於資料結構的不同，有些寫法需要替換
list *sort(list *start) {
    // check if input contains only 0/1 node, 
    if (!start || start->next == start)
        return start;

    list *left = start;
    list *right = left->next;
    
    // one element in left list
    left->next = left; 
    // tail element's next point to the begin of right
    left->prev->next = right; 
    // right head's prev point to the tail element
    right->prev = left->prev; 
    // one element in left list
    left->prev = left;

    left = sort(left);
    right = sort(right);

    // insert to the sorted right list
    // loop until all elements are traversed
    for (list *merge = NULL; left || right != start;) {
        // right list hasn't reach the end (go back to the head of sorted list) or
        // left node has found its position for inserting
        if (right == start || (left && left->data < right->data)) {
            if (!merge) {
                start = merge = left;
            } else {
                // merge is among right list
                // insert left node after the node pointed by merge
                left->prev = merge;
                left->next = merge->next;
                merge->next = left;
                left->next->prev = left;
                // shift merge pointer
                merge = merge->next;
            }
            left = NULL; // LL3
        } else {
            if (!merge) {
                start = merge = right;
            } else {
                // when merge points to the left element
                // (left sublist contains only one element)
                if (merge == merge->next) {
                    // push merge on to right's head
                    merge->next = right;
                    merge->prev = right->prev;
                    right->prev->next = merge;
                    right->prev = merge;
                }
                // shift merge pointer
                merge = merge->next;
            }
            right = right->next;
        }
    }
    return start;
}
  • 最後簡單的測試一下，隨機產生 100 個長度為 10 的陣列，跟 qsort 的結果比較。
bool test(list *head, int* ans, int len) {
    list *curr = head;
    if (!curr) {
        printf("The linked list is empty!\n");
        return false;
    }
    
    qsort(ans, len, sizeof(int), cmp);
    curr = sort(head);

    int i = 0;
    while (i < len) {
        if (curr->data != ans[i]) {
            return false;
        }
        curr = curr->next;
        i++;
    }
    print(curr, false);
    return true;

}

int main() {
    int correct = 0;
    srand(time(NULL));
    for (int i = 0; i < 100; i++) {
        int testcase[10] = {0};
        for (int j = 0; j < 10; j++)
            testcase[j] = rand() % 50;
        
        list *head = NULL;
        for (int j = 9; j >= 0; j--)
            push(&head, testcase[j]);
        printf("Testcase %d: ", i+1);
        print(head, false);
        printf(" --> ");
        if (test(head, testcase, 10))
            correct++;
        list_free(&head);
        printf("\n");
    }
    printf("%d/100 passed.\n", correct);

    return 0;
}
  • 測試結果
Testcase 1: 22 36 43 33 7 26 31 1 27 35  --> 1 7 22 26 27 31 33 35 36 43 
...
Testcase 99: 12 26 47 17 47 17 49 21 1 23  --> 1 12 17 17 21 23 26 47 47 49 
Testcase 100: 17 37 31 0 10 21 21 14 40 1  --> 0 1 10 14 17 21 21 31 37 40 
100/100 passed.

依循 Linux 核心 include/linux/list.h 的實作

了解 Linux kernel list.h

首先，先找到 list.h 本人， 裡面定義了 list_head 的結構

struct list_head {
    struct list_head *next, *prev;
};

它的作用是拿來串接自己定義的結構 (i.e. 作為該 struct 其中一個 member)。
以 quiz1 作為例子，在結構中增加一個型態為 list_head 的變數，如下：

typedef struct Node {
    int data;
    struct list_head list_h;
} Node;

接著，我們可以利用以下的 macro，初始化一個 list_head ，用來代表一串 linked-list 的開頭。

LIST_HEAD(list_start)
// struct list_head list_start = { &(list_start), &(list_start) };

把 macro 替代後發現

  • LIST_HEAD 是拿來宣告一個 list_head 型態的變數，並且進行初始化，將他的 prev、next 都指向自己。
#define LIST_HEAD_INIT(name) \
    {                        \
        &(name), &(name)     \
    }

#define LIST_HEAD(name) \
    struct list_head name = LIST_HEAD_INIT(name)

static inline void INIT_LIST_HEAD(struct list_head *list)
{
    list->next = list;
    list->prev = list;
}

接著來嘗試利用 list.h 提供的函式實作 push() ，將一個新的 node 串接到目前 linked-list 的開頭。

typedef struct list_head list_head;
void push(list_head list_start, int data)
{
    Node *tmp = malloc(sizeof(Node));
    tmp->data = data;
    INIT_LIST_HEAD(&(tmp->list_h));
    list_add(&(tmp->list_h), head_ref);
}

其中 list_add 函式在 list.h 中定義如下

  • 先看 __list_add()，他會將一個新的 node 串接 prev、next 兩個節點之間
  • 而 list_add 則是呼叫 __list_add(new, head, head->next);
    • 實作中將 new 這個 node 插入到當前的 head、head->next之間
    • 想反地，如果要插入尾端呢？利用 Circular linked list 特性其實很簡單
      • 透過 __list_add(new, head->prev, head);
/*
 * Insert a new entry between two known consecutive entries.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */
static inline void __list_add(struct list_head *new,
                              struct list_head *prev,
                              struct list_head *next)
{
    if (!__list_add_valid(new, prev, next))
        return;

    next->prev = new;
    new->next = next;
    new->prev = prev;
    prev->next = new;
}

/**
 * list_add - add a new entry
 * @new: new entry to be added
 * @head: list head to add it after
 *
 * Insert a new entry after the specified head.
 * This is good for implementing stacks.
 */
static inline void list_add(struct list_head *new, struct list_head *head)
{
    __list_add(new, head, head->next);
}

看到這裡，簡單做了一些摘要

  • 透過 LIST_HEAD(list_start) 可以宣告一個 list_head 型態的變數並初始化，代表一串 list 的起始點
  • 而這個 list_start 由於是 list_head 型態，代表它其實是一個 dummy head，不存資料
    • list_start->next 表示第一個元素
    • list_start->prev 表示最後一個元素
list_start --> 1 --> 3 --> 5 ---
(不存data)                      |
    ^                          |
    |                          |
    ----------------------------

如何遍歷

假設我們有一串 Node 型態的資料，每一個都透過各自結構中的 list_head 中的 prev、next 互相串聯，如果我們想遍歷這串 list，很直覺的用 for-loop:

list_head *curr;
list_head *head = &list_start;

for (curr = head->next; curr != &head; curr = curr->next) {
   ...
}

接著遇到了一個問題，要怎麼從 list_head 型態的 curr 取得當前所屬 Node 結構中的 data 呢？接著我看到了一個 macro

/**
 * list_entry - get the struct for this entry
 * @ptr:	the &struct list_head pointer.
 * @type:	the type of the struct this is embedded in.
 * @member:	the name of the list_head within the struct.
 */
#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

從註解上來看，container_of 透過當前的 list_head 指標 (e.g. curr)，回傳一個指向 curr 所屬的結構的 pointer，示意圖如下：

#define container_of(ptr, type, member) ({                      \
        const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
        (type *)( (char *)__mptr - offsetof(type,member) ); })
        
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

一個部分一個部分來看：

  • gcc extension – Statements in Expressions

    • 根據 gcc 的 online doc，{} 的回傳值為最後一個 expression。

    The last thing in the compound statement should be an expression followed by a semicolon; the value of this subexpression serves as the value of the entire construct.

    • 舉例來說 int x = ({1; 2;}) + 3;，x 的值為 2 + 3 = 5

  • Referring to a Type with typeof

    • 根據 gcc 的 online doc，它可以以某一個變數的型態來宣告另一個變數

    typeof (*x) y; declares y with the type of what x points to.

  • Zero Pointer Dereference

    • ((Node *)0)->list ，segmentation fault
    • printf("%zu\n", (size_t) &((Node *)0)->list)，因為有 address-of 運算子的關係，這段程式碼可以正常執行，回傳 list的這個 member 在 Node 結構中從起始位置到他的位址 offset。

透過 list_entry(ptr, type, member) 將遍歷得到的 curr 減去他在 Node 結構中的 offset，就能得到該指向當前結構的指標。

因此現在我們能夠透過 list_head 結構成員遍歷整個 list，並取得結構中的 data。

實作 quiz 中的 sorting algorithm

邏輯相同，先將 list 切成左右部分，把 left 插入到排序好的 right 中正確的位置。

  • 由於實作中需要 include list.h，於是我稍微改寫 include/linux/list.h ，使其成為可以在 userspace 下使用的標頭檔，可參考 Github 中的 list.h。
void sort(list_head *start) {
    // check if list is empty or contains only 1 element
    if (list_empty(start) || start->next == start->prev)
        return;
    
    // initialize left list and perform partition
    LIST_HEAD(new_start);
    list_head *left = &new_start;
    list_cut_position(left, start, start->next);
    list_head *right = start;

    // recursivly sort
    sort(left);
    sort(right);

    // insertion 
    list_head *merge;
    int left_data = list_entry(left->next, Node, list)->data;
    // find the position for insertion
    list_for_each(merge, right)
        if (left_data < list_entry(merge, Node, list)->data)
            break;
            
    // merge is pointing to the first element bigger 
    // than the data in left list.
    // Note that left is a dummy head
    // __list_add(left->next, merge->prev, merge)
    list_add_tail(left->next, merge);
    INIT_LIST_HEAD(left);
    return;
}

對不同實作進行封裝

因為有三種不同的 sorting 實作 (i.e. singular、doubly、list.h)，避免 main 充斥著 if-else， 所以我定義了一個函式介面，對主要的幾個函式進行封裝，並且在sort_orig.c、sort_dbly.c、sort_kernel_list.c 中對各自函式進行實作，最後在 main.c 中，在執行時期才透過 argument 參數決定要執行哪一個實作。

  • 節點結構

    • singular、doubly，singular linked-list 實作只用到 next
    ​​typedef struct __list {
​​  int data;
​​  struct __list *next;
​​  struct __list *prev;
​​} list;
    • list.h
    ​​typedef struct Node {
​​  int data;
​​  struct list_head list_h;
​​} Node;

  • sort.h

    • 因為 list.h 中節點結構跟前兩個差異太多，所以主要函式的參數及回傳值都運用 void * 統一
#ifndef _SORT_H
#define _SORT_H

#include <stdbool.h>

typedef struct __list {
    int data;
    struct __list *next;
    struct __list *prev;
} list;

/* for qsort */
extern int cmp(const void *a, const void *b);

typedef struct __INTERFACE {
    void *(*initialize)();
    void (*push)(void **head_ref, int data);
    void (*print)(void *head, bool new_line);
    void *(*sort)(void *start);
    bool (*test)(void **head_ref, int *ans, int len, struct __INTERFACE *sorting);
    void (*list_free)(void **head);
} Sorting;

extern Sorting orig_sorting;
extern Sorting dbly_sorting;
extern Sorting kernel_list_sorting;

#endif
  • sort_kernel_list.c
...
static LIST_HEAD(list_start);
static void *init()
{
    return (void *)&list_start;
}

static void print(void *start, bool newline)
{
    Node *curr_node;
    list_for_each_entry(curr_node, (list_head *)start, list_h)
        printf("%d ", curr_node->data);
    if (newline)
        printf("\n");
}

static void push(void **head_ref, int data)
{
    ...
}

static void *sort(void *start)
{
    if (list_empty(start) || ((list_head *)start)->next == ((list_head *)start)->prev)
        return start;
    
    LIST_HEAD(new_start);
    list_head *left = &new_start;
    list_cut_position(left, (list_head *)start, ((list_head *)start)->next);
    list_head *right = (list_head *)start;

    left = sort(left);
    right = sort(right);

    // insertion 
    struct list_head *merge;
    int left_data = list_entry(left->next, Node, list_h)->data;
    list_for_each(merge, right)
        if (left_data < list_entry(merge, Node, list_h)->data)
            break;
    list_add_tail(left->next, merge);
    INIT_LIST_HEAD(left);
    return right;
}

static void list_free(void **head_ref)
{
    ...
}

static bool test(void *head, int* ans, int len, Sorting *sorting) 
{
    ...
}

Sorting kernel_list_sorting = {
    .initialize = init,
    .push = push,
    .print = print,
    .sort = sort,
    .test = test,
    .list_free = list_free,
};
  • main.c
...
Sorting *impl_provider[] = {
    &orig_sorting,
    &dbly_sorting,
    &kernel_list_sorting,
};

int main(int argc, char *argv[])
{
    assert((argc == 2) && "Usage: ./sorting impl_selector");
    assert((atoi(argv[1]) < 3) && "Can't find impl");
    Sorting *sorting_impl = impl_provider[atoi(argv[1])];
    int correct = 0;
    srand(time(NULL));
    for (int i = 0; i < 100; i++) {
        int testcase[10] = {0};
        for (int j = 0; j < 10; j++)
            testcase[j] = rand() % 50;
        
        void *head = sorting_impl->initialize();
        
        for (int j = 9; j >= 0; j--) 
            sorting_impl->push((void **)&head, testcase[j]);

        printf("Testcase %d: ", i+1);
        sorting_impl->print(head, false);

        printf(" -->  ");
        if (sorting_impl->test(&head, testcase, 10, sorting_impl))
            correct++;
        sorting_impl->list_free((void **)&head);
        printf("\n");
        
    }
    printf("Testcases %d/100 passed.\n", correct);

    return 0;
}
  • 指出程式改進空間，特別是考慮到 Optimizing merge sort;
  • 依循 Linux 核心 include/linux/list.h 程式碼的方式，改寫上述排序程式
  • 嘗試將原本遞迴的程式改寫為 iterative 版本

References

Doubly Circular Linked List
Linux kernel list efficient generic linked-list
magical container_of macro

Last changed by 
 
Ryan Wang
1
6359

Read more

2020q1 Homework3 (quiz3)

contributed by &lt; ryanwang522 &gt; &#x6E2C;&#x9A57;&#x984C;&#x76EE;&#x63CF;&#x8FF0; GitHub &#x6E2C;&#x9A57; 1 &#x9019;&#x984C;&#x662F;&#x63A2;&#x8A0E; XOR linked list &#x7684;&#x64CD;&#x4F5C;&#xFF0C;&#x5176;&#x5BE6;&#x4E3B;&#x8981;&#x5C31;&#x662F;&#x5229;&#x7528; XOR &#x7684;&#x904B;&#x7B97;&#x7279;&#x6027;: $A \oplus A = 0$ $A \oplus 0 = A$

Mar 30, 2020
Read more from Ryan Wang
Published on HackMD