contributed by < blue76815
>
1
延伸問題:
此 Link list 節點,指向下一個節點位址時,是儲存到 *next
結構成員
問題是 *left
, *right
沒指向下一個節點位址,
請問是在程式哪個步驟中有處理下個節點位址,儲存到*left
和 *right;
結構成員的?
list_tail()
尋找鏈結串列 ( link list ) 的末端節點位址
list_length()
計次鏈結串列 ( link list ) 的節點個數
list_construct()
建立新節點,並將資料 n
,存入指定節點內的 value
成員裡
list_construct()
在測驗1中,是用在將 test_arr[count]
陣列裡的資料一個一個的存放到 list
鍊結串列的節點內
list_construct()
和
list_add()
不同
list_add()
是在鏈結串列 (link list)中,插入一個節點 ( list_add()
函式內,沒有建立一個新節點的功能)
list_add()
在鏈結串列 ( link list )中,插入一個節點
註明: list_add()
函式內,沒有建立一個新節點的功能
list_free()
鏈結串列 ( link list ),釋放節點
quick_sort()
快速演算法(Quick Sort) 又稱為分割交換排序法,
其觀念是先在資料中找到一個中間值,
把小於中間值的資料放在左邊
而大於中間值的資料放在右邊,
再以同樣的方式分別處理左右邊兩邊的資料,直到完成為止
備註:在 Introduction to Algorithms, 4/e CH7 Quicksort 介紹中,不叫中間值,而是稱為 pivot
pivot: 樞紐
詳細流程介紹參閱
quit sort 非遞迴版 程式步驟詳解
在我們的專案文件夾裡,引入 lab0 的 list.h
Linux List API 使用方法,參閱
目標把
替換成 list.h
內的 API
有參考 vax-r 同學的作法,寫成
詳細變更,請看我的 Github 3723ace 紀錄
makefile 中
sudo taskset -c 0 ./main 10000 > data.csv
其中 sudo taskset -c 0
就是要將程式綁定在1個cpu上執行
根據 man clock_gettime
使用 clock_gettime()函數,計時 nanosecond
先作到量測 1000筆 資料做 q_sort 計時為例
可看到生成
1000_data.csv 1000_qsort.png 這兩個檔案
1000_qsort.png
根據這篇 快速排序 (Quick Sort) 提到
quick_sort worst case 是發生在
Pivot 恰好是該資料陣列的最小值或最大值,使得切割無法產生一分為二的效果。
cn 為切割時間
故時間複雜度為
根據 避免 Quick Sort 的 Worst Case 發生
有鑑於時間複雜度高達 ,要怎麼樣才能避免取到最小或最大值的 Worst Case 呢?
以下提供三種可能解法:
- Middle-of-Three 方法
- Randomized Quick Sort
- 使用 Median-of-Medians 作為基準
根據 避免 Quick Sort 的 Worst Case 發生 提到的方法
之前的 find_middle()
每次要先做 list_length(head)/2;
時間複雜度太長
因次參照 Jserv 老師的
分析「快慢指標」作法
改成
step1.取出 link list 頭 (low_node) 尾(high_node) 中間(middle_node) ,這三個節點
step2.前面三筆資料,找出中間值節點(
middle_value_node
)。find_median_of_three()
step3.中間值節點 和 頭節點 交換
swap_nodes()
step4.讓新的 頭節點 作為 pivot
詳細程式實做,請看
github commit Implement median_of_three qsort.
和 q_sort
差別是,加入 median_of_three(begin[i])
預先處裡 link list
根據文章中 2. Randomized Quick Sort 提到
2. Randomized Quick Sort
用亂數選取的方式,隨機挑一個值作為 pivot。
當然,這還是可能會發生 Worst Case 高達 O(n2) 的問題,只是機率比較低。 Average Case 與 Best Case 同樣是 O(n log n)。
所以我們也可以把以上兩種改進合併──先用亂數任選三個,再用其中的中間值作為 pivot。
詳細程式實做,請看
github commit Implement random_pivot qsort.
和 q_sort
差別是加入,這三行是 做 random pivot
因為我們的 quick_sort 排序完,節點是升冪排序
例如 1–>2–>3–>4–>5–>7
所以 worst case 我們餵降冪排序的節點資料,給 quick_sort 排序
詳細程式實做,請看
github commit Implement plot_qsort.gp to measure 3 ways of qsort performance.
編譯量測效能
以量測2000筆為例
加入 median_of_three 和 random_pivot 處理,根本沒有使排序更省時,相反的
因為 quick_sort_median_of_three()
內多了 median_of_three(begin[i])
交換節點的處理步驟
quick_sort_random_pivot
內多了random_pivot(begin[i]);
交換節點的處理步驟
反而比 q_sort
更耗費處理時間
2
延伸問題:
Timsort 混和了合併排序法(Merge Sort)及插入排序法(Insertion Sort)
根據 測驗 2 描述提到
Timsort 致力於從以下三個方面,改進合併排序演算法:
- 加快合併(merge)過程
- 減少進行合併的次數。
- 在某些特定情況下,尋找比合併排序更有效的排序方法
先歸納成以下3個主要步驟
step1. 將遞增數列分割成一組一組 run
step2. 合併(用 Merge sort 做合併)
step3. Galloping mode
以下詳細介紹步驟細節
分割要領
數列中,一路遞增的數組,當成一組run數列
例如 測驗2 中
1,2,3,4,3,2,4,7,8 數列中
可以拆分成3個run
合併序列時,
每個 run 的長度,定義一個 minrun (最小運行長度)
minrun要定義多少個,參照 最貼近現實的排序演算法- Timsort
那問題來了,該如何知道這個 minrun 的值是多少呀?這個 minrun 必須滿足三個條件,
- minrun必須小於 64 ,因為大於 64 的 Insertion sort 效率會變差。
- 盡可能的平均分配,不能有全部都剛好是 minrun 而最後一個只剩下很少元素的情況發生
- 盡可能將切割完的 run 的數量控制在二的次方(前面講的 2的冪),方便待會的Merge sort
因此 Tim 想了一個非常聰明的方法,先將序列的總長度表示成二進位,取出前六個數之後如果後面還有值,就+1,舉個例子:如果總長度是197,換成二進位那就是 11000101,取出前六個數 110001 = 49,後面還有 01 所以將49+1=50,那麼在最壞的情況下,會被拆成 50 50 50 47,剛好滿足了上面的那三個條件,這個方法真的相當聰明。以上我們已經將 Timsort 的切割完全介紹完畢。
合併
為了達到高效率且省空間的合併,Tim 精心設計了合併的細節,先聊大方向的合併,我們手上現在有非常多個 run,我們從最右邊抓三個 run 出來,由左到右依次命名為 runX, runY, runZ,只要不滿足以下兩個條件的其中之一,就將 runY 與 ( runX 和 runZ 較小的 )合併:
- runX 長度 > runY + runZ 長度
- runY 長度 > runZ 長度
上面那段合併條件限制,就是對應到 成大 測驗二 描述的
Timsort 採用一組堆疊 (stack) 來暫存 run,此舉是為了避免在一開始就掃描整個資料範圍來產生 run,從而降低記憶體開銷。過程中,Timsort 運用 merge_collapse 函式來確保堆疊上的 run 長度保持平衡。該函式主要檢查堆疊頂端的 3 個 run 是否滿足以下原則:
A 的長度要大於 B 和 C 的長度總和。
B 的長度要大於 C 的長度。
接下來我們來聊兩個 run 之間的合併,為了解決 Merge sort 在處理空間上的不足(可以往上回去看第一張圖),Tim 想出了底下的合併方法:
- 將比較小的 run 當成圖中的 X
- 把 runX 複製到一個新的空間 temporary
- 接下來用 Merge sort 合併
上面這個合併的方法可以確保在最壞的情況下,Timsort 使用的空間是 n/2 (Tim真的是個很務實的人),到這邊其實已經可以算是很圓滿的結束了,但是 Tim 覺得這樣不行,還必須對 Merge sort 做出優化,所以 Tim 提出了 Galloping mode。(本次作業我最想釐清的點)
Galloping
再強調一次!
Tim 認為在現實世界中的序列大多都是已經部分排序的(partial sorted)
所以假設有兩個序列 {1, 2, 3, 4, 5, …,1000} {2001, 2002, 2003, …,3000}做 Merge sort,總共需要比對一千次,這實在是太耗資源了,所以 Tim 想了一個新的做法,就是只比二的次方的數,比完之後再用 binary search(前面已經排序好了) 找到那個對的位子,這樣總共比較的次數可以壓低到 O(logn), 但是Tim又發現了一個問題:
從上面那張圖可以發現在比較 2, 4 的時候 linear search 的效果是比 galloping 的效果來的好的(分別是左二欄和右一欄),所以 Tim 決定當兩個序列比較到第七次都是由同一個序列取值時,才啟動 Galloping mode。 以上就是 Timsort 所有合併的細節了。
介紹篇幅太長,另開共筆頁面
Tim sort 程式步驟詳解
參考資料:
用 valgrind 檢查
這裡的指令選項解釋如下:
--leak-check=full
:告訴 Valgrind 執行完整的記憶體泄漏檢查。--show-leak-kinds=all
:顯示所有類型的記憶體泄漏。--track-origins=yes
:這個選項可以幫助追蹤未初始化的記憶體讀取的來源,這對於確定未初始化記憶體使用的位置非常有用。--verbose
:提供更多的調試信息。--log-file=filename
:將 Valgrind 的輸出導向到一個文件。假設你的程序叫做 my_program
,並且已經編譯成執行檔 my_program
,並產生valg_log
將 Valgrind 的輸出導向到一個文件,你可以這樣使用 Valgrind:
其中顯示出
valgrind 指出,我的 main.c
main (main.c:116)
main (main.c:117)
main (main.c:118)
第 116-118 行顯示錯誤
發現
在Tim sort後沒有釋放動態記憶體
加入
再用 valgrind 檢查,顯示