2025q1 Homework2 (quiz1+2)

contributed by < weiso131 >

第一週測驗 `1`

填空

AAAA : &l
BBBB : before
CCCC : &(*p)->next
DDDD : item->next

程式運作原理

list_insert_before 運作原理

digraph LinkedList {
    rankdir=LR;
    node [shape=record, style=filled, fillcolor=lightgray];

    
    head_ptr [label="{l | <head >head}"];
    indirect [label="p", shape=note, fillcolor=lightyellow];

    node1 [label="{ data | <next >next }"];
    node2 [label="{ before | next }"];
    node3 [label="{ data | next }"];
    null [label="NULL", shape=plaintext];
    node4 [label="{ item | next }"];

    // head -> node1
    head_ptr -> node1 [label="head"];

    // node1 -> node2 -> node3 -> NULL
    node1 -> node2 [label="next"];
    node2 -> node3 [label="next"];
    node3 -> null [label="next"];

    // indirect 指向 head_ptr（間接指標）
    indirect -> head_ptr: next [style=dashed, color=blue];
}

digraph LinkedList {
    rankdir=LR;
    node [shape=record, style=filled, fillcolor=lightgray];

    
    head_ptr [label="{l | <head >head}"];
    indirect [label="p", shape=note, fillcolor=lightyellow];

    node1 [label="{ data | <next >next }"];
    node2 [label="{ before | next }"];
    node3 [label="{ data | next }"];
    null [label="NULL", shape=plaintext];
    node4 [label="{ item | next }"];

    // head -> node1
    head_ptr -> node1 [label="head"];

    // node1 -> node2 -> node3 -> NULL
    node1 -> node2 [label="next"];
    node2 -> node3 [label="next"];
    node3 -> null [label="next"];

    // indirect 指向 head_ptr（間接指標）
    indirect -> node1: next [style=dashed, color=blue];
}

digraph LinkedList {
    rankdir=LR;
    node [shape=record, style=filled, fillcolor=lightgray];

    
    head_ptr [label="{l | <head >head}"];
    indirect [label="p", shape=note, fillcolor=lightyellow];

    node1 [label="{ data | <next >next }"];
    node2 [label="{ before | next }"];
    node3 [label="{ data | next }"];
    null [label="NULL", shape=plaintext];
    node4 [label="{ item | next }"];

    // head -> node1
    head_ptr -> node1 [label="head"];

    // node1 -> node2 -> node3 -> NULL
    node1 -> node4 [label="next"];
    node2 -> node3 [label="next"];
    node3 -> null [label="next"];

    // indirect 指向 head_ptr（間接指標）
    indirect -> node1: next [style=dashed, color=blue];
}

digraph LinkedList {
    rankdir=LR;
    node [shape=record, style=filled, fillcolor=lightgray];

    
    head_ptr [label="{l | <head >head}"];
    indirect [label="p", shape=note, fillcolor=lightyellow];

    node1 [label="{ data | <next >next }"];
    node2 [label="{ before | next }"];
    node3 [label="{ data | next }"];
    null [label="NULL", shape=plaintext];
    node4 [label="{ item | next }"];

    // head -> node1
    head_ptr -> node1 [label="head"];

    // node1 -> node2 -> node3 -> NULL
    node1 -> node4 [label="next"];
    node2 -> node3 [label="next"];
    node3 -> null [label="next"];
    node4 -> node2 [label="next"];
    // indirect 指向 head_ptr（間接指標）
    indirect -> node1: next [style=dashed, color=blue];
}

merge_sort 實作

list_item_t *merge(list_item_t *l, list_item_t *r, int descend) 
{
    list_item_t *head = NULL, **indir = &head;
    while (1) {
        if (l->value > r->value == descend) {
            *indir = l;
            indir = &l->next;
            l = l->next;
            if (!l) {
                *indir = r;
                break;
            }
        }
        else {
            *indir = r;
            indir = &r->next;
            r = r->next;
            if (!r) {
                *indir = l;
                break;
            }
        }
    }
    return head;
}

list_item_t *merge_sort(list_item_t *head, int descend)
{
    if (head->next == NULL)
        return head;
    list_item_t *l = head, *last_r = head, *r = head->next, *fast = head->next;
    while (fast != NULL && fast->next != NULL) {
        last_r = r;
        r = r->next;
        fast = fast->next->next;
    }
    last_r->next = NULL;
    l = merge_sort(l, descend), r = merge_sort(r, descend);

    return merge(l, r, descend);
}

第一週測驗 `2`

填空

EEEE: (*pred_ptr)->r
FFFF: &(*pred_ptr)->r

`remove_free_tree` 解讀

`l == r == NULL`

digraph BST {
    rankdir=TB;
    node [shape=record, style=filled, fillcolor=lightgray];

    indirect [label="node_ptr", shape=note, fillcolor=lightyellow];
    //pred_ptr [label="pred_ptr", shape=note, fillcolor=lightyellow];
    // 節點
    n4 [label="{ <n4node> 4 | {<l> l | <r> r }}"];
    n2 [label="{ <n2node> 2 | {<l> l | <r> r }}"];
    n6 [label="{ <n6node> 6 | {<l> l | <r> r }}"];
    n1 [label="{ <n1node> 1 | {<l> l | <r> r }}"];
    n3 [label="{ <n3node> 3 | {<l> l | <r> r }}"];
    n5 [label="{ <n5node> 5 | {<l> l | <r> r }}"];
    n7 [label="{ <n7node> 7 | {<l> l | <r> r }}"];

    // NULL 節點
    null1 [label="NULL", shape=plaintext];
    null2 [label="NULL", shape=plaintext];
    null3 [label="NULL", shape=plaintext];
    null4 [label="NULL", shape=plaintext];
    null5 [label="NULL", shape=plaintext];
    null6 [label="NULL", shape=plaintext];
    null7 [label="NULL", shape=plaintext];
    null8 [label="NULL", shape=plaintext];


    // 建立連線（從 l、r port 出發，接到子節點的 <xxxnode> port）
    n4:l -> n2:n2node;
    n4:r -> n6:n6node;
    n2:l -> n1:n1node;
    n2:r -> n3:n3node;
    n6:l -> n5:n5node;
    n6:r -> n7:n7node;

    n1:l -> null1;
    n1:r -> null2;

    n3:l -> null3;
    n3:r -> null4;

    n5:l -> null5;
    n5:r -> null6;

    n7:l -> null7;
    n7:r -> null8;

    indirect -> n2: l [style=dashed, color=blue];
    //pred_ptr -> n2: n2node [style=dashed, color=blue];
}

