2024q1 Homework2 (quiz1+2)

contributed by < slipet >

Qicksort

從題目實作中觀察到，變數i 表示遞迴深度，用陣列begin[i]和end[i]模擬堆疊，並分別指向鏈結串列的首尾判斷當前迭代的鏈結是否為空或只剩一個節點。

排序時，每次會選取鏈結串鏈的開頭作為pivot ，走訪剩餘的節點進行比較大小，較小的節點會被放入left陣列，其餘則分配至right 陣列。走訪結束後將left放入heads[i]，pivot放入heads[i + 1]，right放入heads[i + 2]。接著將i + 2繼續排序heads[i]。

當迴圈持續進行直至鏈結為空或僅剩一節點時，i 會開始減少，並將鏈結合併到 result 中，這過程類似於遞迴時遇到中止條件的返回。i的減少會持續，直到陣列中的鏈結節點數超過一個，隨後重複前述過程直到全部節點排序完成加入result中。

原始實作(baseline)的改善空間我認為是在迴圈中每次儲存 end[i] 時都要呼叫 list_tail 並且走訪過一次子串列這會需要 O(n) 的時間複雜度，若是引入 Linux 核心風格的 List API 改寫可以利用環狀的鏈結串列的特性在 O(1) 的時間存取鏈結的尾端。

commit: 58f1e0c

Linux style API

設計實驗觀察 quick sort 在 baseline 和 Linux style API 不同實作下的執行時間。下圖展示了在這兩種情況下，鏈節串列使用原始 quick sort 時的執行時間折線圖。圖中的 X 軸代表輸入的隨機序列大小

$N$，Y 軸則代表執行時間

$T$（以毫秒為單位）。每組資料集都進行了 100 次取樣。我參考了 "Dude, is my code constant time?" 一文中的方法，對每組收集到的樣本使用 percentiles 進行後處理，並計算平均執行時間。為了方便觀察，對 X 軸和 Y 軸分別取了

$lo{g}_2$ :

從這張圖可以看出來，兩者的平均執行時間在資料量

$N\le 2^{12}$ 時並沒有太大的差距，

$N>12$ 時可以看得出來 Baseline 的執行時間漸漸與Linux style API 拉開差距。

Worst-Case

而quick sort的最差情況為

$O(n^2)$。以題目的實作為例子，我們可以產生一個有

$n$個節點的數列

$L$，使得在

$j$ 次遞迴時

$L_j$開頭的節點皆為最大的元素，如下:

$$\begin{array}{r}L=[a_1,a_2,a_3......,a_k]\end{array}$$
假設

$L$ 中節點的大小關係如下所示:

$$\begin{array}{r}{a}_1\ge a_k\ge a_2\ge a_{k-1}\ge ....\ge a_{\lfloor \frac{k+1}{2}\rfloor }\ge a_{\lfloor \frac{k+1}{2}\rfloor +1}\end{array}$$

從題目list_add 的實作可以發現，插入節點後的鏈結串列會跟插入的順序相反(如

$L_2$,

$L_3$ 所示)，因此若是串列

$L$的大小關係為如上所示，則

$L_j$ 在遞迴時會使得每次從開頭取得的pivot都是

$L$最大的元素，left在走訪

$L_j$後會放入

$L$中除了pivot外其他節點，right則因為沒有其他比pivot大的節點因此保持為空。

$$\begin{array}{rl}Q(L_1)& =Q(L_2=[a_k,a_{k-1},...])+a_1+Q([])\\ Q(L_2)& =Q(L_3=[a_2,a_3,...])+a_k+Q([])\end{array}$$

我們可以發現

$L_j$ 每次進行排序

$Q$ 的鏈結個數都只比前一次少一個節點，因此比較次數會是從 n-1, n-2,…遞減至 n = 1，我們可以發現這會是一個等差數列，由等差數列合我們可以知道最差情況的時間複雜度會是

$\frac{((n-1)+1)\ast (n-1)}{2}=\frac{n^2-n}{2}=O(n^2)$

設計實驗觀察 quick sort 在最差情況和隨機情況下的執行時間。

從這張圖中可以觀察到，當鏈結串列的大小超過

$2^6$ 時，最差情況與隨機情況的執行時間開始出現明顯的差距。最差情況下的執行時間增長速度明顯快於隨機情況，這表示最差情況的斜率大於隨機情況的斜率。

Duplicate elements

若是

$L$ 中節點的大小關係如下所示:

$$\begin{array}{r}{a}_1=a_2=a_3=a_4=....=a_{k-1}=a_k\end{array}$$

也就是由重複的元素組成的鏈結串列

$L$ 進行快速排序

$Q$ 時，由 Baseline 的實作我們可以得知若是 pivot 和鏈結串列中的元素都是相同的情況下，走訪後會將元素都插入 left 中，此時 right 則因為沒有其他比pivot大的節點因此保持為空。

$$\begin{array}{rl}Q(L_1)& =Q(L_2=[a_k,a_{k-1},...])+a_1+Q([])\\ Q(L_2)& =Q(L_3=[a_2,a_3,...])+a_k+Q([])\end{array}$$

從上面的式子可以發現重複元素的情況會跟最差情況一樣每次走訪後

$L_j$ 排序

$Q$ 的鏈結個數都仍然只比前一次少一個節點，因此在重複元素的情況下時間複雜度會跟最差情況一樣為

