owned this note changed 4 months ago
Linked with GitHub

2024-02-{20,27} 問答簡記

不同長度的 linked list 是否可以合併?

jouae

案例探討: LeetCode 21. Merge Two Sorted Lists 延伸,我們將討論文中程式碼對不同長度的單向鏈結串列可否做合併?可以的話怎麼做到的?

回顧 C99 規格書(ISO/IEC 9899:TC3)

  • 6.5.13 Logical AND operator

    The && operator shall yield 1 if both of its operands compare unequal to 0; otherwise, it yields 0. The result has type int.

    這邊要注意的是經由 && 邏輯運算子後,得到的型態是 int

  • 6.8.5 Iteration statements

    \(while\) \((\) \(expression\) \()\) statement
    \(do\) statement \(while\) \((\) \(expression\) \()\) ;
    \(for\) \((\) \(expression_{opt}\) ; \(expression_{opt}\) ; \(expression_{opt}\) \()\) statement
    \(for\) \((\) \(declaration\) \(expression_{opt}\) ; \(expression_{opt}\) \()\) statement

    C99規格書中描述 controlling expression 的限制為

    The controlling expression of an iteration statement shall have scalar type.

    這邊 scalar type 根據 C99 6.2.5 Type 第 21 項 (page 36) 定義為

    Arithmetic types and pointer types are collectively called scalar types. Array and structure types are collectively called aggregate types.

    而 Arithmetic types 在同個 section 下,第 18 項定義為

    Integer and floating types are collectively called arithmetic types.

  • 有意思的是在C++11規格書中, 5.14 Logical AND operator 下的規定是 bool 型態

    The && operator groups left-to-right. The operands are both contextually converted to type bool.

可以看到文中 mergeTwoLists(*L1, *L2) 輸入只有兩個 ListNode 結構體的指標。而內部實作的部分則由 while(L1 && L2) 實踐,所以當兩者皆非 null pointer 時,比較完大小順序就可以將兩者合併。

考慮其控制表達式的否命題即為:

L1 or L2 is a null pointer

說明停止條件為 L1 或是 L2 指向 null。兩者同時指向 null 的情形只會發生在傳入函式的 L1 和 L2 皆是 null pointer 。

以下圖例簡易說明兩不同長度的單向串列是如何合併的,L1=[4, 5]L2=[1, 6, 7]ptr 就像針線的針,會依據節點數值大小把針頭(指標)穿過比較後的節點:

  digraph structs {
        node[shape=record]
        rankdir=LR
        ptr [label="<data> ptr"]
        L2_a [label="<data> 1|<header> L2"];
        L2_b [label="<data> 6"];
        L2_c [label="<data> 7"];
        
        L1_a [label="<data> 4|<header> L1"];
        L1_b [label="<data> 5"];
        
        
        L1_a -> L1_b -> null1;
        L2_a -> L2_b -> L2_c -> null2;
}

比較 L1 和 L2 大小。 ptr->next 指向 4 , ptr 串接後的數列為 [4]

  digraph structs {
        node[shape=record]
        rankdir=LR
        ptr [label="<data> ptr"]
        L2_a [label="<data> 1|<header> L2"];
        L2_b [label="<data> 6"];
        L2_c [label="<data> 7"];
        
        L1_a [label="<data> 4"];
        L1_b [label="<data> 5|<header> L1"];
        
        ptr->L1_a -> L1_b -> null1;
        L2_a -> L2_b -> L2_c -> null2;
}

比較 L1 和 L2 大小。 ptr->next 指向 5 , ptr 串接後的數列為 [4, 5]

  digraph structs {
        node[shape=record]
        rankdir=LR
        ptr [label="<data> ptr"]
        L2_a [label="<data> 1|<header> L2"];
        L2_b [label="<data> 6"];
        L2_c [label="<data> 7"];
        
        L1_a [label="<data> 4"];
        L1_b [label="<data> 5"];
        null1 [label="<data> null1|<header> L1"]
        
        L1_a -> L1_b -> null1;
        L2_a -> L2_b -> L2_c -> null2;
        ptr -> L1_a
}

跳出迴圈,判斷 ptr->next 該接到哪裡。由於 L1 目前為 null , ptr->next 指向 L2 串接後的數列為 [4, 5, 1, 6, 7] 合併完成。

能否使用 linked list 去實作 quicksort

joec1368

針對 Linux 核心的場景,強調是否可以達成 in-place algorithm

何時用到 bubble sort 或 insertion sort?

wilicw

  • 已經接近排序好的 list。
  • 任務優先權沒有顯著變化

Linus 提到的 bad taste

The mind behind Linux | Linus Torvalds | TED 中的程式碼為何是 bad taste?

  • 避免 headnull
  • 使用 indirect pointer 來減少特殊案例的處理

排序程式碼練習