digraph BST {
    rankdir=TB;
    node [shape=record, style=filled, fillcolor=lightgray];

    indirect [label="node_ptr", shape=note, fillcolor=lightyellow];
    //pred_ptr [label="pred_ptr", shape=note, fillcolor=lightyellow];
    // 節點
    n4 [label="{ <n4node> 4 | {<l> l | <r> r }}"];
    n2 [label="{ <n2node> 2 | {<l> l | <r> r }}"];
    n6 [label="{ <n6node> 6 | {<l> l | <r> r }}"];
    n1 [label="{ <n1node> 1 | {<l> l | <r> r }}"];
    n3 [label="{ <n3node> 3 | {<l> l | <r> r }}"];
    n5 [label="{ <n5node> 5 | {<l> l | <r> r }}"];
    n7 [label="{ <n7node> 7 | {<l> l | <r> r }}"];

    // NULL 節點
    null1 [label="NULL", shape=plaintext];
    null2 [label="NULL", shape=plaintext];
    null3 [label="NULL", shape=plaintext];
    null4 [label="NULL", shape=plaintext];
    null5 [label="NULL", shape=plaintext];
    null6 [label="NULL", shape=plaintext];
    null7 [label="NULL", shape=plaintext];
    null8 [label="NULL", shape=plaintext];
    null9 [label="NULL", shape=plaintext];

    // 建立連線（從 l、r port 出發，接到子節點的 <xxxnode> port）
    n4:l -> n2:n2node;
    n4:r -> n6:n6node;

    n2:l -> null9;
    n2:r -> n3:n3node;

    n6:l -> n5:n5node;
    n6:r -> n7:n7node;

    n1:l -> null1;
    n1:r -> null2;

    n3:l -> null3;
    n3:r -> null4;
    n5:l -> null5;
    n5:r -> null6;
    n7:l -> null7;
    n7:r -> null8;

    indirect -> n2: l [style=dashed, color=blue];
    //pred_ptr -> n2: n2node [style=dashed, color=blue];
}

`l != NULL || r != NULL`

digraph BST {
    rankdir=TB;
    node [shape=record, style=filled, fillcolor=lightgray];

    indirect [label="node_ptr", shape=note, fillcolor=lightyellow];
    //pred_ptr [label="pred_ptr", shape=note, fillcolor=lightyellow];
    // 節點
    n4 [label="{ <n4node> 4 | {<l> l | <r> r }}"];
    n2 [label="{ <n2node> 2 | {<l> l | <r> r }}"];
    n6 [label="{ <n6node> 6 | {<l> l | <r> r }}"];
    n3 [label="{ <n3node> 3 | {<l> l | <r> r }}"];
    n5 [label="{ <n5node> 5 | {<l> l | <r> r }}"];
    n7 [label="{ <n7node> 7 | {<l> l | <r> r }}"];

    // NULL 節點
    
    null3 [label="NULL", shape=plaintext];
    null4 [label="NULL", shape=plaintext];
    null5 [label="NULL", shape=plaintext];
    null6 [label="NULL", shape=plaintext];
    null7 [label="NULL", shape=plaintext];
    null8 [label="NULL", shape=plaintext];
    null9 [label="NULL", shape=plaintext];

    // 建立連線（從 l、r port 出發，接到子節點的 <xxxnode> port）
    n4:l -> n2:n2node;
    n4:r -> n6:n6node;

    n2:l -> null9;
    n2:r -> n3:n3node;

    n6:l -> n5:n5node;
    n6:r -> n7:n7node;

    n3:l -> null3;
    n3:r -> null4;
    n5:l -> null5;
    n5:r -> null6;
    n7:l -> null7;
    n7:r -> null8;

    indirect -> n4: l [style=dashed, color=blue];
    //pred_ptr -> n2: n2node [style=dashed, color=blue];
}

digraph BST {
    rankdir=TB;
    node [shape=record, style=filled, fillcolor=lightgray];

    indirect [label="node_ptr", shape=note, fillcolor=lightyellow];
    //pred_ptr [label="pred_ptr", shape=note, fillcolor=lightyellow];
    // 節點
    n4 [label="{ <n4node> 4 | {<l> l | <r> r }}"];
    n2 [label="{ <n2node> 2 | {<l> l | <r> r }}"];
    n6 [label="{ <n6node> 6 | {<l> l | <r> r }}"];
    n3 [label="{ <n3node> 3 | {<l> l | <r> r }}"];
    n5 [label="{ <n5node> 5 | {<l> l | <r> r }}"];
    n7 [label="{ <n7node> 7 | {<l> l | <r> r }}"];

    // NULL 節點
    
    null3 [label="NULL", shape=plaintext];
    null4 [label="NULL", shape=plaintext];
    null5 [label="NULL", shape=plaintext];
    null6 [label="NULL", shape=plaintext];
    null7 [label="NULL", shape=plaintext];
    null8 [label="NULL", shape=plaintext];
    null9 [label="NULL", shape=plaintext];

    // 建立連線（從 l、r port 出發，接到子節點的 <xxxnode> port）
    n4:l -> n3:n3node;
    n4:r -> n6:n6node;

    n2:l -> null9;
    n2:r -> n3:n3node;

    n6:l -> n5:n5node;
    n6:r -> n7:n7node;

    n3:l -> null3;
    n3:r -> null4;
    n5:l -> null5;
    n5:r -> null6;
    n7:l -> null7;
    n7:r -> null8;

    indirect -> n4: l [style=dashed, color=blue];
    //pred_ptr -> n2: n2node [style=dashed, color=blue];
}

digraph BST {
    rankdir=TB;
    node [shape=record, style=filled, fillcolor=lightgray];

    indirect [label="node_ptr", shape=note, fillcolor=lightyellow];
    //pred_ptr [label="pred_ptr", shape=note, fillcolor=lightyellow];
    // 節點
    n4 [label="{ <n4node> 4 | {<l> l | <r> r }}"];
    n2 [label="{ <n2node> 2 | {<l> l | <r> r }}"];
    n6 [label="{ <n6node> 6 | {<l> l | <r> r }}"];
    n3 [label="{ <n3node> 3 | {<l> l | <r> r }}"];
    n5 [label="{ <n5node> 5 | {<l> l | <r> r }}"];
    n7 [label="{ <n7node> 7 | {<l> l | <r> r }}"];

    // NULL 節點
    
    null3 [label="NULL", shape=plaintext];
    null4 [label="NULL", shape=plaintext];
    null5 [label="NULL", shape=plaintext];
    null6 [label="NULL", shape=plaintext];
    null7 [label="NULL", shape=plaintext];
    null8 [label="NULL", shape=plaintext];
    null9 [label="NULL", shape=plaintext];
    null1 [label="NULL", shape=plaintext];

    // 建立連線（從 l、r port 出發，接到子節點的 <xxxnode> port）
    n4:l -> n3:n3node;
    n4:r -> n6:n6node;

    n2:l -> null9;
    n2:r -> null1;

    n6:l -> n5:n5node;
    n6:r -> n7:n7node;

    n3:l -> null3;
    n3:r -> null4;
    n5:l -> null5;
    n5:r -> null6;
    n7:l -> null7;
    n7:r -> null8;

    indirect -> n4: l [style=dashed, color=blue];
    //pred_ptr -> n2: n2node [style=dashed, color=blue];
}

