---
tags: linux2023
---

# 2023q1 Homework1 (quiz1)
contributed by < [paintako](https://github.com/Paintako) >

> [題目](https://hackmd.io/@sysprog/linux2023-quiz1)

## 開發環境

$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         43 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  16
  On-line CPU(s) list:   0-15
Vendor ID:               AuthenticAMD
  Model name:            AMD Ryzen 7 1700 Eight-Core Processor
    CPU family:          23
    Model:               1
    Thread(s) per core:  2
    Core(s) per socket:  8
    Socket(s):           1
    Stepping:            1
    Frequency boost:     enabled
    CPU max MHz:         3000.0000
    CPU min MHz:         1550.0000
    BogoMIPS:            5987.96

## 測驗一

:::warning
不用列出上述答案項目，專注於程式碼和背後的原理。
:notes: jserv
>好的了解
:::

- [ ] 解釋程式碼運作原理
取 list 中第一個 entry 作為 `pivot`, 並且移除它
使用 `list_for_each_safe` 迭代, 需要注意的是, 並且用 `itm` 作為當前節點, 如果此點小於 `pivot` , 將此點移到 `list_less` 最後, 反之移到 `list_greater` 中
分成左右兩邊後 （ `list_less` 以及 `list_greater` ), 遞迴的下去呼叫 `list_sort`,
再將 pivot 加回串列中，並用 `list_splice` 將 `list_less` 加到 `head` 後， `pivot` 之前再執行 `list_splice_tail` 將 `list_greater` 加回結尾完成排序。

- [ ] 改進方案
`pivot` 挑選問題, 如果原本節點內的排列方式是由大到小, 那此方法的複雜度: $O(n^2)$
若要改善此問題, 那每次挑 `pivot` 時可隨機挑選而不是挑固定位置

**延伸問題**

- [ ] 針對 [Quick sort](https://en.wikipedia.org/wiki/Quicksort) 提出程式碼的改進方案並實作
- [ ] 引入 hybrid sort 策略並在 Linux 核心風格的 circular doubly-linked list 實作，需要量化性能表現並探討不同資料集 (data set) 的影響
- [ ] ==BONUS==: 嘗試對 Linux 核心提出排序程式碼改進的貢獻

## 測驗二
- [ ] 改進方案
與其直接宣告一個 `MAX_DEPTH 512` 大小的陣列, 不如在需要增加 `stack top` 時在 malloc 一塊新的空間給其使用 （ in heap memory) , 這樣可以避免 `stack memory` 一大塊空間被佔住, 但需要在程式結束前自己手動 `free`, 原本的作法離開 function 時系統就會自動回收掉 `list_head stack[MAX_DEPTH]` 所佔用的記憶體