2024q1 Homework2 (quiz1+2)

第一周測驗 1

void quick_sort(node_t **list)
{
   int n = list_length(list);
   int value;
   int i = 0;
   int max_level = 2 * n;
   node_t *begin[max_level], *end[max_level];
   node_t *result = NULL, *left = NULL, *right = NULL;
   
   begin[0] = *list;
   end[0] = list_tail(list);
           
   while (i >= 0) {
       node_t *L = begin[i], *R = end[i];
       if (L != R) {
           node_t *pivot = L;
           value = pivot->value;
           node_t *p = pivot->next;
           pivot->next = NULL;
   
           while (p) {
               node_t *n = p;
               p = CCCC;
               list_add(n->value > value ? &right : &left, n);
           }

           begin[i] = left;
           end[i] = DDDD;
           begin[i + 1] = pivot;
           end[i + 1] = pivot;
           begin[i + 2] = right;
           end[i + 2] = EEEE;

           left = right = NULL;
           i += 2;
       } else {
           if (L)
               list_add(&result, L);
           i--;
       }
   }
   *list = result;
}

特別將這個函數list_add以圖表示過程

void list_add(node_t **list, node_t *node_t)
{
    node_t->next = *list;
    *list = node_t;
}

當 node_t 要插入 list 原本會長這樣

加入後變這樣

也就是加入在前端。

stack 用途與特性
- 用途 : 先了解 stack 用意，在這個程式碼中使用了兩個變數begin和end來儲存任何子串列的頭跟尾的位置(下圖)，stack 每次都會將左中右的子串列儲存在 stack 中，其中最上端的串列位置所指的子串列，因為屬於右邊所以平均值會最大，用以日後 pop stack 時會先加入最大的數，可以回去看list_add的加入方法是從右到左放入數字。\((f > b > c,d,e\) )
- 特性 : stack 中每層位置指向的串列元素們都會大於自己下方和小於自己上方元素們

知道上述的變數用途後，可以把問題分成兩部分L==R與L!=R每次進入迭代時都會先取 stack 最上端分別給 L與R

L==R : 代表這個子串列只剩一個元素可以直接加入result

L!=R : 代表這個子串列還得繼續將它分成左右子串列再繼續處理

綜合以上各個模組討論就可以把整個程式串起來了 !

測驗一 : 空格填答

AAAA = BBBB = (*left)->next) 走訪全串列
CCCC : 將串列中元素根據 pivot 為標準將 \(<pivot\) 之元素加入 left 串列 \(>pivot\) 之元素加入 right 串列






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

DDDD = &list_tail(left)
EEEE = &list_tail(right)

使用 Linux 核心風格的 List API ：

完整程式碼在 commit
這是我使用的結構，node_t內包含struct list_head去做串接

我保留原本的堆疊方法，將其改儲存struct list_head地址

改進方案：

配置大小的必要性 : 可以發現在十萬筆資料下不管怎麼執行堆疊元素的量都遠小於資料量，因此可以探討 struct list_head *begin[2 * number_of_data]配置大小的必要性

n = 100000
max stack element : 46   cpu clock time : 38384
max stack element : 50   cpu clock time : 29717
max stack element : 58   cpu clock time : 34506

pivot 的選擇 : 首先我先將區域極端值都抓到最前端與我提出的方法去做比較，可以發先區域極端值的排序相當耗時，可見選擇 pivot 相當重要
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 →
以下程式碼都是固定 stack 容量大小下實驗

// 1
max stack element : 38   cpu clock time : 148056
// 2    
max stack element : 10   cpu clock time : 261

這裡我採用不多花空間去紀錄所有值，然後再取中位數，我選擇從左到右比大小，但要比大還比小是交替選擇，來近似取中位數的方法，以下是我尋找 pivot 的程式碼

void find_pivot(struct list_head *head, int n)
{
    int k = 0;
    int stop = n / 2 + 1;
    bool lock = false;
    struct list_head *m = head->next;
    struct list_head *node;
    list_for_each(node, head){
        k++;
        if(!lock){
            m = list_entry(m, node_t, list)->value < 
                list_entry(node, node_t, list)->value ?
                node : m;
            lock = !lock;
        }else{
            m = list_entry(m, node_t, list)->value > 
            list_entry(node, node_t, list)->value ?
            node : m;
            lock = !lock;
        }
        if(k == stop){
            list_move(m,head);
            return;

        }
        
    };
}

考慮到極端值會影響執行時間，因此我決定犧牲一點時間去選擇 pivot，雖然感覺多做一些操作，但實際排序結果卻快上很多

// without find_pivot()
// with find_pivot()

n : 10000        max stack element : 10         cpu clock time : 1050
n : 10000        max stack element : 38         cpu clock time : 3430
    
n : 100000       max stack element : 26         cpu clock time : 10253
n : 100000       max stack element : 46         cpu clock time : 29003
    
n : 1000000      max stack element : 44         cpu clock time : 172131
n : 1000000      max stack element : 64         cpu clock time : 449864