`l != NULL && r != NULL`

`pred_ptr != (node_ptr)->l`

digraph BST {
    rankdir=TB;
    node [shape=record, style=filled, fillcolor=lightgray];

    indirect [label="node_ptr", shape=note, fillcolor=lightyellow];
    pred_ptr [label="pred_ptr", shape=note, fillcolor=lightyellow];
    // 節點
    root [label="{root}"];
    n4 [label="{ <n4node> 4 | {<l> l | <r> r }}"];
    n2 [label="{ <n2node> 2 | {<l> l | <r> r }}"];
    n6 [label="{ <n6node> 6 | {<l> l | <r> r }}"];
    n1 [label="{ <n1node> 1 | {<l> l | <r> r }}"];
    n3 [label="{ <n3node> 3 | {<l> l | <r> r }}"];
    n5 [label="{ <n5node> 5 | {<l> l | <r> r }}"];
    n7 [label="{ <n7node> 7 | {<l> l | <r> r }}"];

    // NULL 節點
    null1 [label="NULL", shape=plaintext];
    null2 [label="NULL", shape=plaintext];
    null3 [label="NULL", shape=plaintext];
    null4 [label="NULL", shape=plaintext];
    null5 [label="NULL", shape=plaintext];
    null6 [label="NULL", shape=plaintext];
    null7 [label="NULL", shape=plaintext];
    null8 [label="NULL", shape=plaintext];

    root -> n4;
    // 建立連線（從 l、r port 出發，接到子節點的 <xxxnode> port）
    n4:l -> n2:n2node;
    n4:r -> n6:n6node;
    n2:l -> n1:n1node;
    n2:r -> n3:n3node;
    n6:l -> n5:n5node;
    n6:r -> n7:n7node;

    n1:l -> null1;
    n1:r -> null2;

    n3:l -> null3;
    n3:r -> null4;

    n5:l -> null5;
    n5:r -> null6;

    n7:l -> null7;
    n7:r -> null8;

    indirect -> root;
    pred_ptr -> n2 : r [style=dashed, color=blue];
}

digraph BST {
    rankdir=TB;
    node [shape=record, style=filled, fillcolor=lightgray];

    indirect [label="node_ptr", shape=note, fillcolor=lightyellow];
    pred_ptr [label="pred_ptr", shape=note, fillcolor=lightyellow];
    // 節點
    root [label="{root}"];
    n4 [label="{ <n4node> 4 | {<l> l | <r> r }}"];
    n2 [label="{ <n2node> 2 | {<l> l | <r> r }}"];
    n6 [label="{ <n6node> 6 | {<l> l | <r> r }}"];
    n1 [label="{ <n1node> 1 | {<l> l | <r> r }}"];
    n3 [label="{ <n3node> 3 | {<l> l | <r> r }}"];
    n5 [label="{ <n5node> 5 | {<l> l | <r> r }}"];
    n7 [label="{ <n7node> 7 | {<l> l | <r> r }}"];

    // NULL 節點
    null1 [label="NULL", shape=plaintext];
    null2 [label="NULL", shape=plaintext];
    null3 [label="NULL", shape=plaintext];
    null4 [label="NULL", shape=plaintext];
    null5 [label="NULL", shape=plaintext];
    null6 [label="NULL", shape=plaintext];
    null7 [label="NULL", shape=plaintext];
    null8 [label="NULL", shape=plaintext];
    null9 [label="NULL", shape=plaintext];

    root -> n4;
    // 建立連線（從 l、r port 出發，接到子節點的 <xxxnode> port）
    n4:l -> n2:n2node;
    n4:r -> n6:n6node;
    n2:l -> n1:n1node;
    n2:r -> null9;
    n6:l -> n5:n5node;
    n6:r -> n7:n7node;

    n1:l -> null1;
    n1:r -> null2;

    n3:l -> null3;
    n3:r -> null4;

    n5:l -> null5;
    n5:r -> null6;

    n7:l -> null7;
    n7:r -> null8;

    indirect -> root;
    pred_ptr -> n2 : r [style=dashed, color=blue];
}

digraph BST {
    rankdir=TB;
    node [shape=record, style=filled, fillcolor=lightgray];

    indirect [label="node_ptr", shape=note, fillcolor=lightyellow];
    pred_ptr [label="pred_ptr", shape=note, fillcolor=lightyellow];
    // 節點
    root [label="{root}"];
    n4 [label="{ <n4node> 4 | {<l> l | <r> r }}"];
    n2 [label="{ <n2node> 2 | {<l> l | <r> r }}"];
    n6 [label="{ <n6node> 6 | {<l> l | <r> r }}"];
    n1 [label="{ <n1node> 1 | {<l> l | <r> r }}"];
    n3 [label="{ <n3node> 3 | {<l> l | <r> r }}"];
    n5 [label="{ <n5node> 5 | {<l> l | <r> r }}"];
    n7 [label="{ <n7node> 7 | {<l> l | <r> r }}"];

    // NULL 節點
    null1 [label="NULL", shape=plaintext];
    null2 [label="NULL", shape=plaintext];
    null3 [label="NULL", shape=plaintext];
    null4 [label="NULL", shape=plaintext];
    null5 [label="NULL", shape=plaintext];
    null6 [label="NULL", shape=plaintext];
    null7 [label="NULL", shape=plaintext];
    null8 [label="NULL", shape=plaintext];
    null9 [label="NULL", shape=plaintext];

    root -> n3;
    // 建立連線（從 l、r port 出發，接到子節點的 <xxxnode> port）
    n4:l -> null3;
    n4:r -> null4;
    n2:l -> n1:n1node;
    n2:r -> null9;
    n6:l -> n5:n5node;
    n6:r -> n7:n7node;

    n1:l -> null1;
    n1:r -> null2;

    n3:l -> n2;
    n3:r -> n6;

    n5:l -> null5;
    n5:r -> null6;

    n7:l -> null7;
    n7:r -> null8;

    indirect -> root;
    pred_ptr -> n2 : r [style=dashed, color=blue];
}

`pred_ptr == (node_ptr)->l`

