# 2024q1 Homework2 (quiz1+2)
contributed by < [`blue76815`](https://github.com/blue76815/Linux-2024q1-Homework2-quiz1-2-?tab=readme-ov-file) >
[第 1 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz1)
## 測驗 `1`
:::success
延伸問題：
1. 解釋上述程式碼的運作原理，提出改進方案並予以實作。
2. 使用 Linux 核心風格的 List API 改寫上述程式碼，並針對鏈結串列，提出可避免最差狀況的快速排序實作，應設計效能評比的測試程式。
:::
### 1. 解釋程式碼運作原理
```c
typedef struct __node {
struct __node *left, *right;
struct __node *next;
long value;
} node_t
```
:::success
### 疑問：
此 Link list 節點，指向下一個節點位址時，是儲存到 `*next` 結構成員
問題是 `*left`, `*right` 沒指向下一個節點位址，
請問是在程式哪個步驟中有處理下個節點位址，儲存到`*left` 和 `*right;`結構成員的？
:::
#### **`list_tail()`**
**尋找**鏈結串列 ( link list ) 的**末端節點位址**
```c
node_t *list_tail(node_t **left)
{
/* 當 (*left)->next 還有紀錄節點位址
* 就繼續指向下一個節點
* */
while ((*left) && (*left)->next)
left = &((*left)->next );//AAAA
return *left;
}
```
#### **`list_length()`**
**計次**鏈結串列 ( link list ) 的**節點個數**
```c
int list_length(node_t **left)
{
int n = 0;
while (*left) {
/* 一直指向下一個節點，順便 ++n 計次
* 直到 *left 節點位址為NULL尾端時，才跳出不計次
* */
++n;
left = &((*left)->next);// BBBB
}
return n;
}
```
#### **`list_construct()`**
**建立新節點**，並將資料 `n`，存入指定節點內的 `value` 成員裡
```c
node_t *list_construct(node_t *list, int n)
{
node_t *node = malloc(sizeof(node_t));//建一個新節點
node->next = list; //
node->value = n;//插入節點資料
return node;//回傳節點位址
}
```
:::info
`list_construct()` 在測驗1中，是用在**將 `test_arr[count]` 陣列裡的資料**一個一個的**存放到 `list` 鍊結串列的節點內**
```c
int main(int argc, char **argv)
{
node_t *list = NULL;
size_t count = 100000;
int *test_arr = malloc(sizeof(int) * count);
for (int i = 0; i < count; ++i)
test_arr[i] = i;
shuffle(test_arr, count);/* 對 test_arr[] 陣列內的資料洗牌*/
while (count--)
list = list_construct(list, test_arr[count]);
/*將 test_arr[count] 陣列裡的資料
* 一個一個的存放到 `list` 鍊結串列的節點內
* */
...
}
```
`list_construct()`和
`list_add()`不同
**`list_add()`** 是在鏈結串列 (link list)中，**插入一個節點** ( `list_add()`函式內，沒有建立一個新節點的功能)
:::
#### **`list_add()`**
在鏈結串列 ( link list )中，**插入一個節點**
註明: `list_add()`函式內，沒有建立一個新節點的功能
```c
void list_add(node_t **list, node_t *node_t)
{
node_t->next = *list;
*list = node_t;
}
```
#### **`list_free()`**
鏈結串列 ( link list )，**釋放節點**
```c
void list_free(node_t **list)
{
node_t *node = (*list)->next;
while (*list) {
free(*list);
*list = node;
if (node)
node = node->next;
}
}
```
#### **`quick_sort()`**
:::success
根據 [動畫圖解資料結構：使用C語言](https://www.sanmin.com.tw/product/index/006550630)
> **快速演算法（Quick Sort）** 又稱為**分割交換排序法**，
> 其觀念是先在資料中找到一個**中間值**，
> 把**小於中間值**的資料**放在左邊**
> 而**大於中間值**的資料**放在右邊**，
> 再以同樣的方式分別處理左右邊兩邊的資料，直到完成為止
備註：在 [Introduction to Algorithms, 4/e](https://www.tenlong.com.tw/products/9780262046305) CH7 Quicksort 介紹中，不叫**中間值**，而是稱為 **pivot**
pivot: 樞紐
:::
```c
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 = p->next;//CCCC
list_add(n->value > value ? &right : &left, n);
}
begin[i] = left;
end[i] = list_tail(&left) ;//DDDD
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] =list_tail(&right) ;//EEEE
left = right = NULL;
i += 2;
} else {
if (L)
list_add(&result, L);
i--;
}
}
*list = result;
}
```
詳細流程介紹參閱
[quit sort 非遞迴版 程式步驟詳解](https://hackmd.io/@blue76815/BybOD3mxA)
### 2. 改成 Linux 核心的 List API 撰寫風格
在我們的專案文件夾裡，引入 [lab0](https://github.com/sysprog21/lab0-c/blob/master/list.h) 的 `list.h`
```c
#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include "list.h"
```
Linux List API 使用方法，參閱
* [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#Linked-list-%E5%9C%A8-Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A8%8B%E5%BC%8F%E7%A2%BC)
* [The Linux Kernel API](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html)
目標把
```c
void list_add(node_t **list, node_t *node_t)
node_t *list_tail(node_t **left)
int list_length(node_t **left)
node_t *list_construct(node_t *list, int n)
void list_free(node_t **list)
static bool list_is_ordered(node_t *list)
```
替換成 `list.h` 內的 API
有參考 [vax-r](https://hackmd.io/@vax-r/linux2024-homework2#%E6%B8%AC%E9%A9%97%E4%B8%80) 同學的作法，寫成
```c
void quick_sort(struct list_head **head)
{
int n = list_length(*head);
int pivot_value;
int i = 0;
int max_level = 2 * n;
struct list_head *begin[max_level];
begin[0] = *head;
for (int i = 1; i < max_level; i++)
begin[i] = list_new();
struct list_head *result = list_new(), *left = list_new(), *right = list_new();//OK
while (i >= 0) {
struct list_head *L = begin[i]->next, *R=begin[i]->prev;
if (L!=R) {
node_t *pivot = list_remove_head(begin[i]);
pivot_value = pivot->value;
node_t *entry, *safe;
list_for_each_entry_safe(entry, safe, begin[i], list){
list_del(&entry->list);
list_add(&entry->list,entry->value > pivot_value? right:left);
}
list_splice_init(left, begin[i]);
list_add(&pivot->list, begin[i + 1]);
list_splice_init(right, begin[i + 2]);
i += 2;
} else {
if (list_is_singular(begin[i]))
list_splice_init(begin[i], result);
i--;
}
}
for (int i = 0; i < max_level; i++)
list_free(begin[i]);
list_free(left);
list_free(right);
*head = result;
}
```
詳細變更，請看我的 Github [3723ace](https://github.com/blue76815/Linux-2024q1-Homework2-quiz1-2-/commit/3723aceaa7f77c3d8c7ef79c36eb7a8f0a7a6b15) 紀錄
### 3. 提出可避免最差狀況的快速排序實作，設計效能評比
### 3.1 撰寫 gunplot 繪圖程式
根據 [在 Linux 中以特定的 CPU 核心執行程式](https://blog.gtwang.org/linux/run-program-process-specific-cpu-cores-linux/)
:::warning
makefile 中
`sudo taskset -c 0 ./main 10000 > data.csv `
其中 `sudo taskset -c 0 ` 就是要將程式綁定在1個cpu上執行
:::
根據 [man clock_gettime](https://man7.org/linux/man-pages/man3/clock_gettime.3.html)
使用 clock_gettime()函數，計時 nanosecond
先作到量測 1000筆 資料做 q_sort 計時為例
```c
int main(int argc, char **argv)
{
//for (int i = 10; i <= 100000; i++) {
for (int i = 10; i <= 1000; i++) {
unsigned long long time_non_sort = 0, time_sort= 0;
struct timespec t1, t2;
struct list_head *list = list_new();
size_t count = i, data_number=i;
int *test_arr = malloc(sizeof(int) * count);
for (int i = 0; i < count; ++i)
test_arr[i] = i;
shuffle(test_arr, count);
while (count--)
list = list_construct(list, test_arr[count]);
//list_print(list);
clock_gettime(CLOCK_MONOTONIC, &t1); //撮記時間t1
quick_sort(&list);//真正跑分析的函式
clock_gettime(CLOCK_MONOTONIC, &t2); //撮記時間t2
time_non_sort += (unsigned long long) (t2.tv_sec * 1000000000 + t2.tv_nsec) -
(t1.tv_sec * 1000000000 + t1.tv_nsec);//轉成 nanosecond
assert(list_is_ordered(list));
clock_gettime(CLOCK_MONOTONIC, &t1); //撮記時間t1
quick_sort(&list);//真正跑分析的函式
clock_gettime(CLOCK_MONOTONIC, &t2); //撮記時間t2
time_sort += (unsigned long long) (t2.tv_sec * 1000000000 + t2.tv_nsec) -
(t1.tv_sec * 1000000000 + t1.tv_nsec);//轉成 nanosecond
assert(list_is_ordered(list));
printf("%ld,%llu,%llu\n", data_number, time_non_sort, time_sort);
//list_print(list);
list_free(list);
free(test_arr);
}
return 0;
}
```
#### gunplot ：撰寫 plot_qsort.gp
```
reset
set xlabel 'data number'
set ylabel 'nanosecond'
set title 'perfomance comparison'
set term png enhanced font 'Times_New_Roman, 10'
set output 'qsort.png'
set xtics 0,100 //x軸 每間隔100點，設一個座標
set datafile separator ","
set key left
plot \
"data.csv" using 1:2 with linespoints linewidth 1 title "qsort", \
"data.csv" using 1:3 with linespoints linewidth 1 title "non-qsort"
```
#### makefile
```
SHELL = /bin/bash
CC = gcc
CFLAGS = -g -pthread
SRC = $(wildcard *.c)
EXE = $(patsubst %.c, %, $(SRC))
SRC2 = $(wildcard *.csv)
SRC3 = $(wildcard *.png)
all: ${EXE}
%: %.c
${CC} ${CFLAGS} $@.c -o $@
plot:
sudo taskset -c 0 ./main > data.csv
gnuplot plot_qsort.gp
mv data.csv 1000_data.csv
mv qsort.png 1000_qsort.png
clean:
rm ${EXE}
rm ${SRC2}
rm ${SRC3}
```
#### 編譯驗證程式
```
$ make
$ make plot
sudo taskset -c 0 ./main > data.csv
gnuplot plot_qsort.gp
mv data.csv 1000_data.csv
mv qsort.png 1000_qsort.png
```
```
$ ls
1000_data.csv 1000_qsort.png cpucycles.h list.h main main.c makefile plot_qsort.gp
```
可看到生成
1000_data.csv 1000_qsort.png 這兩個檔案
1000_qsort.png
### 4. 針對鏈結串列，提出可避免最差狀況的快速排序實作，應設計效能評比的測試程式。
### 4.1 quick_sort worst case
根據這篇 [快速排序 (Quick Sort)](https://kopu.chat/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F-quick-sort/) 提到
quick_sort worst case 是發生在
> **Pivot 恰好是該資料陣列的最小值或最大值**，使得切割無法產生一分為二的效果。
>
> $T(n)=c$$\times$$n+T(n-1)+T(0),$ c$\times$n 為切割時間
>
> $T(n)=T(n-1)+c$$\times$$((n-1)+n)=...=T(1)+c$$\times$$(2+...+n)$
>
> $T(n)=c$$\dfrac{(n+2)(n-1)}{2}$
>
> 故時間複雜度為 $O(n^2)$
### 4.2 提昇效能方法：
根據 [避免 Quick Sort 的 Worst Case 發生](https://kopu.chat/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F-quick-sort/#lwptoc4)
> 有鑑於**時間複雜度高達 $O(n^2)$**，要怎麼樣才能避免取到最小或最大值的 Worst Case 呢？
>
> 以下提供三種可能解法：
> 1. Middle-of-Three 方法
> 2. Randomized Quick Sort
> 3. 使用 Median-of-Medians 作為基準
### 4.3 撰寫程式
根據 [避免 Quick Sort 的 Worst Case 發生](https://kopu.chat/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F-quick-sort/#lwptoc4) 提到的方法
### 4.3.1 修改 find_middle
之前的 `find_middle()` 每次要先做 `list_length(head)/2; `時間複雜度太長
```c
struct list_head *find_middle(struct list_head *head)
{
//用 list_length(struct list_head *head) 方法取一半
int n = list_length(head)/2;
struct list_head *middle,*safe;
printf("list_length=%d\r\n",n);
list_for_each_safe (middle, safe,head) {
if (n == 0)
break;
n--;
}
return middle;
}
```
因次參照 Jserv 老師的
[分析「快慢指標」](https://hackmd.io/@sysprog/ry8NwAMvT)作法
改成
```c
node_t *get_middle_node(struct list_head *head) {
struct list_head *slow = head->next;
struct list_head *fast = head->next;
while (fast != head && fast->next != head) {
slow = slow->next;
fast = fast->next->next;
}
return list_entry(slow, node_t, list);
}
```
### 4.3.2 實做 Middle-of-Three
根據 [1. Middle-of-Three 方法](https://kopu.chat/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F-quick-sort/#%E9%81%BF%E5%85%8D_Quick_Sort_%E7%9A%84_Worst_Case_%E7%99%BC%E7%94%9F)
> step1.取出 link list 頭 (low_node) 尾(high_node) 中間(middle_node) ，這三個節點
>
> step2.前面三筆資料，找出中間值節點( `middle_value_node` )。 `find_median_of_three()`
>
> step3.中間值節點 和 頭節點 交換 `swap_nodes()`
>
> step4.讓新的 頭節點 作為 pivot
詳細程式實做，請看
github commit [Implement median_of_three qsort.](https://github.com/blue76815/Linux-2024q1-Homework2-quiz1-2-/commit/849adf0e659e6786e1df1e0163b1e551aae681dc)
```c
/* 從三筆資料，找出中間值節點 */
node_t *find_median_of_three(node_t *a, node_t *b, node_t *c) {
if ((a->value > b->value && a->value < c->value) || (a->value > c->value && a->value < b->value)) {
return a;
} else if ((b->value > a->value && b->value < c->value) || (b->value > c->value && b->value < a->value)) {
return b;
} else {
return c;
}
}
/**
* https://github.com/torvalds/linux/blob/master/include/linux/list.h
* list_replace - replace old entry by new one
* @old : the element to be replaced
* @new : the new element to insert
*
* If @old was empty, it will be overwritten.
*/
static inline void list_replace(struct list_head *old, struct list_head *new)
{
new->next = old->next;
new->next->prev = new;
new->prev = old->prev;
new->prev->next = new;
}
/**
* https://github.com/torvalds/linux/blob/master/include/linux/list.h
* list_swap - replace entry1 with entry2 and re-add entry1 at entry2's position
* @entry1: the location to place entry2
* @entry2: the location to place entry1
*/
static inline void list_swap(struct list_head *entry1, struct list_head *entry2)
{
struct list_head *pos = entry2->prev;
list_del(entry2);
list_replace(entry1, entry2);
if (pos == entry1)
pos = entry2;
list_add(entry1, pos);
}
struct list_head* swap_nodes(node_t *node1, node_t *node2, struct list_head *head) {
if (node1 == node2) return head;
list_swap(&node1->list,&node2->list);
// If node1 or node2 was the head, update head
if (&node1->list == head) {
head = &node2->list;
} else if (&node2->list == head) {
head = &node1->list;
}
return head;
}
```
和 `q_sort` 差別是，加入 `median_of_three（begin[i]）`預先處裡 link list
```c
void quick_sort_median_of_three(struct list_head **head)
{
....
while (i >= 0) {
struct list_head *L = begin[i]->next, *R=begin[i]->prev;
if (L!=R) {
begin[i]=median_of_three(begin[i]); // 在這行加入 median_of_three（begin[i]）預先處裡 link list
node_t *pivot = list_remove_head(begin[i]);
pivot_value = pivot->value;
....
}
```
### 4.3.3 實做 Randomized Quick Sort
根據文章中 [2. Randomized Quick Sort](https://kopu.chat/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F-quick-sort/#lwptoc4) 提到
> ## 2. Randomized Quick Sort
>
> **用亂數選取的方式，隨機挑一個值作為 pivot。**
>
> **當然，這還是可能會發生 Worst Case 高達 O(n2) 的問題，只是機率比較低。** Average Case 與 Best Case 同樣是 O(n log n)。
>
> 所以我們也可以把以上兩種改進合併──**先用亂數任選三個，再用其中的中間值作為 pivot。**
詳細程式實做，請看
github commit [Implement random_pivot qsort.](https://github.com/blue76815/Linux-2024q1-Homework2-quiz1-2-/commit/7784fa7b66d2fb662eae42a87472b4c989d0b69e)
和 `q_sort` 差別是加入，這三行是 做 random pivot
```c
/*
step0. 先準備好 begin[i]的 head 節點，準備之後做交換用==> *head_node
step1. 用亂數任選三個，再用其中的中間值作為 pivot。
step2. 再用其中的中間值作為 pivot。
step1~step2 就是 random_pivot_node=random_pivot(begin[i]); 在處裡
最後產生 random_pivot_node
step4. swap_nodes(begin[i], head_node, random_pivot_node);
代表 begin[i] link list 的 pivot 要改成 random_pivot_node做排序
*/
node_t *head_node = list_first_entry(begin[i], node_t, list);
node_t *random_pivot_node=random_pivot(begin[i]);
begin[i]=swap_nodes(head_node, random_pivot_node,begin[i]);
```
```c
void quick_sort_random_pivot(struct list_head **head)
{
...
while (i >= 0) {
struct list_head *L = begin[i]->next, *R=begin[i]->prev;
if (L!=R) {
// 這三行是 做 random pivot
/*
step0. 先準備好 begin[i]的 head 節點，準備之後做交換用==> *head_node
step1. 用亂數任選三個，再用其中的中間值作為 pivot。
step2. 再用其中的中間值作為 pivot。
step1~step2 就是 random_pivot_node=random_pivot(begin[i]); 在處裡
最後產生 random_pivot_node
step4. swap_nodes(begin[i], head_node, random_pivot_node);
代表 begin[i] link list 的 pivot 要改成 random_pivot_node做排序
*/
node_t *head_node = list_first_entry(begin[i], node_t, list);
node_t *random_pivot_node=random_pivot(begin[i]);
begin[i]=swap_nodes(head_node, random_pivot_node,begin[i]);
node_t *pivot = list_remove_head(begin[i]);
pivot_value = pivot->value;
...
}
```
### 4.4 量測效能
~~因為我們的 quick_sort 排序完，節點是**升冪排序**
例如 1-->2-->3-->4-->5-->7~~
~~所以 worst case 我們餵**降冪排序**的節點資料，給 quick_sort 排序~~
詳細程式實做，請看
github commit [Implement plot_qsort.gp to measure 3 ways of qsort performance.](https://github.com/blue76815/Linux-2024q1-Homework2-quiz1-2-/tree/aa80cb545da54cc53ab2d8c60a1db66a192ee577)
編譯量測效能
以量測2000筆為例
```
$ make
$ make plot
sudo taskset -c 0 ./main > data.csv
gnuplot plot_qsort.gp
mv data.csv 2000_data.csv
mv qsort.png 2000_qsort.png
```
:::info
加入 median_of_three 和 random_pivot 處理，**根本沒有使排序更省時**，相反的
**因為 `quick_sort_median_of_three()`內多了 `median_of_three(begin[i])`交換節點的處理步驟**
```c
void quick_sort_median_of_three(struct list_head **head)
{
...
while (i >= 0) {
struct list_head *L = begin[i]->next, *R=begin[i]->prev;
if (L!=R) {
/* type35 median_of_three 解決辦法
當`begin[i]` link list 長度有3個節點以上，
才丟進 `median_of_three(begin[i]);` 處裡，
*/
begin[i]=median_of_three(begin[i]); // 在這行加入 median_of_three（begin[i]）預先處裡 link list
node_t *pivot = list_remove_head(begin[i]);
pivot_value = pivot->value;
}
```
**`quick_sort_random_pivot`內多了`random_pivot(begin[i]);`交換節點的處理步驟**
```c
void quick_sort_random_pivot(struct list_head **head)
{
...
while (i >= 0) {
struct list_head *L = begin[i]->next, *R=begin[i]->prev;
if (L!=R) {
node_t *head_node = list_first_entry(begin[i], node_t, list);
node_t *random_pivot_node=random_pivot(begin[i]);
begin[i]=swap_nodes(head_node, random_pivot_node,begin[i]);
node_t *pivot = list_remove_head(begin[i]);
pivot_value = pivot->value;
...
}
```
反而比 `q_sort` 更耗費處理時間
- [ ] 問題：在找 median_of_three，其他**步驟更精簡**的實做方法，才能**降低時間複雜度**
:::
---
## 測驗 `2`
:::success
延伸問題：
1. 解釋上述程式碼的運作原理，提出改進方案並予以實作。
2. 將改進過的 Timsort 實作整合進 [sysprog21/lab0-c](https://github.com/sysprog21/lab0-c)，作為另一個有效的排序命令，應設計效能評比的測試程式，確保測試案例符合 Timsort 設想的資料分布樣式。
:::
## 1. 解釋上述程式碼的運作原理
### 1.1 Timsort 演算法介紹
Timsort 混和了合併排序法(Merge Sort)及插入排序法(Insertion Sort)
根據 [測驗 2](https://hackmd.io/@sysprog/linux2024-quiz1#%E6%B8%AC%E9%A9%97-2) 描述提到
> Timsort 致力於從以下三個方面，改進合併排序演算法：
>
> 1. 加快合併（merge）過程
> 2. 減少進行合併的次數。
> 3. 在某些特定情況下，尋找比合併排序更有效的排序方法
### 1.2 Timsort 演算法步驟
:::success
先歸納成以下3個主要步驟
step1. 將遞增數列分割成一組一組 run
step2. 合併（用 Merge sort 做合併）
step3. Galloping mode
:::
以下詳細介紹步驟細節
#### step1.分割成 run
分割要領
1. 數列中，**一路遞增**的**數組**，**當成一組run數列**
例如 [測驗2](https://hackmd.io/@sysprog/linux2024-quiz1#%E6%B8%AC%E9%A9%97-2) 中
1,2,3,4,3,2,4,7,8 數列中
可以拆分成3個run
* 1,2,3,4==>**一路遞增，當成一組run數列**
* 3,2==>遇到**遞減的數列**，會被反轉成**遞增**的序列，變成2,3
* 4,7,8==>**一路遞增,當成一組run數列**
2. 合併序列時，
* 若 run 的數量**等於**或**小於 2 的冪( $2^n$ 個)**，**效率會最高（[指方便待會的 Merge sort 效率最高](https://jason18153.medium.com/%E6%9C%80%E8%B2%BC%E8%BF%91%E7%8F%BE%E5%AF%A6%E7%9A%84%E6%8E%92%E5%BA%8F%E6%BC%94%E7%AE%97%E6%B3%95-timsort-a75da75b65a2)）**；
* 若**大於** **2 的冪( $2^n$ 個)**，**效率就會特別低**。
3. 每個 run 的長度，定義一個 minrun (最小運行長度)
* 若長度太短，就用**二分插入排序**，將 run 後面的元素插入到前面的 run 裡面。
例如 run 的長度設定 minrun=5，則在分割
1,2,3,4,3,2,4,7,8數列時，
按照**一路遞增，當成一組run數列**規則
只有1,2,3,4是一組run，但是**因為設定 minrun=5（一組run數列最小長度得5個數字）**，因此得取
**1,2,3,4,3 當成一組run數列**，還要用**二分插入排序**整理 run 變成
**1,2,3,3,4**
4. minrun要定義多少個，參照 [最貼近現實的排序演算法- Timsort](https://jason18153.medium.com/%E6%9C%80%E8%B2%BC%E8%BF%91%E7%8F%BE%E5%AF%A6%E7%9A%84%E6%8E%92%E5%BA%8F%E6%BC%94%E7%AE%97%E6%B3%95-timsort-a75da75b65a2)
> 那問題來了，該如何知道這個 minrun 的值是多少呀？這個 minrun 必須滿足三個條件，
>
> 1. **minrun必須小於 64 ，因為大於 64 的 Insertion sort 效率會變差。**
> 2. 盡可能的平均分配，不能有全部都剛好是 minrun 而最後一個只剩下很少元素的情況發生
> 3. 盡可能將**切割完的 run 的數量控制在二的次方（前面講的 2的冪），方便待會的Merge sort**
>
> 因此 Tim 想了一個非常聰明的方法，先將序列的總長度表示成二進位，取出前六個數之後如果後面還有值，就+1，舉個例子：如果總長度是197，換成二進位那就是 11000101，取出前六個數 110001 = 49，後面還有 01 所以將49+1=50，那麼在最壞的情況下，會被拆成 50 50 50 47，剛好滿足了上面的那三個條件，這個方法真的相當聰明。以上我們已經將 Timsort 的切割完全介紹完畢。
#### step2.合併
根據 [最貼近現實的排序演算法- Timsort](https://jason18153.medium.com/%E6%9C%80%E8%B2%BC%E8%BF%91%E7%8F%BE%E5%AF%A6%E7%9A%84%E6%8E%92%E5%BA%8F%E6%BC%94%E7%AE%97%E6%B3%95-timsort-a75da75b65a2)
> ## 合併
> 為了達到高效率且省空間的合併，Tim 精心設計了合併的細節，先聊大方向的合併，**我們手上現在有非常多個 run，我們從最右邊抓三個 run 出來，由左到右依次命名為 runX, runY, runZ，只要不滿足以下兩個條件的其中之一，就將 runY 與 ( runX 和 runZ 較小的 )合併：**
>
> 1. runX 長度 > runY + runZ 長度
> 2. runY 長度 > runZ 長度
上面那段合併條件限制，就是對應到 成大 [測驗二](https://hackmd.io/@sysprog/linux2024-quiz1#%E6%B8%AC%E9%A9%97-2) 描述的
> Timsort 採用一組堆疊 (stack) 來暫存 run，此舉是為了避免在一開始就掃描整個資料範圍來產生 run，從而降低記憶體開銷。過程中，Timsort 運用 merge_collapse 函式來確保堆疊上的 run 長度保持平衡。該函式主要檢查堆疊頂端的 3 個 run 是否滿足以下原則：
>
> **A 的長度要大於 B 和 C 的長度總和。
> B 的長度要大於 C 的長度。**
#### step3.Galloping mode
根據 [最貼近現實的排序演算法- Timsort](https://jason18153.medium.com/%E6%9C%80%E8%B2%BC%E8%BF%91%E7%8F%BE%E5%AF%A6%E7%9A%84%E6%8E%92%E5%BA%8F%E6%BC%94%E7%AE%97%E6%B3%95-timsort-a75da75b65a2)
> 接下來我們來聊兩個 run 之間的合併，為了解決 Merge sort 在處理空間上的不足(可以往上回去看第一張圖)，Tim 想出了底下的合併方法：
> 
> 1. 將比較小的 run 當成圖中的 X
> 2. 把 runX 複製到一個新的空間 temporary
> 3. 接下來用 Merge sort 合併
>
> 上面這個合併的方法可以確保在最壞的情況下，Timsort 使用的空間是 n/2 (Tim真的是個很務實的人)，到這邊其實已經可以算是很圓滿的結束了，**但是 Tim 覺得這樣不行，還必須對 Merge sort 做出優化，所以 Tim 提出了 Galloping mode**。（本次作業我最想釐清的點）
> Galloping
> =========
>
> 再強調一次!
>
> > Tim 認為在現實世界中的序列大多都是已經部分排序的(partial sorted)
>
> 所以**假設有兩個序列 {1, 2, 3, 4, 5, …,1000} {2001, 2002, 2003, …,3000}做 Merge sort，總共需要比對一千次，這實在是太耗資源了，所以 Tim 想了一個新的做法，就是只比二的次方的數，比完之後再用 binary search(前面已經排序好了) 找到那個對的位子，這樣總共比較的次數可以壓低到 O(logn)，** 但是Tim又發現了一個問題：
> 
> 從上面那張圖可以發現在比較 2, 4 的時候 linear search 的效果是比 galloping 的效果來的好的(分別是左二欄和右一欄)，**所以 Tim 決定當兩個序列比較到第七次都是由同一個序列取值時，才啟動 Galloping mode。** 以上就是 Timsort 所有合併的細節了。
---
### 1.3 對應到程式碼介紹原理
介紹篇幅太長，另開共筆頁面
[Tim sort 程式步驟詳解](https://hackmd.io/@blue76815/timsort)
:::info
參考資料：
* [Timsort wiki](https://en.wikipedia.org/wiki/Timsort#Galloping_mode_during_merge)
* [Timsort 研究與對 Linux 核心貢獻嘗試](https://hackmd.io/@yanjiew/linux2023q1-timsort#%E5%90%88%E4%BD%B5%E6%BC%94%E7%AE%97%E6%B3%95)
* [(台大計組中心) Python小技巧：Python 中的 list 排序演算法](https://www.cc.ntu.edu.tw/chinese/epaper/home/News_Content_n_103858_s_232975.html)
* [最貼近現實的排序演算法- Timsort](https://jason18153.medium.com/%E6%9C%80%E8%B2%BC%E8%BF%91%E7%8F%BE%E5%AF%A6%E7%9A%84%E6%8E%92%E5%BA%8F%E6%BC%94%E7%AE%97%E6%B3%95-timsort-a75da75b65a2)
* [TimSort - Python 內建排序法](https://codingman.cc/timsort-python-built-in-sorting-algorithm/)
* [[演算法] TimSort — 以人命名的排序法](https://mailtojacklai.medium.com/%E6%BC%94%E7%AE%97%E6%B3%95-timsort-%E4%BB%A5%E4%BA%BA%E5%91%BD%E5%90%8D%E7%9A%84%E6%8E%92%E5%BA%8F%E6%B3%95-5d5e6ed7872c)
:::
### 1.4 提出改進方案並予以實作。
#### 1.4.1 改善記憶體洩漏
用 valgrind 檢查
:::info
```
$ valgrind --leak-check=full --show-leak-kinds=all --track-origins=yes --verbose --log-file=filename ./timtest
```
這裡的指令選項解釋如下：
- `--leak-check=full`：告訴 Valgrind 執行完整的記憶體泄漏檢查。
- `--show-leak-kinds=all`：顯示所有類型的記憶體泄漏。
### 其他常用選項
- `--track-origins=yes`：這個選項可以幫助追蹤未初始化的記憶體讀取的來源，這對於確定未初始化記憶體使用的位置非常有用。
- `--verbose`：提供更多的調試信息。
- `--log-file=filename`：將 Valgrind 的輸出導向到一個文件。
### 範例
假設你的程序叫做 `my_program`，並且已經編譯成執行檔 `my_program`，並產生`valg_log`將 Valgrind 的輸出導向到一個文件，你可以這樣使用 Valgrind：
```
valgrind --leak-check=full --show-leak-kinds=all --track-origins=yes --verbose --verbose --log-file=valg_log ./my_program
```
:::
---
```
$ valgrind --leak-check=full --show-leak-kinds=all --track-origins=yes --verbose --log-file=valg_log ./timtest
```
其中顯示出
```
==127653== Searching for pointers to 3 not-freed blocks
==127653== Checked 109,392 bytes
==127653==
==127653== 24,000 bytes in 1 blocks are definitely lost in loss record 1 of 3
==127653== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==127653== by 0x109673: main (main.c:116)
==127653==
==127653== 24,000 bytes in 1 blocks are definitely lost in loss record 2 of 3
==127653== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==127653== by 0x109681: main (main.c:117)
==127653==
==127653== 24,000 bytes in 1 blocks are definitely lost in loss record 3 of 3
==127653== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==127653== by 0x10968F: main (main.c:118)
==127653==
==127653== LEAK SUMMARY:
==127653== definitely lost: 72,000 bytes in 3 blocks
==127653== indirectly lost: 0 bytes in 0 blocks
==127653== possibly lost: 0 bytes in 0 blocks
==127653== still reachable: 0 bytes in 0 blocks
==127653== suppressed: 0 bytes in 0 blocks
==127653==
==127653== ERROR SUMMARY: 3 errors from 3 contexts (suppressed: 0 from 0)
```
valgrind 指出，我的 main.c
main (main.c:116)
main (main.c:117)
main (main.c:118)
第 116-118 行顯示錯誤
發現
```c=116
element_t *samples = malloc(sizeof(*samples) * SAMPLES);
element_t *warmdata = malloc(sizeof(*warmdata) * SAMPLES);
element_t *testdata = malloc(sizeof(*testdata) * SAMPLES);
```
在Tim sort後沒有釋放動態記憶體
加入
```c=139
free(samples);
free(warmdata);
free(testdata);
```
再用 valgrind 檢查，顯示
```
All heap blocks were freed -- no leaks are possible
ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
```
```
==128843== HEAP SUMMARY:
==128843== in use at exit: 0 bytes in 0 blocks
==128843== total heap usage: 4 allocs, 4 frees, 73,024 bytes allocated
==128843==
==128843== All heap blocks were freed -- no leaks are possible
==128843==
==128843== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
```
Sign in with Wallet
Connect another wallet