第一周測驗 2

timsort 程式碼部分介紹

引用C語言規格書 6.3.2.3 ，整數與指標間是可以合法轉換

An integer may be converted to any pointer type. Except as previously specified, the
result is implementation-defined, might not be correctly aligned, might not point to an
entity of the referenced type, and might be a trap representation.

static struct pair find_run(...) 中將 run size 轉型成指標後儲存在 head->next->prev

head->next->prev = (struct list_head *) len;

tp 為儲存所有 run 的串列，注意tp->prev...->prev資料比tp 還早進來表示越舊

static struct list_head *merge_collapse(...) 合併判斷標準為最新或者次新的 run 往後數三個來判斷 run size 大小，當最新的兩個\(( A、B )\)大小大於最舊的那個\(( C )\)且如果 \(A>C\) 就將 \(B、C\) 合併，否則 \(A、B\) 合併

timsort 主流程

建立串列並以 NULL 中斷串列連結成單向串列
迭代尋找串列中的 run ，每個 run 使用 result 這個結構進行包裝，並每次都檢查目前發現的 run 中是否需要進行合併，來保持所有 run size 的平衡
迭代尋找完所有 run 後合併所有 run 至 stk_size < 3 為止，合併條件當 \(A>C\) 就先合併 \(B、C\) 否則合併 \(A、B\)

第二周測驗 1

其中 pprev 為何要宣告為指標的指標？ : 根據教材 : 雙向鏈結串列進行節點移去時，會產生的問題。而且 pprev 指向指著自身節點的指標。
變數用途
- hlist_head : 供 hash table 使用
- hlist_node : 填入 table 內，內部含有 next 做碰撞的串接
static inline void node_add(...) : 將索引和值設定好在 node 的結構中透過，再利用 inorder size 計算出 hash value 加入在對應的 hash value 的串列
static struct TreeNode *dfs : 透過find函數找從 hash table 中找到 inoder node 結構中的索引值，其中因為從 preoder 中找到任意子樹的 root 後就可以從 inoder 中找到左右子數節點的個數，在下列舉個左子樹 dfs 範例，pre_low 屬於目前 preoder 中左子數節點索引最低點，所以要繼續走訪的話，最低點索引要再加一，最高點索引就是從 inoder 推算出來的左子樹節點的個數(idx - in_low) 進行相加得到左子數節點在 preoder 中索引的範圍

tn->left = dfs(preorder, pre_low + 1, pre_low + (idx - in_low), inorder,
                   in_low, idx - 1, in_heads, size);

preorder

inorder

static struct TreeNode *buildTree(...) :
將 inorder 所有的值都建立( by INIT_HLIST_HEAD )並計算雜湊值到對應的 in_heads 這個 hash table ( by node_add )，最後就透過dfs去建立整顆樹，即可完成

第二周測驗 2

原理
這個 LRU 是使用 hash table 來實作，首先分析它的結構成員的用途

LRUCache :
- capacity : cache 總容量
- count : chche 目前的使用量
- dhead : 紀錄整個 hash node 的最近使用順序
- hhead : 整個 hash table

typedef struct {
    int capacity;
    int count;
    struct list_head dhead;
    struct hlist_head hhead[];
} LRUCache;

LRUNode :
- node : 用來儲存碰撞的串列元素
- link : 紀錄在 dhead 中的位置

typedef struct {
    int key;
    int value;
    struct hlist_node node;
    struct list_head link;
} LRUNode;

有了以上的結構成員用途後，就可以知道整個程式碼的流程，特別的一點是每次使用lRUCacheGet、lRUCachePut 都必須更新 cache 結構中紀錄 hash node 的使用順序，因為不管是最近讀取或者最近放入，都算剛使用過，因此都會有以下這段程式碼，當找到對應的 key 時必須將 dhead 中自身往前挪移

if (c->key == key) {
    list_move(&c->link, &obj->dhead);
    cache = c;
}

另外如果 cache 容量使用達到限制，必須移除 least recently used 的節點

if (obj->count == obj->capacity) {
        cache = list_last_entry(&obj->dhead, LRUNode, link);
        list_move(&cache->link, &obj->dhead);
        hlist_del(&cache->node);
        hlist_add_head(&cache->node, &obj->hhead[hash]);
    } else {
        cache = malloc(sizeof(LRUNode));
        hlist_add_head(&cache->node, &obj->hhead[hash]);
        list_add(&cache->link, &obj->dhead);
        obj->count++;
    }

第一周測驗 1

測驗一 : 空格填答

使用 Linux 核心風格的 List API ：

改進方案 ：

第一周測驗 2

timsort 程式碼部分介紹

timsort 主流程

第二周測驗 1

第二周測驗 2

第二周測驗 3

Read more

2024q1 Homework5 (assessment)

2024q1 Homework4 (quiz3+4)

2024q1 Homework1 (lab0)

OOOOObjdetect

改進方案：