digraph BST {
    rankdir=TB;
    node [shape=record, style=filled, fillcolor=lightgray];

    indirect [label="node_ptr", shape=note, fillcolor=lightyellow];
    pred_ptr [label="pred_ptr", shape=note, fillcolor=lightyellow];
    // 節點
    n4 [label="{ <n4node> 4 | {<l> l | <r> r }}"];
    n2 [label="{ <n2node> 2 | {<l> l | <r> r }}"];
    n6 [label="{ <n6node> 6 | {<l> l | <r> r }}"];
    n1 [label="{ <n1node> 1 | {<l> l | <r> r }}"];
    n3 [label="{ <n3node> 3 | {<l> l | <r> r }}"];
    n5 [label="{ <n5node> 5 | {<l> l | <r> r }}"];
    n7 [label="{ <n7node> 7 | {<l> l | <r> r }}"];

    // NULL 節點
    null1 [label="NULL", shape=plaintext];
    null2 [label="NULL", shape=plaintext];
    null3 [label="NULL", shape=plaintext];
    null4 [label="NULL", shape=plaintext];
    null5 [label="NULL", shape=plaintext];
    null6 [label="NULL", shape=plaintext];
    null7 [label="NULL", shape=plaintext];
    null8 [label="NULL", shape=plaintext];

    // 建立連線（從 l、r port 出發，接到子節點的 <xxxnode> port）
    n4:l -> n2:n2node;
    n4:r -> n6:n6node;
    n2:l -> n1:n1node;
    n2:r -> n3:n3node;
    n6:l -> n5:n5node;
    n6:r -> n7:n7node;

    n1:l -> null1;
    n1:r -> null2;

    n3:l -> null3;
    n3:r -> null4;

    n5:l -> null5;
    n5:r -> null6;

    n7:l -> null7;
    n7:r -> null8;

    indirect -> n4 : l;
    pred_ptr -> n2 : l [style=dashed, color=blue];
}

digraph BST {
    rankdir=TB;
    node [shape=record, style=filled, fillcolor=lightgray];

    indirect [label="node_ptr", shape=note, fillcolor=lightyellow];
    pred_ptr [label="pred_ptr", shape=note, fillcolor=lightyellow];
    // 節點
    n4 [label="{ <n4node> 4 | {<l> l | <r> r }}"];
    n2 [label="{ <n2node> 2 | {<l> l | <r> r }}"];
    n6 [label="{ <n6node> 6 | {<l> l | <r> r }}"];
    n1 [label="{ <n1node> 1 | {<l> l | <r> r }}"];
    n3 [label="{ <n3node> 3 | {<l> l | <r> r }}"];
    n5 [label="{ <n5node> 5 | {<l> l | <r> r }}"];
    n7 [label="{ <n7node> 7 | {<l> l | <r> r }}"];

    // NULL 節點
    null1 [label="NULL", shape=plaintext];
    null2 [label="NULL", shape=plaintext];
    null3 [label="NULL", shape=plaintext];
    null4 [label="NULL", shape=plaintext];
    null5 [label="NULL", shape=plaintext];
    null6 [label="NULL", shape=plaintext];
    null7 [label="NULL", shape=plaintext];
    null8 [label="NULL", shape=plaintext];

    // 建立連線（從 l、r port 出發，接到子節點的 <xxxnode> port）
    n4:l -> n2:n2node;
    n4:r -> n6:n6node;
    n2:l -> n1:n1node;
    n2:r -> n3:n3node;
    n6:l -> n5:n5node;
    n6:r -> n7:n7node;

    n1:l -> null1;
    n1:r -> null2;

    n3:l -> null3;
    n3:r -> null4;

    n5:l -> null5;
    n5:r -> null6;

    n7:l -> null7;
    n7:r -> null8;

    indirect -> n4:l;
    pred_ptr -> n2 : l [style=dashed, color=blue];
}

digraph BST {
    rankdir=TB;
    node [shape=record, style=filled, fillcolor=lightgray];

    indirect [label="node_ptr", shape=note, fillcolor=lightyellow];
    pred_ptr [label="pred_ptr", shape=note, fillcolor=lightyellow];
    // 節點
    n4 [label="{ <n4node> 4 | {<l> l | <r> r }}"];
    n2 [label="{ <n2node> 2 | {<l> l | <r> r }}"];
    n6 [label="{ <n6node> 6 | {<l> l | <r> r }}"];
    n1 [label="{ <n1node> 1 | {<l> l | <r> r }}"];
    n3 [label="{ <n3node> 3 | {<l> l | <r> r }}"];
    n5 [label="{ <n5node> 5 | {<l> l | <r> r }}"];
    n7 [label="{ <n7node> 7 | {<l> l | <r> r }}"];

    // NULL 節點
    null1 [label="NULL", shape=plaintext];
    null2 [label="NULL", shape=plaintext];
    null3 [label="NULL", shape=plaintext];
    null4 [label="NULL", shape=plaintext];
    null5 [label="NULL", shape=plaintext];
    null6 [label="NULL", shape=plaintext];
    null7 [label="NULL", shape=plaintext];
    null8 [label="NULL", shape=plaintext];
    null9 [label="NULL", shape=plaintext];

    // 建立連線（從 l、r port 出發，接到子節點的 <xxxnode> port）
    n4:l -> n1:n1node;
    n4:r -> n6:n6node;
    n2:l -> null9;
    n2:r -> null2;
    n6:l -> n5:n5node;
    n6:r -> n7:n7node;

    n1:l -> null1;
    n1:r -> n3;

    n3:l -> null3;
    n3:r -> null4;

    n5:l -> null5;
    n5:r -> null6;

    n7:l -> null7;
    n7:r -> null8;

    indirect -> n4:l;
    pred_ptr -> n2 : l [style=dashed, color=blue];
}

補完程式碼

find_free_tree

block_t **find_free_tree(block_t **root, block_t *target)
{
    block_t **node_ptr = root;
    while (*node_ptr != target && *node_ptr != NULL) {
        if (target->size > (*node_ptr)->size)
            node_ptr = &(*node_ptr)->r;
        else
            node_ptr = &(*node_ptr)->l;
    }
    return node_ptr;
}

解說

digraph BST {
    rankdir=TB;
    node [shape=record, style=filled, fillcolor=lightgray];

    indirect [label="node_ptr", shape=note, fillcolor=lightyellow];
    // 節點
    n4 [label="{ <n4node> 4 | {<l> l | <r> r }}"];
    n2 [label="{ <n2node> target | {<l> l | <r> r }}"];
    n6 [label="{ <n6node> 6 | {<l> l | <r> r }}"];
    n1 [label="{ <n1node> 1 | {<l> l | <r> r }}"];
    n3 [label="{ <n3node> 3 | {<l> l | <r> r }}"];
    n5 [label="{ <n5node> 5 | {<l> l | <r> r }}"];
    n7 [label="{ <n7node> 7 | {<l> l | <r> r }}"];

    // NULL 節點
    null1 [label="NULL", shape=plaintext];
    null2 [label="NULL", shape=plaintext];
    null3 [label="NULL", shape=plaintext];
    null4 [label="NULL", shape=plaintext];
    null5 [label="NULL", shape=plaintext];
    null6 [label="NULL", shape=plaintext];
    null7 [label="NULL", shape=plaintext];
    null8 [label="NULL", shape=plaintext];

    root -> n4;
    // 建立連線（從 l、r port 出發，接到子節點的 <xxxnode> port）
    n4:l -> n2:n2node;
    n4:r -> n6:n6node;
    n2:l -> n1:n1node;
    n2:r -> n3:n3node;
    n6:l -> n5:n5node;
    n6:r -> n7:n7node;

    n1:l -> null1;
    n1:r -> null2;

    n3:l -> null3;
    n3:r -> null4;

    n5:l -> null5;
    n5:r -> null6;

    n7:l -> null7;
    n7:r -> null8;

    indirect -> root;
}

