Try   HackMD

2020q1 Homework3 (quiz3)

contributed by < Hsuhaoxiang >

2020q1 第三週測驗題 解題思路

測驗 1















































list *sort(list *start)
{
    if (!start || !start->addr)
        return start;

    list *left = start, *right = start->addr;
    left->addr = NULL;
    right->addr = XOR(right->addr, left);

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

    for (list *merge = NULL; left || right;) {
        if (!right || (left && left->data < right->data)) {
            list *next = left->addr;
            if (next)
                next->addr = XOR(left, next->addr);

            if (!merge) {
                start = merge = left;
                merge->addr = NULL;
            } else {
                merge->addr = LL1;
                left->addr = LL2;
                merge = left;
            }
            left = next;
        } else {
            list *next = right->addr;
            if (next)
                next->addr = XOR(right, next->addr);

            if (!merge) {
                start = merge = right;
                merge->addr = NULL;
            } else {
                merge->addr = RR1;
                right->addr = RR2;
                merge = right;
            }
            right = next;
        }
    }

    return start;
}

XOR linked list

本題與第一週極為相似，重點在於要看懂每個 node 的連結方式，除了頭尾的每個 node 都可以藉由與指向上個 node 的 pointer 以及自己本身的 addr 做 XOR 得到下個節點的位置，同樣地如果擁有指向下個 node 的 pointer 便可以與自己的 addr 做 XOR 得到上個節點的位置，那頭尾的 addr 要放什麼呢？如果是 list 的 head 要指出下一個節點的位置就要將 head 前一個節點 NULL 與 addr 做 XOR ，而 NULL 轉型為 uintptr_t 其內含值仍是 0，根據

A⊕0=A ，我們只需要放下一個 node 的記憶體位置即可，至於如果是一個 list 的 tail 則只要放上一個 node 的記憶體位置。藉由此技巧我們就能在降低空間使用量的情況下實作雙向的 linked list。







xor_linked_list



a

12

B



b

99

A XOR C



a:c->b:data






b->a:ref






c

37

B XOR D



b:ref->c:data






c->b:ref






d

35

C



c:ref->d:data






d->c:ref

如上圖假設 node 的記憶體位址依序為 A 、 B 、 C 、 D , 則 head 在 addr 只要放下個節點的記憶體位址與 0 (NULL) 做 XOR 還是 得到下個節點的位置 B ，而對於第二個節點需要上個節點的記憶體位址也就是 A 便可得到

(A⊕C)⊕A=C ，對於 tail 與 head 相同只需要放上一個節點的記憶體位置 C 就好了。

解題思路

LL1 = ?

從第 13 行的 for loop 可以看出這段和第一週測驗題一樣是在 merge 左右兩邊已經 sort 好的 xor linked list，如果第一個判斷式 !right || (left && left->data < right->data) 成立的話，要 merge 的點就會是 left 的 head ， list *next = left->addr 由於 left 為 head addr 即為下個 node 的位置不必經過 XOR 運算，而 next 若不為 NULL (如果 list 只有單一節點他的 addr 放的會是 NULL) 原本的 left head 將會被合併到正在排序的 list 所以這個 next 會成為新的 head 故我們必須更新他的 addr ，也就是只需要放下個 node 的記憶體位置利用與前一個節點記憶體位置和現在的 addr 便是next 新的 addr 的值，也就是 next->addr = XOR(left, next->addr)。再來我們需要知道 merge 這個變數，他是指著正在合併的 list 的 tail

所以第一題 merge->addr = LL1 ，我們便可以知道需要將尾巴再加上現在要合併的點left 的 head 所以答案刪到只剩 (d) (h)，那我們知道既然 merge 是正在合併的 tail 那他的 addr所放的就會是他的上一個 node 的記憶體位置，我們必須讓 addr 的值變成 上個 node 與 下個 node 的記憶體位置的 XOR。

答案為 (h) XOR(merge->addr, left)

LL2 = ?

left->addr = LL2將會是正在合併的 list 的 tail 只要放上一個節點的記憶體位置就好了，

答案為 (c) merge

LL3 & LL4 = ?

這兩題其實只是上面的題目變成 right 先合併所以只要找對稱的選項即可

LL3 = (i)XOR(merge->addr, right)
LL4 = (c)merge

延伸問題:

  1. 修改 lab0-c 裡頭的 harness.c，將原本內部使用的 doubly-linked list 換為 XOR linked list，觀察記憶體佔用率的變化，可設計頻繁的 test_malloc / test_free 呼叫交錯情境。

測驗 2

考慮以下 singly-linked list 程式:

#include <stddef.h>
struct node {
    int data;
    struct node *next;
} *head;

void insert(struct node *newt) {
    struct node *node = head, *prev = NULL;
    while (node != NULL && node->data < newt->data) {
        prev = node;
        node = node->next;
    }
    newt->next = node;
    if (prev == NULL)
        head = newt;
    else
        prev->next = newt;
}

