2024q1 Homework5 (assessment)

contributed by < jeremy90307 >

使用指定格式書寫，注意細節！

閱讀 因為自動飲料機而延畢的那一年

留意書名號的使用。

當我看到最後時讓我非常感動，在看這之前還想說 Linux 核心跟這到底有什麼關係，原本只是為了寫心得而去看，卻越看越認真的看完了，故事內容沒有什麼華麗的詞彙或有趣的劇情，用單純認真的態度去紀錄自己的故事，到故事的結尾那段 我要選擇全世界第三杯的紅茶 ! 真的是打動到我，我的人生從未為了什麼目標放手一搏，我在想或許是我太過膽小害怕於改變。

在課程的後續我更應該要為自己負責，每個作業都很多可以學習的東西，若是中間有問題要做的不應該是拖延，而是當下解決問題，對每個實驗都應該更全面去思考問題，訓練自己對細節的重視!

檢視前六周學習狀況

作業回顧

M01: lab0

共筆

初次認識 Linux 核心 API 相關實作，當初還算認真的作完 queue 部分，後續補上 dudect 的論文研讀及實作及 list_sort 實作及 shuffle 命令等，過程中參考過很多人的共筆，當在看看自己打的程式碼時總覺得自己是一坨大便，因此在 lab0 還需待改進。

M02: quiz1+2

共筆

這份作業現在看來完整度非常差，尤其在 Timsort 部分，當初沒搞懂Timsort 卻被我的拖延症拖到現在，目前就決定先改進它。

M03: review

將 jimmy01240397 的 code review 意見加入到我的專案中。

M03: ttt

共筆

目前僅將 ttt 原封不動的加入到 lab0 中，且能順利運行井字遊戲，後續定點數相關實作待完成。

M04: quiz3+4

共筆

這份作業讓我初次真正認識到 bitwise 的有趣之處，像是僅依靠位移操作就能達到幾乎等效除十的答案，做著做著幾天就過去了，雖然延伸問題還未完全做到。
XTree 中還是有些許不懂，但卻讓我更認識 rb tree、AVL Tree、B tree 的概念，像是其中透過左旋、右旋來平衡樹的方法。

homework5 預期目標

由於對自身評估，將全部作業完整將花費到大量時間，因此先將以下兩個作業完成，後續有多餘時間在繼續精進。

1. 將 quiz1+2 中的 Timsort 部份完整
2. 完成 ttt 作業要求，至少要作到參照〈並行程式設計：排程器原理〉，引入若干 coroutine

   lab0-ttt

檢視想投入之專案

2023 年期末專題

依據你的付出，還沒辦法看出「實力」

根據我現在實力 ，我認為還沒法對專案做出什麼實質貢獻，但我希望可以從做專案的過程學習到 Linux 相關工作技能，希望以後可以進入到這個行業中，因此我希望老師能給我個方向在之後的期末專案，謝謝。

TODO: 〈並行程式設計：排程器原理〉
紀錄問題

一對一討論:

Timsort 在 Merge sort 的基礎之上，做了什麼改進？

回顧 測驗 2

Timsort 結合 Merge sort 和 Insertion Sort，改進的目的有以下:

1. 加速 merge 的過程
2. 減少合併次數
3. 在處理有部分已排序的資料下，有更好的表現

值得一提的是， Timsort 將資料由 run 所構成，這裡的 run 由部分已排列的資料所構成。
那 run 的長度該怎麼決定，定義一個 minrun (最小運行長度)，用以表示每個 run 的最小長度。有幾點需要我們考慮到:

• minrun 不宜太長，會造成花費更多時間在執行插入排序
• minrun 不宜太短，否則在進行 merge 時次數變多
• 理想情況下 run 的數量等於或者略小於 2 的冪，效率會最高

在 find_run 函式會尋找符合遞增順序的元素，並組成一個 run ，接著使用 merge_collapse 來讓 run 的數量保持平衡，且須滿足以下條件:

• 假設有三個 run 分別為 A、B、C
  • A > B + C
  • B > C

只要有一項不符合則將 B 與 A、C 中較小者進行合併。

合併分成兩種:

• 在這我們假設有 run A 及 run B

A : [3, 7, 11, 12, 13, 31, 45]
B : [21, 22, 24, 24, 29, 300, 400]

