2024q1 Homework1 (lab0)

contributed by < marsh-fish >

Reviewed by `marvin0102`

q_ascend 和 q_descend 的實作中，我原本的作法是透過 list_for_each_entry_safe 逐一排查，當檢查到不符合 ascned 或 descend 的節點時，將期刪除後還須回過頭檢查之前的佇列，review 時，發現 marsh-fish 同學的作法更有效率。

需要解釋 marsh-fish 的方案為何更有效率，這樣才有同儕程式碼審查的效果。 :notes: jserv

Reviewed by `mesohandsome`

可以貼出修改或新增的程式碼，或是貼出 commit 紀錄，以便日後修改或參考時較為便利。

q_ascend 和 q_descend 中，重複了很多一樣的程式碼，能提高程式碼的可重用程度。
我讓兩個函式同樣都是從尾端往前端走訪，以類似 q_sort 用一個 boolean 變數讓比較時可以更改方式，從而讓他們呼叫同一個函式，透過變數去控制行為。

if (descend ? strcmp(entry1->value, entry2->value) > 0
            : strcmp(entry1->value, entry2->value) < 0)

開發環境

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  4
  On-line CPU(s) list:   0-3
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i5-4590 CPU @ 3.30GHz
    CPU family:          6
    Model:               60
    Thread(s) per core:  1
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            3
    CPU max MHz:         3700.0000
    CPU min MHz:         800.0000
    BogoMIPS:            6584.43
Virtualization features: 
  Virtualization:        VT-x
Caches (sum of all):     
  L1d:                   128 KiB (4 instances)
  L1i:                   128 KiB (4 instances)
  L2:                    1 MiB (4 instances)
  L3:                    6 MiB (1 instance)
NUMA:                    
  NUMA node(s):          1
  NUMA node0 CPU(s):     0-3

針對佇列操作的程式碼實作

說好的進度呢？

q_new

使用在 list.h 定義的 INIT_LIST_HEAD 來實作

q_free

由於需要釋放所有的節點，所以用 list_for_each_entry_safe 以便能更刪除節點，最後也別忘記將空的串列空間釋放出來。

q_insert_head 和 q_insert_tail

與 Ackerman666 及 dockyu 討論的結果，使用 strdup 便會自動複製字串並配置記憶體空間，另可參照 strcpy vs strdup(內也有提到 memcpy 較 strcpy 有效率，所以在 q_remove_head 和 q_remove_tail 的實作有使用到)。

注意超連結的標示方式，該提及摘要標題。

q_delete_mid

用快慢指標（Fast & Slow pointers）找到中間節點，這邊選擇讓兩個指標（烏龜和兔子）在初始就移動到第一個節點，這樣的好處是當迴圈結束時慢指標所指向的節點剛好會是中間節點。

for (slow = head->next, fast = head->next;
         fast != head && fast->next != head;
         fast = fast->next->next, slow = slow->next)
        ;

q_swap

這裡的概念和快慢指標類似，但與 q_delete_mid 不同的是初始並未移動到第一個節點，因為這裡先移動不會有額外的好處，所以我選擇先不移動。

討論「先移動不會有額外的好處」，提供量化分析。
改進漢語表達。

