2023q1 Homework1 (quiz1)

contributed by < paintako >

題目

開發環境

$ 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

測驗一

不用列出上述答案項目，專注於程式碼和背後的原理。

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 提出程式碼的改進方案並實作
• 引入 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] 所佔用的記憶體