c24094031@gs.ncku.edu.tw

考慮以下程式碼,使用 list.h

#include <stddef.h>
#include <stdint.h>

#include "list.h"

struct listitem {
    uint16_t i;
    struct list_head list;
};

static inline int cmpint(const void *p1, const void *p2)
{
    const uint16_t *i1 = (const uint16_t *) p1;
    const uint16_t *i2 = (const uint16_t *) p2;

    return *i1 - *i2;
}

static void list_insert_sorted(struct listitem *entry, struct list_head *head)
{
    struct listitem *item = NULL;

    if (list_empty(head)) {
        list_add(&entry->list, head);
        return;
    }

    list_for_each_entry (item, head, list) {
        if (cmpint(&entry->i, &item->i) < 0) {
            list_add_tail(&entry->list, &item->list);
            return;
        }
    }

    list_add_tail(&entry->list, head);
}

static void list_insertsort(struct list_head *head)
{
    struct list_head list_unsorted;
    struct listitem *item = NULL, *is = NULL;

    INIT_LIST_HEAD(&list_unsorted);
    list_splice_init(head, &list_unsorted);
    /* Put your code here */
}

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 →
上方程式碼不完整

為什麼不用在環狀鏈結串列中使用 swap 就可以做到交換?

jouae

最簡單實作的 swap 如下:

void swap(int *a, int *b)
{
    int tmp;
    tmp = *a;
    *a = *b;
    *a = tmp;
}

可以看到上述的部分需要額外一個變數 tmp 來暫存交換的值。

而在單向鏈結串列中,不用做到額外變數,只要使用間接指標( indirect pointer )。參見你所不知道的 C 語言: linked list 和非連續記憶體——Merge Sort 的實作

struct ListNode *mergeTwoLists(struct ListNode *L1, struct ListNode *L2) {
    struct ListNode *head = NULL, **ptr = &head, **node;

    for (node = NULL; L1 && L2; *node = (*node)->next) {
        node = (L1->val < L2->val) ? &L1: &L2;
        *ptr = *node;
        ptr = &(*ptr)->next;
    }
    *ptr = (struct ListNode *)((uintptr_t) L1 | (uintptr_t) L2);
    return head;
}

merge sort 實作何處可用 list_splice

a1157857220

Timsort 什麼時候用到 list_splice

jouae

在 Python 官方文件中 listsort.txt 紀錄這個由 Peters, Tim 開發的 Timsort 跟實驗內容,以下摘入自開頭片段:

This describes an adaptive, stable, natural mergesort, modestly called timsort.

在 Timsort 中,討論的基本單位稱作為 run ,為一非遞減或是嚴格遞減的數列。例如:

[60, 50, 40, 1, 2, 3]

可以拆解成兩個 run:

run 1: [60, 50, 40]
run 2: [1, 2, 3]

而向上述原始數列就已經有排序的子數列,這些子數列稱作為 natural run ,而其餘沒有排序過的元素,會先蒐集起來至一定數量後,藉由插入排序( insert sort )來排序成為一個 run 。同時為避免比較次數過多, Tim 在實作的過程中有限制每個 run 的上限為 64。

在過往學員 yanjiew1 紀錄中,詳述 Timsort 流程。

回頭來看 list_splice(*list, *head),由兩個輸入組成 *list*head ,兩者皆是 list_head 結構體的指標,作用為將 list 這個節點包含其後續節點,繫( splice )於 head 之後。所以在進行合併各個 run 的過程中, list_splice 就在此時上場。

在 Linux list_sort.c 中合併的實踐是由 *merge(void *priv, list_cmp_func_t cmp, struct list_head *a, struct list_head *b) 達成。由於並非環狀鏈結串列的合併,跟我們預期 list_splice 的運作不一樣, list_splice 針對環狀結構操作。

注意:在此的 *a*b 為 null-terminated singly-linked list 。詳見原始碼中 list_sort() 的部分。

merge_final() 部分中,則還原了原本串列的環狀結構。

在函數的一開始先把單向串列改成雙向串列

// 將 a 鏈結在 tail 之後
// 並將 a 的前一個節點指向 tail 形成 doubly linked
tail->next = a;
a->prev = tail;

// 更新 tail 位置為 a
tail = a;
a = a->next;

函式的最後將雙向串列頭尾相連形成環狀結構

/* And the final links to make a circular doubly-linked list */
tail->next = head;
head->prev = tail;

整個過程簡化的話,就是 list_splice 的功能。

為何 list.h 選定 0x00100100 與 0x00200200 作為無效的地址?

Jimmy01240397

我在做 git log | grep <address> 之類的操作後依然沒有詳細說明。只知道該 address 第一次出現是在 commit 9a69abf80edf2ea0dac058cab156879d29362788 "menuconfig: Add "breadcrumbs" navigation aid" 的位置