for (this = head, temp = head;
         temp->next != head && temp->next->next != head;
         temp = temp->next->next) {
        this = temp->next;
    ...

q_delete_dup

這個函式我認為還有很大的改進空間，我使用 list_for_each_entry_safe 來作為方便刪除節點的迴圈，但我是選擇判斷當前節點與下一個節點，所以當到達最後一個節點時便會出錯，此時我的想法有兩個，一個是我從第二個節點開始搜尋，但我想保留 list_for_each_entry_safe 的使用，我不知道要如何在使用 list_for_each_entry_safe 的前提下從第二個節點開始搜尋，所以我選擇在最後節點時便跳出迴圈。

list_for_each_entry_safe (entry, safe, head, list) {
        if (&safe->list == head) {
            break;
        }
    ...

q_reverse 和 q_reverseK

嘗試使用指標的指標來實作，每次將倒數第二個節點移動到最後一個

struct list_head **sec_last = &head->prev->prev;

q_sort

用分治法（Divide-and-conquer algorithm）來實作，以遞迴來實作較為容易，再次使用快慢指標將前半串列和後半串列分別遞迴，多建立一個 merge_two_sorted 函式以利於再次利用，由於 strcmp 會回傳正數或複數，便可以用以下的方式直接判斷要做遞增排序或遞減排序。

if (strcmp(entry1->value, entry2->value) * (descend ? -1 : 1) > 0)

如果不採取遞迴，你要怎麼開發排序程式？

若不採取遞迴，可以先將原始串列分群(每個群將會是排列好的串列)，較簡單的分群方式即相鄰的節點分成一群，如果串列個數是奇數，最後一個節點自己一群即可，接著將相鄰的群依序合併，重複此流程便可得到排列好的串列，由與每次合併群的節點數目會是 2 的冪，所以不需要遞迴，用一個變數紀錄每次欲合併的群之大小就能知道每次迭代要合併的範圍，如此分析，可用兩個迴圈來實現。

q_ascend 和 q_descend

q_descend 每當下一個節點比當前節點小就將其刪除便會是答案移除所有右側比自身小的節點之串列了，q_ascend 反過來搜尋即是答案移除所有左側比自身小的節點之串列。

答案？使用明確的詞彙。

已修正

q_merge

使用在 queue.h 定義的 queue_contex_t 來實作，並再次利用前面定義的 merge_two_sorted 函式，由於我是將後面的串列(第二個之後)合併進第一個串列，所以在 list_for_each_entry_safe 迴圈的第一步跳過。

新增 q_shuffle 命令

新增 do_shuffle 至 qtest.c ，別忘了加入對應的 ADD_COMMAND 。

ADD_COMMAND(shuffle, "Shuffle the queue with Fisher–Yates shuffle algorithm", "");

實作演算法為 Fisher–Yates shuffle ，從最後一個節點開始，用 rand() 隨機選擇前面的節點進行交換，新增一個 swap 函式以交換選擇到的節點， swap 的功能為交換兩個節點的 value 值實作演算法為 Fisher–Yates shuffle ，從最後一個節點開始，用 rand() 隨機選擇前面的節點進行交換，新增一個 swap 函式以交換選擇到的節點， swap 的功能為交換兩個節點的 value 值。

思考如何針對鏈結串列特性，減少記憶體存取的次數。

可以考慮刪除節點並加入插入節點的方式實作交換，例如:想要交換 a,b 兩個節點，其中 a 在 b 的前方，先將 a 移除並插入在 b 之後面，再將 b 移除並插入於 a 原先的位置，如此不會對串列存取之內容讀寫，能夠減少記憶體存取的次數。

shuffle 分析

新增腳本程式至 scripts 目錄，新增 make shuffle_test 命令到 Makefile ，由於實際上只是執行一個 python 程式，所以多加 make 命令不是必要的步驟。

以下是分析的結果

Expectation:  41666
Observation:  {'1234': 41760, '1243': 41852, '1324': 41221, '1342': 41732, '1423': 41779, '1432': 41722, '2134': 41618, '2143': 41706, '2314': 41726, '2341': 41683, '2413': 41465, '2431': 41686, '3124': 42107, '3142': 41863, '3214': 41455, '3241': 41635, '3412': 41428, '3421': 41840, '4123': 41781, '4132': 41280, '4213': 41571, '4231': 41671, '4312': 41829, '4321': 41590}
chi square sum:  21.11121777948447

比較 list_sort

sort

 Performance counter stats for './qtest -f ./traces/trace-sort-1000000.cmd' (5 runs):

         3504,6613      cache-misses                     #   58.30% of all cache refs           ( +-  0.15% )
       7,0088,4938      branches                                                                ( +-  0.01% )
         6011,4640      cache-references                                                        ( +-  0.09% )
      48,0760,5459      instructions                     #    0.61  insn per cycle              ( +-  0.01% )
      78,4441,2454      cycles                                                                  ( +-  0.62% )
                24      context-switches                                                        ( +- 38.61% )

           2.17923 +- 0.00332 seconds time elapsed  ( +-  0.15% )

list_sort from Linux

 Performance counter stats for './qtest -f ./traces/trace-list_sort-1000000.cmd' (5 runs):

         3297,2745      cache-misses                     #   64.60% of all cache refs           ( +-  0.77% )
       6,8959,4174      branches                                                                ( +-  0.01% )
         5104,1682      cache-references                                                        ( +-  0.09% )
      47,6232,0583      instructions                     #    0.64  insn per cycle              ( +-  0.01% )
      74,7756,7293      cycles                                                                  ( +-  0.78% )
                28      context-switches                                                        ( +- 58.00% )

            2.0907 +- 0.0162 seconds time elapsed  ( +-  0.77% )

引入 ttt

hlist 相關的程式碼抽出

閱讀linux/list.h並將與 hlist 相關的程式碼抽出，同時閱讀jserv/ttt專案，將未使用到的函式移除，使其精簡。