digraph BST {
    rankdir=TB;
    node [shape=record, style=filled, fillcolor=lightgray];

    indirect [label="return: node_ptr", shape=note, fillcolor=lightyellow];
    // 節點
    n4 [label="{ <n4node> 4 | {<l> l | <r> r }}"];
    n2 [label="{ <n2node> target | {<l> l | <r> r }}"];
    n6 [label="{ <n6node> 6 | {<l> l | <r> r }}"];
    n1 [label="{ <n1node> 1 | {<l> l | <r> r }}"];
    n3 [label="{ <n3node> 3 | {<l> l | <r> r }}"];
    n5 [label="{ <n5node> 5 | {<l> l | <r> r }}"];
    n7 [label="{ <n7node> 7 | {<l> l | <r> r }}"];

    // NULL 節點
    null1 [label="NULL", shape=plaintext];
    null2 [label="NULL", shape=plaintext];
    null3 [label="NULL", shape=plaintext];
    null4 [label="NULL", shape=plaintext];
    null5 [label="NULL", shape=plaintext];
    null6 [label="NULL", shape=plaintext];
    null7 [label="NULL", shape=plaintext];
    null8 [label="NULL", shape=plaintext];

    root -> n4;
    // 建立連線（從 l、r port 出發，接到子節點的 <xxxnode> port）
    n4:l -> n2:n2node;
    n4:r -> n6:n6node;
    n2:l -> n1:n1node;
    n2:r -> n3:n3node;
    n6:l -> n5:n5node;
    n6:r -> n7:n7node;

    n1:l -> null1;
    n1:r -> null2;

    n3:l -> null3;
    n3:r -> null4;

    n5:l -> null5;
    n5:r -> null6;

    n7:l -> null7;
    n7:r -> null8;

    indirect -> n4:l;
}

insert_free_tree

void insert_free_tree(block_t **root, block_t *target)
{
    block_t **node_ptr = find_free_tree(root, target);
    *node_ptr = target;
}

init_block

block_t *init_block(size_t size) 
{
    block_t *block = malloc(sizeof(block_t));
    block->size = size;
    block->l = block->r = NULL;
    return block;
}

測試程式

void block_test() 
{
    for (int i = 0;i < N;i++) {
        size_t size = rand() % 8192;
        blocks[i] = init_block(size);
        insert_free_tree(&root, blocks[i]);
    }
    for (int i = 0;i < N;i++) {
        remove_free_tree(&root, blocks[i]);
        block_t **find = find_free_tree(&root, blocks[i]);
        assert(*find == NULL);
        free(blocks[i]);
        blocks[i] = NULL;
    }
    printf("All test complete!!!\n");
}

解說

自訂記憶體配置器

github
參考 memory-allocators 的 free list allocator。
這種記憶體分配器屬於通用型分配器，利用一個資料結構(通常是鏈結串列或紅黑樹)紀錄可供使用的記憶體區塊，在使用者請求分配時，在這個資料結構尋找合適的區塊提供給使用者。
另外，若在釋放記憶體時，發現有相鄰的記憶體區塊是可用的，這種實作方法會將其合併。
要以時間複雜度 \(O(1)\) 確認是否能合併，可以使用雙向鏈結串列維護其順序，以方便查詢。

文中提到可以用鍊結串列或是紅黑樹維護，我嘗試使用二元搜尋樹代替紅黑樹，實作這種記憶體分配器。在不發生樹嚴重傾斜的情況下，查詢的時間複雜度與紅黑樹相同，皆是 \(O(log(n))\)。而在測驗題中也有提供相關實作，可直接使用。

至於雙向鏈結串列，在實作過程中發現，若是環狀的鏈結串列，在插入節點時就沒有判斷下一項是否為空指標的問題，因此我使用 list.h 的資料結構與 API 來維護這個雙向鏈結串列。

功能簡述

這些是這個分配器提供給使用者的主要功能
定義在 includes/free_list_alloc.h

void init_fl(size_t size);
根據使用者提供的size，設定這個記憶體分配器的總分配空間大小上限
void *fl_alloc(size_t size)
分配使用者需要的記憶體空間，分配成功則回傳該記憶體的位址
分配失敗或是 size 為 0 則回傳 NULL
void fl_free(void *ptr)
將使用者傳入的指標對應的空間釋放
若傳入空指標則不做任何事情
若傳入已經釋放過，或是不屬於 init_fl 初始化的記憶體，則屬於 undefine behavior
與 C 語言原生的 free 類似(參考: C standard (ISO/IEC 9899:2011 §7.20.3.2))

`init_fl`

步驟

利用 init_block 建立一個初始 block (root_block)。
把這個 block 設定為 tree_root（BST 根節點）。
建立一個 root_head，為雙向鏈結串列的頭節點。
將 root_block 加入雙向鏈結串列（使用 list_add）。

說明

這個新的 block 是一個全新可用的區塊，所以直接加入二元搜尋樹
先使用 root_block 儲存這個分配器全部的可用區塊，再將 tree_root 設定成 root_block ，可以在最後方便使用者一次釋放所有空間，不會因為二元搜尋樹根節點的改變而無法一次釋放

`fl_alloc`

步驟

使用 find_block_by_size() 找一個合適的 block
從 BST 移除該 block ，代表這個 block 不再是未使用空間
分割多餘空間：
- 若剩餘空間足夠放一個 block 結構和額外資料 ➜ 建立新 block (unuse)。
- 重新設定兩個區塊所持有的空間
- 將 unuse 插入鏈結串列(在原本的 block 後方)，並加入二元搜尋樹。
標記分配的 block 為已使用

說明

若剩餘空間小於等於 block 結構的大小，則無法正常成為一個可使用的 block，此時儘管超出使用者要求的記憶體一些，仍會一次將這些記憶體都提供給使用者

`find_block_by_size`

找到最小大於等於使用者要求大小的區塊
在迴圈中，若最後找不到相同大小的區塊時， find 會變成 NULL
為了確保找到的區塊絕對大於使用者要求大小，利用 last_bigger 儲存最後一個往左，也就是最後一個發現比目標大的區塊的指標

dded92d
find 為 NULL 的時候會將其設為 last_bigger ，若 size 大於所有可用區塊，就會因為尋找過程中一直向右， last_bigger 仍為 NULL ，符合需求

`fl_free`

步驟

檢查時否未使用
標記 block 為未使用
插入二元搜尋樹
呼叫 try_merge() 嘗試合併周圍未使用區塊

`try_merge`