1. merge sort 從 A、 B 的開頭逐一比較來進行合併，稱為 one-pair-at-a-time
2. Timsort 的合併基於 merge sort 做出改進，首先將 A 與 B 中長度較短者放入一塊臨時記憶區 temp (這裡 A 為較短者)

A : []
B : [21, 22, 24, 24, 29, 300, 400]
temp : [3, 7, 11, 12, 13, 31, 45]

接著 B 的第一個元素

$B_0$ 會去找在 A 的何處 (

$A_4$ 與

$A_5$ 之間)，並將

$A_0$ ~

$A_4$ 放回 A 數組中

A : [3, 7, 11, 12, 13]
B : [21, 22, 24, 24, 29, 300, 400]
temp : [31, 45]

接著將 temp[0] 比對 B ，介於 B[4] 與 B[5] 之間

A : [3, 7, 11, 12, 13, 21, 22, 24, 24, 29]
B : [300, 400]
temp : [31, 45]

以此類推

A : [3, 7, 11, 12, 13, 21, 22, 24, 24, 29, 31, 45]
B : [300, 400]
temp : []

==>

A : [3, 7, 11, 12, 13, 21, 22, 24, 24, 29, 31, 45, 300, 400]
B : []
temp : []

這種合併方法被稱為 Galloping mode 。

優劣:
數組若為隨機資料序列，可能會比逐對合併來的更慢。

Timesort 基於 mergesort 做了那些改進?

• 改善比較次數
  Timsort 會將已排序的子序列組成 run 並透過一些規則使 run 的數量保持平衡，從而讓合併時使用 Galloping mode 來減少比較次數。

• 改善記憶體開銷
  相較 merge sort ，我們僅需將以排序的兩個 run 重疊部分進行合併。
  舉例 [2, 4, 6, 7, 8, 11] 與 [9, 10, 11, 15, 17]，僅須對重疊部分合併(即 [8, 11] 與 [9, 10, 11])，在配置額外空間，僅需配置合併部分及數組數量較小的那一方，因此只須配置 2 個空間即可。

這裡配置的空間為
[2, 4, 6, 7] 及 [8, 9, 10, 11, 11, 15, 17] 最後僅需將兩數組街上即可完成排序
=> [2, 4, 6, 7, 8, 9, 10, 11, 11, 15, 17]

• 降低 cache miss
  Timsort 不必走訪每個序列才進行合併，而是一邊走訪，就一邊把序列的元素加進待合併的 runs 當中，在適當時機就合併。對記憶體來說這些元素因近期存過，所以還在記憶體的上層中，能有效減少 cache miss。

看測驗 2 過程中

在連續記憶體的情境，其合併的順序相對於非遞迴版對 cache 較友善，但對鏈結串列一類非連續性記憶體而言，進行分治（divide) 的過程中，意即決定要切在哪一個點決定左右子樹，要走訪目前遞迴呼叫對應到合併樹中內部節點，所有待排序的元素，對 cache 不友善。

這段我無法理解為何是什麼原因導致的對 cache 不友善。

如何用 bitwise 運算做到 integer div/mod 10？

show me the code!

/* a / b or a % b, b = 10 */
void divmod10(int a, int *div, int *mod)
{
    int q,r;
    
    q = ((a >> 3) + (a >> 1) + a) << 3) >> 7;
    r = a - (((q << 2) + q) << 1);
    *div = q;
    *mod = r;
}

a = 23
10111

q = 2
r = 3

數學證明

(a >> 3) 等於

${\displaystyle \frac{a}{8}}$
(a >> 1) 等於

${\displaystyle \frac{a}{2}}$

最後再將結果加上 a 得到

q_approx = (a / 8) + (a / 2) + a = a * (1/8 + 1/2 + 1) = a * 1.625

然後這個值會左移 3 位（乘以 8）再右移 7 位（除以 128）：

q = ((a * 1.625) * 8) / 128 = (a * 13) / 128 = a * 0.1015625

根據餘數定理

$r=f-g\times Q$

r = a - (((q << 2) + q) << 1);

可以看作

r = a - (10 * q);

即可求出餘數 r

驗證
假設 a = 591

近似商計算

q_approx = ((591 >> 3) + (591 >> 1) + 591) = (73 + 295 + 591) = 959
q = (959 * 8) >> 7 = 59

近似餘數計算

r = 591 - (((59 << 2) + 59) << 1) = 591 - 590 = 1