$O(n^2)$。

下圖為隨機、情況、重複情況的執行時間折線圖，我們可以發現最差跟重複情況的折線幾乎重疊在一起，因此若是要改善快速排序也必須考量重複元素的影響。

在 baseline 和 Linux style API 的實作當中，每次排序時會單向的從頭到尾走訪鏈結串列，若是 pivot 與元素相同我們會將元素都放入同一個鏈結串列

$L$ 當中，這種實作方式跟 Lomuto partition scheme 的方式很相似，這也是為什麼當全部的元素都是相同時會成為最差情況的原因。

• Lomuto partition scheme:

// Divides array into two partitions
algorithm partition(A, lo, hi) is 
  pivot := A[hi] // Choose the last element as the pivot

  // Temporary pivot index
  i := lo

  for j := lo to hi - 1 do 
    // If the current element is less than or equal to the pivot
    if A[j] <= pivot then 
      // Swap the current element with the element at the temporary pivot index
      swap A[i] with A[j]
      // Move the temporary pivot index forward
      i := i + 1

  // Swap the pivot with the last element
  swap A[i] with A[hi]
  return i // the pivot index

下方 Hoare partition scheme 的實作中會從左 (i) 右 (j) 兩端相向而行的方式走訪， i 和 j 在 whil-loop 遞增/遞減時我們把元素當作加入比 pivot 小(左陣列)和大(右陣列)，而在左端點遇到比 pivot 大或是相等的元素以及右端點遇到比 pivot 小或是相等的元素時，會將兩端點的元素進行交換。

一旦兩端進行元素交換時，我們可以看作將兩個陣列內的元素平均分配，因此分配元素時可以避免過於集中某一邊的陣列。在最極端情況，陣列內皆為相同元素時，可以使兩邊陣列的元素平均分配。

• Hoare partition scheme

// Divides array into two partitions
algorithm partition(A, lo, hi) is 
  // Pivot value
  pivot := A[lo] // Choose the first element as the pivot

  // Left index
  i := lo - 1 

  // Right index
  j := hi + 1

  loop forever 
    // Move the left index to the right at least once and while the element at
    // the left index is less than the pivot
    do i := i + 1 while A[i] < pivot
    
    // Move the right index to the left at least once and while the element at
    // the right index is greater than the pivot
    do j := j - 1 while A[j] > pivot

    // If the indices crossed, return
    if i >= j then return j
    
    // Swap the elements at the left and right indices
    swap A[i] with A[j]

若是要將 Hoare's 的演算法實作在鏈結串列中，因為沒有辦法像隨機存取陣列可以利用比較索引的方式判斷何時跳脫 while-loop ，因此需要利用額外一個 if-else 判斷式在可能兩端匯合的地方判斷是否跳脫迴圈，否則會因此陷入無窮迴圈，實作的程式碼如下:

struct list_head *pivot = L->next;
uint32_t value = *list_entry(pivot, element_t, list)->value;
list_move(pivot, &heads[i + 1]);

struct list_head *forward, *backward;
forward = backward = L;

while (true) {
    do {
        forward = forward->next;
    } while (forward != backward &&
             *list_entry(forward, element_t, list)->value < value);

    if (forward == backward)
        break;

    do {
        backward = backward->prev;
    } while (forward != backward &&
             *list_entry(backward, element_t, list)->value > value);

    if (forward != backward) {
        struct list_head *forward_pre = forward->prev;
        struct list_head *backward_nxt = backward->next;
        list_move(forward, backward);
        list_move(backward, forward_pre);
        forward = forward_pre->next;
        backward = backward_nxt->prev;
    } else
        break;
}
list_cut_position(R, backward->prev, L->prev);

5~32 行是實作 Hoare's 的演算法的部份，分別使用 forward 和 backward 代表兩個不同方向走訪鏈結的端點，兩端點會不斷的前進直到相遇或是需要交換的元素的位置，22~28行使用兩次 list_move 將兩端元素進行交換。而跳脫迴圈的判斷點為22行以及14行，22行為當兩端相向走訪時若是在同一個元素停下，則跳脫迴圈，這個判斷式只能判斷是否為同一元素，當兩端停下的位置若是恰好相交，也就是兩端各走一步就會交錯時，會因為前面兩個 while-loop 在進入迴圈時沒有辦法判斷是否兩端相遇，而陷入無窮迴圈。因此為了避免陷入無窮迴圈第14行的判斷式，在進入第二個 while-loop 時會先檢查是否兩端相遇。最後使用 list_cut_position 將 backward 至 L 間的元素加入 R ，完成一次分配兩端元素。

下圖為不同實作方式的重複元素排序執行時間比較圖，雖然 Linux style API(綠) 的執行時間稍微比 baseline(紫) 低一點，但是兩個方法的執行時間的增長速度(斜率)在

$N>2^6$ 時呈現接近平行的折線。Linux style API 在使用 Hoare's 的方式實作後，執行時間的增長速度(斜率)在

$N>2^6$ 後明顯低於與其他兩種方法。

• ANOVA

從前面的說明我們可以知道 quick sort 在取 pivot 時的最差情況會是選到當前串列的最大值，因此一個好的 pivot 選擇策略會大大的影響我們後續的排序效能。一開始我想到的改善方式是使用隨機選擇 pivot 的方式，但是仍然有可能會選到最大的元素。