檢查 block 的 list.next 和 list.prev 是否是未使用。
若是 ➜ 呼叫 merge_b_to_a()

`merge_b_to_a`

將 b 從 BST 和 linked list 移除。
將 a 從 BST 移除。
計算合併後新大小 ➜ a->size = a->size + b->size + sizeof(block_t)。
將合併後的 a 插回 BST

說明

因為合併大小時，可能會改變二元搜尋樹的性質，所以要先將 a 從樹上移除

5c0da11

效能測試

測試程式

圖為隨機執行 alloc / free 1000000 次所花費的時間累積圖
如圖，目前的分配器效能明顯比 malloc 差

使用 perf 尋找效能瓶頸

可以發現 find_free_tree 佔用了非常大量的時間
查看組合語言可以看到 cmp 前最後一個 dereference 非常花時間，這可能對應到原始碼的 (*node_ptr)->size

  0.07 │25:   mov     -0x20(%rbp),%rax                                                                                                                                                                 ▒
  0.71 │      mov     (%rax),%rax                                                                                                                                                                      ▒
  0.13 │      mov     -0x8(%rbp),%rdx                                                                                                                                                                  ▒
 53.47 │      mov     (%rdx),%rdx

似乎與太多的 cache miss 發生有關

嘗試減少 `find_free_tree` 使用

參考 rota1001 開發紀錄

效能或許有些微提昇，使用 t 檢定驗證





















def calculate_cohens_d(x1, x2):
    # Pooled standard deviation
    nx = len(x1)
    ny = len(x2)
    pooled_std = np.sqrt(((nx - 1)*np.var(x1, ddof=1) + (ny - 1)*np.var(x2, ddof=1)) / (nx + ny - 2))
    d = (np.mean(x1) - np.mean(x2)) / pooled_std
    return d

def compare_groups(free_list, new_free_list):
    # Welch's t-test（自動考慮變異數不等）
    t_value, p_value = ttest_ind(free_list, new_free_list, equal_var=False)

    # 自由度由 ttest_ind 自動處理（Welch 方法）
    cohen_d = calculate_cohens_d(free_list, new_free_list)

    print(f"✅ Welch's t-test 結果：")
    print(f"t 值：{t_value:.4f}")
    print(f"p 值：{p_value:.4f} {'（顯著）' if p_value < 0.05 else '（不顯著）'}")
    print(f"Cohen's d 效果量：{cohen_d:.4f}")
    print(f"效能提升倍率：{free_list.sum() / new_free_list.sum():.4f}")
compare_groups(free_list, new_free_list)

輸出：

✅ Welch's t-test 結果：
t 值：54.8427
p 值：0.0000 （顯著）
Cohen's d 效果量：0.0776
效能提升倍率：1.0997

8e833ec

第一週測驗 `3`

填空

GGGG: head->prev=prev
HHHH: list_entry(pivot,node_t,list)->value
IIII: list_entry(n,node_t,list)->value
JJJJ: pivot
KKKK: right

`rebuild_list_link` 解說

node 不斷往 next
prev 緊跟在 node 後面
當 node 為 NULL 時，代表鍊結串列的最後一個節點找到了
此時 prev 就是最後一個節點

`quick_sort` 解說

digraph LinkedList {
    rankdir=LR;
    node [shape=record, style=filled];
    
    list [label="list | {<prev>perv | <next>next } "];
    begin [label="begin: | {4}"];
    node1 [label="{{4 | {<head> list_head | <next >next}}}"];
    node2 [label="{{8 | {<head> list_head | <next >next}}}"];
    node3 [label="{{7 | {<head> list_head | <next >next}}}"];
    node4 [label="{{6 | {<head> list_head | <next >next}}}"];
    node5 [label="{{3 | {<head> list_head | <next >next}}}"];

    node1: next -> node2: head;
    node2:next -> node3:head;
    node3:next -> node4:head;
    node4:next -> node5:head;
    node5:next -> list: prev;
    list:next -> node1:head;
}

digraph LinkedList {
    rankdir=LR;
    node [shape=record, style=filled];
    pivot [label="pivot", style=filled, fillcolor=lightyellow]
    p [label="p", style=filled, fillcolor=lightyellow]
    right [label="right", style=filled, fillcolor=lightyellow]
    left [label="left", style=filled, fillcolor=lightyellow]
    null1 [label="NULL"]
    node1 [label="{{4 | {<head> list_head | <next >next}}}"];
    node2 [label="{{8 | {<head> list_head | <next >next}}}"];
    node3 [label="{{7 | {<head> list_head | <next >next}}}"];
    node4 [label="{{6 | {<head> list_head | <next >next}}}"];
    node5 [label="{{3 | {<head> list_head | <next >next}}}"];

    node1: next -> node2: head;
    node2:next -> node3:head;
    node3:next -> node4:head;
    node4:next -> node5:head;
    node5:next -> null1:head;
    pivot -> node1: head;
    p -> node2: head;
}

digraph LinkedList {
    rankdir=LR;
    node [shape=record, style=filled];
    pivot [label="pivot", style=filled, fillcolor=lightyellow]
    p [label="p", style=filled, fillcolor=lightyellow]
    right [label="right", style=filled, fillcolor=lightyellow]
    left [label="left", style=filled, fillcolor=lightyellow]
    null1 [label="NULL"]
    null2 [label="NULL"]
    node1 [label="{{4 | {<head> list_head | <next >next}}}"];
    node2 [label="{{8 | {<head> list_head | <next >next}}}"];
    node3 [label="{{7 | {<head> list_head | <next >next}}}"];
    node4 [label="{{6 | {<head> list_head | <next >next}}}"];
    node5 [label="{{3 | {<head> list_head | <next >next}}}"];

    node1: next -> null2;
    node2:next -> node3:head;
    node3:next -> node4:head;
    node4:next -> node5:head;
    node5:next -> null1:head;
    pivot -> node1: head;
    p -> node3: head;
    right -> node2;
}

digraph LinkedList {
    rankdir=LR;
    node [shape=record, style=filled];
    pivot [label="pivot", style=filled, fillcolor=lightyellow]
    p [label="p", style=filled, fillcolor=lightyellow]
    right [label="right", style=filled, fillcolor=lightyellow]
    left [label="left", style=filled, fillcolor=lightyellow]
    null1 [label="NULL"]
    null2 [label="NULL"]
    node1 [label="{{4 | {<head> list_head | <next >next}}}"];
    node2 [label="{{8 | {<head> list_head | <next >next}}}"];
    node3 [label="{{7 | {<head> list_head | <next >next}}}"];
    node4 [label="{{6 | {<head> list_head | <next >next}}}"];
    node5 [label="{{3 | {<head> list_head | <next >next}}}"];

    node1: next -> null2;
    node2:next -> node3:head;
    node3:next -> node4:head;
    node4:next -> node5:head;
    node5:next -> null1:head;
    pivot -> node1: head;
    p -> null1;
    right -> node2;
    left -> node5;
}