static inline void list_del(struct list_head *node)
{
    struct list_head *next = node->next;
    struct list_head *prev = node->prev;

    next->prev = prev;
    prev->next = next;

#ifdef LIST_POISONING
    node->prev = (struct list_head *) (0x00100100);
    node->next = (struct list_head *) (0x00200200);
#endif
}

linux/poison.h 的註解:

These are non-NULL pointers that will result in page faults under normal circumstances, used to verify that nobody uses non-initialized list entries.

list_del 執行時,會將節點的的 prev 和 next 指向一個特定的地址,當存取到該地址時,會觸發 page fault

在《Linux Device Drivers 3/e》第四章 Debugging Techniques 的引言提到,Linux 核心的程式碼不易在除錯器中運作、錯誤也不易重現,不過一旦引發錯誤時,可能會讓整個系統崩潰,而造成錯誤的證據則隨之消失。

除錯的的其一手法就是將這種有毒 (poison) 的值設在使用前後,當該數值變更時,我們就會知道非預期的狀況發生。

諺語: One man's meat is another man's poison

有了這樣的設計,我們便可在除錯時知道 : 若 node->nextnode->prev 分別指向 LIST_POISON1LIST_POISON2 的話,就代表發生 use-after-free 的情況,像是 lib/list_debug.c 便是 Linux 核心中對應的除錯程式碼。

若無 LIST_POISONING 的設計,在 list_del() 時將 node->nextnode->prev 都指向 NULL,除錯階段就無法得知此時的 NULL 代表的是 uninitialized 抑或被釋放後才指派的。

至於不直接釋放節點的原因,可參閱 Kernel Self-Protection 中 Memory poisoning 的部份得知:

When releasing memory, it is best to poison the contents, to avoid reuse attacks that rely on the old contents of memory. E.g., clear stack on a syscall return (CONFIG_GCC_PLUGIN_STACKLEAK), wipe heap memory on a free. This frustrates many uninitialized variable attacks, stack content exposures, heap content exposures, and use-after-free attacks.

2024q1 第 2 週測驗題第 1 題

weihsinyeh

建立二元樹需要有透過得知中序(in-order)與前序 (pre-order) 或是後序 (post-order)才能具體說明一個獨一無二的二元樹的原因說明舉例如下。

前序是 [A B C]
透過前序知道 A 是 中間的那個點,但卻無法透過前序知道 B C 相對於A的左邊還是右邊。
因此產生的二元樹可能如下中序分別是 [B C A], [B A C] , [A B C]

   A         A     A
  /         / \     \
 B         B   C     B
  \                   \
   C                   C
 (1)       (2)      (3)

第一個樹:由中序知道 A 是 中間的那個點,B C 相對於A在左邊。所以都在 A 的左子樹中。
第二個樹:由中序知道 A 是 中間的那個點,B 相對於 A 在左邊,所以在 A 的左子樹中。C 相對於A在右邊,所以在 A 的右子樹中。
第三個樹:由中序知道 A 是 中間的那個點,B C 相對於A在右邊。所以都在 A 的右子樹中。
所以 DFS 中的實作是透過 preorder 會藉由 find 找到preorder[pre_low]inorder中的位置 idx

由圖得知在 idx 左邊的都會被放到左子樹,在idx右邊的都會被放到右子樹。

因此對應到左子樹的在中序涵蓋的範圍 : [in_low,idx-1],右子樹在中序涵蓋的範圍 : [idx+1,in_high]

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

而觀察剛剛的前序可以知道他的分佈的規則就是 [中點 左子樹 右子樹],從這裡就可以看到只要知道左子樹有多少個,右子樹有多少個,就可以知道在前序的範圍了。

而因為 pre_low 是中點
左子樹在前序的涵蓋範圍 : [pre_low + 1, pre_low + (idx - in_low)] 其實就是pre_low往後左子樹的在中序涵蓋的範圍 : [in_low,idx-1]
右子樹在前序的涵蓋範圍 : [pre_high - (in_high - idx - 1), pre_high] 其實就是pre_high往前右子樹的在中序涵蓋的範圍 : [idx+1,in_high]

也因此從這樣的分析其實知道如果題目提供的只有後序與中序,我只要從後序的最後一個往前讀。
改變範圍即可因為後序的分佈是 [左子樹 右子樹 中點]post_high是中點。
所以左子樹在後序的涵蓋範圍:[post_low, post_low + (idx - 1 - in_low)]
右子樹在後序的涵蓋範圍:[post_high - 1 - (in_high - (idx+1)) , post_high-1]

所以這樣也就明白中序在建立二元樹中缺一不可的角色,而前序與後序則是可以只挑其中一個。
find 函式則是用 hash table 去紀錄in-order的位置而已,可換成其他資料結構來實作。

Select a repo