可透過以下 pointer to pointer 改寫 insert 函式，功能等價但更簡潔，如下:

void insert(struct node *newt)
{
    struct node **link = &head;
    while (*link && AA)
        BB;
    newt->next = *link;
    *link = newt;
}

AA = ?

(a)(link)->data < newt->data
(b)*link->data < newt->data
(c)(*link)->data < newt->data
(d)**link->data < newt->data

要將list中的data值取出來故選(c)(*link)->data < newt->data (*link) 為指向目前 node 的 pointer

BB = ?

(a)link = &(*link)->next
(b)*link = *link->next
(c)(*link) = (*link)->next
(d)link = (*link)->next

因為 link 為 pointer to pointer 一開始他指著 head 也就是 (*link) 為 head 如果 選 (c)(*link) = (*link)->next head 就被改變。

答案是 (a) link = &(*link)->next

為何要用 pointer to pointer?

  • 從刪除 linked list node 看程式設計的品味
    在你所不知道的 C 語言中有提到，「有品味」(Linus 原話) 的程式碼，不管是不是 head 其實只是要將一個 node * 的指標指向他而已，如果使用 pointer to pointer 的方式存取 list 就能直接改動 *list 這個 pointer 如果假設 insert 的node 是最小的元素那 *list 其實還是等於是 head 便能將 head 指向新插入的 node，而如果今天是 insert 在中間 list 這個 pointer to pointer 已經指向目前欲插入元素位置前一個 node 的 next 所以不用多加處理，只要一行*link = newt;就能完成這些指標的連結，稍微能體會到一點什麼是有品味的程式碼了！

延伸問題

Optimizing merge sort 找到一個恰當的 S

在 Wikipedia 關於合併排序的詞目中，談及 Optimizing merge sort，我們可知道一種最佳化策略是：在子序列大小達到

S 時就不再繼續分割，此時這個
S 為可完整放進處理器 cache 中的元素數量。每個大小為
S 的子序列，都透過適用於小規模 in-place (即不需要額外配置記憶體) 排序演算法（如插入排序或泡沫排序）進行排序，以減少在記憶體內交換特定區域的次數。在小型子序列排序完畢後，再以典型的遞迴型合併排序完剩下的部份。
若可找到一個恰當的
S， 便能有效的同時利用到插入排序和合併排序的優點，並減少原始的合併排序當中 locality 不好的影響。請觀察你的硬體組態 (如 L1 data cache 的容量和行為)，以上述策略實作效率更好的 XOR linked list 排序程式。過程中應該充分量化數據並進行視覺化處理。

修改 sort

  • 原本的 sort 在分成左右兩個 list 時只是單純的把最左邊的 node 分開
  • 修改成左右兩邊各為原來的一半，原本 sort() 的參數加上一項 list 的長度
  • 測試排序1~10000 個 node ，原本的 merge sort 為
    O(n2)
int m2 = size / 2;
list *left = start, *right = start->addr, *left_end = start;
for (int i = 0; i < m2 - 1; i++) {
    list *tmp;
    tmp = right;
    right = XOR(right->addr, left_end);
    left_end = tmp;
}
left_end->addr = XOR(right, left_end->addr);
right->addr = XOR(right->addr, left_end);
left = sort(left, m2);
right = sort(right, size - m2;

In-place Sort Algorithm

  • 我選擇使用 bubble sort
  • 中間的 swap 我只是單純交換 node 的 data 而不是 addr
void bubble_sort(list* head, int count)
{

    int i, j, swapped; 
    for (i = 0; i < count-1; i++) { 
        list *h = head; 
        list *pre = NULL;
        swapped = 0; 
        list *p1 = h, *p2 = XOR(p1->addr, pre), *temp;
        for (j = 0; j < count - i - 1; j++) { 

            if (p1->data > p2->data) { 
                swap(p1, p2); 
                swapped = 1; 
            } 
            temp = p1;
            p1 = p2;
            p2 = XOR(temp, p1->addr);           
        } 
        
        if (swapped == 0) 
            break; 

    } 
}

void swap(list* node1, list* node2) 
{ 
    int tmp = node1->data;
    node1->data = node2->data;
    node2->data = tmp;
}

Experiments

  • 每次使用merge sort 時先將 list 分成 left 與 right 長度為
    len/2
  • 直到
    len     小於 S 再用 bubble sort 做好排序
  • 最後合併 left right
  • list 長度為 10000， S 測到1000

看起來S越接近零排序越快完成，也就是直接使用 merge sort 排的最快，我覺得跟問題所說的策略(找到一個恰當的 S， 便能有效的同時利用到插入排序和合併排序的優點)不相符，之後要再看看 S 從零到五十的時間

Last changed by 
 
Hsuhaoxiang
0
2589
Published on HackMD