digraph LinkedList {
    rankdir=LR;
    node [shape=record, style=filled];
    pivot [label="pivot", style=filled, fillcolor=lightyellow]
    right [label="right", style=filled, fillcolor=lightyellow]
    left [label="left", style=filled, fillcolor=lightyellow]
    null1 [label="NULL"]
    null2 [label="NULL"]
    null3 [label="NULL"]
    node1 [label="{{4 | {<head> list_head | <next >next}}}"];
    node2 [label="{{8 | {<head> list_head | <next >next}}}"];
    node3 [label="{{7 | {<head> list_head | <next >next}}}"];
    node4 [label="{{6 | {<head> list_head | <next >next}}}"];
    node5 [label="{{3 | {<head> list_head | <next >next}}}"];

    node1: next -> null2;
    node2:next -> node3:head;
    node3:next -> node4:head;
    node4:next -> null3;
    node5:next -> null1;
    pivot -> node1: head;
    right -> node2;
    left -> node5;
    begin [label="begin: | 3 | 4| 8"];
}

稍微跳過幾個步驟

digraph LinkedList {
    rankdir=LR;
    node [shape=record, style=filled];
    result [label="result", style=filled, fillcolor=lightyellow]
    right [label="right", style=filled, fillcolor=lightyellow]
    left [label="left", style=filled, fillcolor=lightyellow]
    null1 [label="NULL"]
    null2 [label="NULL"]
    null3 [label="NULL"]
    null4 [label="NULL"]
    null5 [label="NULL"]
    node1 [label="{{4 | {<head> list_head | <next >next}}}"];
    node2 [label="{{8 | {<head> list_head | <next >next}}}"];
    node3 [label="{{7 | {<head> list_head | <next >next}}}"];
    node4 [label="{{6 | {<head> list_head | <next >next}}}"];
    node5 [label="{{3 | {<head> list_head | <next >next}}}"];

    node1: next -> null2;
    node2:next -> null4;
    node3:next -> null5;
    node4:next -> null3;
    node5:next -> null1;
    right -> node3: head;
    left -> node3: head;
    begin [label="begin: | 3 | 4| 6 | 7"];
    result -> node2: head;
}

digraph LinkedList {
    rankdir=LR;
    node [shape=record, style=filled];
    result [label="result", style=filled, fillcolor=lightyellow]
    right [label="right", style=filled, fillcolor=lightyellow]
    left [label="left", style=filled, fillcolor=lightyellow]
    null4 [label="NULL"]

    node1 [label="{{4 | {<head> list_head | <next >next}}}"];
    node2 [label="{{8 | {<head> list_head | <next >next}}}"];
    node3 [label="{{7 | {<head> list_head | <next >next}}}"];
    node4 [label="{{6 | {<head> list_head | <next >next}}}"];
    node5 [label="{{3 | {<head> list_head | <next >next}}}"];

    node1: next -> node4: head;
    node2:next -> null4;
    node3:next -> node2: head;
    node4:next -> node3: head;
    node5:next -> node1: head;
    right -> node5: head;
    left -> node5: head;
    begin [label="begin: | 3"];
    result -> node5: head;
}

digraph LinkedList {
    rankdir=LR;
    node [shape=record, style=filled];
    list [label="list | {<prev>perv | <next>next } "];
    result [label="result", style=filled, fillcolor=lightyellow]

    node1 [label="{{4 | {<head> list_head | <next >next}}}"];
    node2 [label="{{8 | {<head> list_head | <next >next}}}"];
    node3 [label="{{7 | {<head> list_head | <next >next}}}"];
    node4 [label="{{6 | {<head> list_head | <next >next}}}"];
    node5 [label="{{3 | {<head> list_head | <next >next}}}"];

    node1: next -> node4: head;
    node3:next -> node2: head;
    node4:next -> node3: head;
    node5:next -> node1: head;
    result -> node5: head;
    list: next -> node5: head;
    list: prev -> node2: head;
    node2: next -> list: head;
}

第二週測驗 1

填空

AAAA: list_first_entry
BBBB: list_del
CCCC: list_move_tail
DDDD: list_add
EEEE: list_splice
FFFF: list_splice_tail

`list_quicksort` 解釋

將 list 的第一項作為 pivot ，並移出環狀鍊結串列
比 pivot 小的節點加入 list_less ，比 pivot 大的節點加入 list_greater ，加入時使用 list_move_tail 維持環狀鍊結串列的特性，同時滿足 stable sorting
list_less 與 list_greater 各自進行 list_quicksort
將 pivot, list_less, list_greater 合併

修正 `random_shuffle_array`

測試程式

使用 4 個元素的陣列
執行 shuffle 1e6 次
紀錄每種排列的出現次數
再計算卡方值

static int index_form[4][4][4];

#define SHUFFLE_TIMES 1000000
#define FACTORIAL_4 24

void build_lookup_table()
{
    int index = 0;
    uint16_t perm[4] = {1, 2, 3, 4};

    // Generate all 4! permutations using stdlib's next_permutation
    for (int a = 1; a <= 4; ++a)
        for (int b = 1; b <= 4; ++b)
            if (b != a)
                for (int c = 1; c <= 4; ++c)
                    if (c != a && c != b)
                        for (int d = 1; d <= 4; ++d)
                            if (d != a && d != b && d != c)
                                index_form[a - 1][b - 1][c - 1] = index++;
}



int main()
{
    uint16_t array[4] = {0, 1, 2, 3};
    uint32_t count[FACTORIAL_4] = {0};
    build_lookup_table();
    for (int i = 0; i < SHUFFLE_TIMES; ++i) {
        random_shuffle_array(array, 4);
        int idx = index_form[(int)array[0]][(int)array[1]][(int)array[2]];
        count[idx]++;
    }
    double expected = (double)SHUFFLE_TIMES / FACTORIAL_4;
    double chi_squared = 0.0;

    for (int i = 0; i < FACTORIAL_4; ++i) {
        double diff = count[i] - expected;
        chi_squared += (diff * diff) / expected;
    }

    printf("Chi-squared value: %.4f\n", chi_squared);

    return 0;
}

原本的 `random_shuffle_array`

輸出：

Chi-squared value: 122688.7850

卡方值遠高於 \(\chi^2_{23,0.05}=35.1725\)

使用 `fisher_yates_shuffle`

參考 lab0 提供的 shuffle 演算法

static inline void fisher_yates_shuffle(uint16_t *operations, uint16_t len)
{
    for (uint16_t i = 0;i < len;i++) {
        uint16_t new = len - i - 1;
        uint16_t old = get_unsigned16() % (new + 1);
        uint16_t save = operations[new];
        operations[new] = operations[old];
        operations[old] = save;

    }
}

輸出：

Chi-squared value: 21748.5402

雖然有減少，但其卡方值仍遠高於 \(\chi^2_{23,0.05}=35.1725\)

使用 `rand` 代替 `get_unsigned16`

        uint16_t new = len - i - 1;
-       uint16_t old = get_unsigned16() % (new + 1);
+       uint16_t old = rand() % (new + 1);
        uint16_t save = operations[new];

輸出：

Chi-squared value: 10.5795

卡方值小於 \(\chi^2_{23,0.05}=35.1725\)
無證據說明這個 shuffle 是不公平的

`list_move_tail` 換為 `list_move` 無法滿足 stable sorting

第二週測驗 2

填空

GGGG: 14
HHHH: 2
IIII: 0
JJJJ: 3
KKKK: 2
LLLL: 1
MMMM: ~1
NNNN: 1
PPPP: 2

`clz32`

解說

先將一個數字藉由 bit mask 切分成 upper 與 lower
檢查 upper 是否為 0 ，若不是 0 ，代表 leading zero 在 upper 裡面，對 upper 執行 clz32。反之， leading zero 在 lower ，此時加上 (16 >> c) 正是前方的位元數量。
重複執行直到 c == 3 ，此時 upper 與 lower 都只剩兩個 bits 的長度，若 upper 不為 0 ，將 upper 帶入 magic 可做最後的計算。反之， +2 然後對 lower 最類似的事情。

mask 補充

最後只剩 2 bits ，代表會有四種可能

00: 前方累計位元數 +2 即是 leading zero 的位置
01: 前方累計位元數 +1 即是 leading zero 的位置
10: 前方累計位元數即是 leading zero 的位置
11: 前方累計位元數即是 leading zero 的位置

`sqrti`

解說

題目中的 sqrti 其實就是 Digit-by-digit Method 的實作，但直接從原本的函式實作解釋它有些困難，我將會提供從最直觀的實作，一步一步優化到現在狀態的過程。

最直觀實作

    int shift = (total_bits - 1 - clz64(x)) & ~1;

    while (shift >= 0) {
        m = 1ULL << shift;
        uint64_t m_2 = 1ULL << (shift >> 1);
        uint64_t b = ((y * m_2) << 1) + m;
        if (x >= b) {
            x -= b;
            y += m_2;
        }
        shift -= 2;
    }

這個實作方法基本上是照著演算法的描述一步一步實現，可以看到他會存在一個乘法運算

移除乘法運算

    int shift = (total_bits - 1 - clz64(x)) & ~1;
    uint64_t last = 0;

    while (shift >= 0) {
        m = 1ULL << shift;
        uint64_t m_2 = 1ULL << (shift >> 1);
        uint64_t b = last + m;
        last >>= 1;
        if (x >= b) {
            x -= b;
            y += m_2;
            last += m;
        }
        shift -= 2;
    }

這個方法由一個 last 儲存每一次 y 更新時的 m
並在進入判斷式前右移一格

這個調整仍是有效的原因，是因為所有 m 都是 2 的次方
以此改寫公式
\[ (2^{i+k}+...+2^i+2^{i-j})^2=(2^i)^2+(2(2^{i+k}+...+2^i)+2^{i-j})\cdot 2^{i-j} \]
再展開
\[ (2^i)^2+(2^{i-j})^2+2^{2i+k-j+1}+...+2^{2i-j+1} \]

觀察到 \(2^{2i-j+1}\) 可以發現只要對 \(2^{2i}\) 右移 \(j-1\) ，就能得到現在做計算所需的值
這正是 last 在做的事情

合併 `last` 與 `y`

    int shift = (total_bits - 1 - clz64(x)) & ~1;

    while (shift >= 0) {
        m = 1ULL << shift;
        uint64_t b = y + m;
        y >>= 1;
        if (x >= b) {
            x -= b;
            y += m;
        }
        shift -= 2;
    }

在 shift 為 \(2i\) 加上一個 m: \(2^{2i}\)
由於到迴圈結束時會被右移 \(i\) 格，對最後的 last 而言相當於每次都加上 \(2^i\)
這與 y 的功能完全相同

到了這步基本上已經跟原本的 sqrti 相同，只差把每次重新計算的 m 放在迴圈外，每次 m 往右移兩格的調整

向上取整

x 在計算過程會被減去 y 的平方
若最後 x 不是 0 ，就代表 x 原本不是完全平方數，需要向上取整，也就是額外 +1
因此，可以對最後的 return 做修改

return y + (x && 1);

即可在只使用加減法與位元操作的情況下，完成向上取整的平方根

第二週測驗 3

填空

AAAA: map->bits
BBBB: map->bits
CCCC: first->pprev
DDDD: n->pprev
EEEE: n->pprev

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`	在筆記中貼入程式碼
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.

2025q1 Homework2 (quiz1+2)

第一週測驗 1

填空

程式運作原理

list_insert_before 運作原理

merge_sort 實作

第一週測驗 2

填空

remove_free_tree 解讀

l == r == NULL

l != NULL || r != NULL

l != NULL && r != NULL

*pred_ptr != (*node_ptr)->l

*pred_ptr == (*node_ptr)->l

補完程式碼

find_free_tree

解說

insert_free_tree

init_block

測試程式

解說

自訂記憶體配置器

功能簡述

init_fl

步驟

說明

fl_alloc

步驟

說明

find_block_by_size

fl_free

步驟

try_merge

merge_b_to_a

說明

效能測試

嘗試減少 find_free_tree 使用

第一週測驗 3

填空

rebuild_list_link 解說

quick_sort 解說

第二週 測驗 1

填空

list_quicksort 解釋

修正 random_shuffle_array

測試程式

原本的 random_shuffle_array

使用 fisher_yates_shuffle

使用 rand 代替 get_unsigned16

list_move_tail 換為 list_move 無法滿足 stable sorting

第二週 測驗 2

填空

clz32

解說

mask 補充

sqrti

解說

最直觀實作

移除乘法運算

合併 last 與 y

向上取整

第二週 測驗 3

填空

程式碼解釋

第一週測驗 `1`

第一週測驗 `2`

`remove_free_tree` 解讀

`l == r == NULL`

`l != NULL || r != NULL`

`l != NULL && r != NULL`

`pred_ptr != (node_ptr)->l`

`pred_ptr == (node_ptr)->l`

`init_fl`

`fl_alloc`

`find_block_by_size`

`fl_free`

`try_merge`

`merge_b_to_a`

嘗試減少 `find_free_tree` 使用

第一週測驗 `3`

`rebuild_list_link` 解說

`quick_sort` 解說

第二週測驗 1

`list_quicksort` 解釋

修正 `random_shuffle_array`

原本的 `random_shuffle_array`

使用 `fisher_yates_shuffle`

使用 `rand` 代替 `get_unsigned16`

`list_move_tail` 換為 `list_move` 無法滿足 stable sorting

第二週測驗 2

`clz32`

`sqrti`

合併 `last` 與 `y`

第二週測驗 3