contributed by < devarajabc >
1
參考 Optimized QuickSort — C Implementation (Non-Recursive),實作非遞迴 (non-recursive; iterative) 的快速排序法
參考 csotaku0926, chloe0919
利用指標陣列 begin
和 end
來模擬堆疊
從堆疊中取出索引值對應的指標 begin[i]
和 end[i]
並將值存在L
和 R
之中
並將 pivot
設定為 L
node_t *L = begin[i], *R = end[i];
示意圖如下
當 L
不等於 R
時,
將大於 pivot 的節點加入 right
,反之則加入 left
接著分別用指標 begin[i]
和 end[i]
來記錄 left
的開頭與結尾、begin[i+2]
和 end[i+2]
來記錄 right
的開頭與結尾,而 pivot
則同時用 begin[i+1]
和 end[i+1]
來記錄
最後將堆疊的索引 i
更新為 i+=2
(取出一層又放回三層)
是意圖如下:
改進你的漢語表達。
可以想像成這樣:
反之當 L
等於 R
時,代表走訪到 pivot ,也就是「位置正確」的節點,所以使用 list_add
來將該節點加入 result 並將 i--
。
參考 list.h
2
Timsort 的實作,刻意不額外配置記憶體空間
參考 jimmylu890303
程式執行可以分成以下幾個階段
上圖修改自 jimmylu0303
stk_size
>= 2 時,利用 merge_collapse
來保堆疊上的 run 長度保持平衡merge_force_collapse
使 stk_size
長度小於 3 stk_size
為 2 則需要利用 merge_final
合併最後兩個 run以下是對 timsort 會用到的函式進行細部的解釋
create_sample
space
是指向「一大串可用且連續的記體空間」的指標,藉由 element_t *elem = space + i
來配置一段記體空間給 element_t 並用區域變數 elem
指向它,隨後使用 rand()
來將 elem->val
設成一個隨機數,最後利用list_add_tail(&elem->list, head)
將 element_t 加入鏈接 head 。
copy_list
利用 element_t *copy = space++
來獲得「指向可使用的記憶體空間」的指標,並在隨後的 list_for_each_entry
中不斷將鏈接 from
中每個的 entry
的資訊如 val, seq 複製到該記憶體空間 , 最後再將該記憶體空間加入鏈接 to
之中。
compare
比較鏈接 a
和鏈接 b
的 val
並輸出相減的結果,跟 strcmp
很像
而 void *priv
的功能是,窩不知道
check_lis
用來檢查是否有以下三種錯誤情況
run_size
一開始看不懂為何 (size_t) (head->next->prev)
就是 runsize ?,一直到參考了 HotMercury 的解釋才知道 run 的被以指標的型態儲存在head->next->prev
之中,最後用 (size_t) 來轉換型態並輸出。
merge
使用逐對合併 (one-pair-at-a-time) 合併兩個單向的鏈接( null-terminated singly-linked list )。
tail
是「指向尾端的指標」的指標,並在 for loop 中不斷更新,最後回傳指向「合併好的鏈結串列 」的指標。
(TODO : 補圖片)
build_prev_link
將單向鏈結串列恢復成雙向鏈結串列。
但我不懂最後兩行程式碼為何可以讓其回復成雙向鏈結串列
merge_final
內容與 merge
相似
不同之處在於:
head
來當記錄「合併好的鏈結串列」build_prev_link
來將單向鏈結串列恢復成雙向鏈結串列find_run
參考 HotMercury
輸出為 pair ,裡面包含了兩個指標 next
和 head
head
為指向當前 run 的指標,而 next
為指向下一個 run 的指標。
在走訪鏈接的過程中會遇到以下兩種情況:
len
並將其反轉,直到遇到比當前節點還大的節點len
,直到遇到比當前節點小的節點-> 將最後一個節點的 next
設為 NULL 。最後透過 head->next->prev = (struct list_head *) len
巧妙地將長度 len
藏在 prev
程式碼註解以美式英語書寫,不該存在漢語。
用清晰的漢語解釋程式行為後,再搭配程式碼驗證,避免「舉燭」。
merge_at
合併 at
和 at->prev
再用指標 list
指向合併的結果且利用 list->prev = prev
來維護鏈接的順序同時減少 stk_size
的值
(推測是在處理 stack 內的合併)
並利用 list->next->prev = (struct list_head *) len
更新合併後的 run 長度,最後再回傳 合併後的 run 。
merge_collapse
參考 維基百科、 jimmylu890303
The runs are inserted in a stack. If |Z| ≤ |Y| + |X|, then X and Y are merged and replaced on the stack. In this way, merging is continued until all runs satisfy :
i. |Z| > |Y| + |X|
ii. |Y| > |X|.
在本例子中,X 是 tp , Y 是 tp->prev , Z 是 tp->prev->prev
而要合併的形況分成以下 3 種
merge_force_collapse
與 merge_collapse
不同之處在於 merge_force_collapse
會不斷進行以下兩種合併直到run_size
小於 3
而 merge_collapse
只要遇到以下兩種情況就會離開 while loop
merge
裡面重複的部分太多,且沒有使用 Galloping mode考慮到 A 和 B 都是已排序好的數列,我們可持續改進:首先尋找 B 的首個元素(即)在 A 中的排序位置,從而確定 A 中有一段是小於者,可將這部分元素放回 A。接著,尋找剩餘 A 的首個元素在 B 中的位置,如此反覆進行,直到完成排序。
參考 yanjiew
然而有關「重複部分太多」 的改進方案再參考 第一次嘗試貢獻 Linux 核心 所提供的結果後發現小丑竟是我自己。
find_run
沒有遵守 2 的冪的原則也沒有確保每個run 的長度不小於 minrun取資料長度的前 6 位,若剩餘位中任何一位被設置,則加 1。
這主要是為了在處理隨機數列時,使得能夠被 minrun 切分成 2 的冪的 run,以便在合併時達到最佳平衡。
原本看不懂敘述,直到翻閱了 Wikipedia: Timsort 中的描述才知道是取陣列長度的「二進位表示法」的前六位為 minrun ,若剩餘位中任何一位被設置(剩餘位中有任何一位是1),則 minrun 要再加 1。
minrun 具體具體流程如下:
n
除以 2 直到其值小於等於 63 (111111,六位皆為1)n & 1
來取得最後一位 (LSB) 的值 ,並用 |
來更新 r
的值考慮 compute_minrun 的實作,以 CLZ 加速與算,善用 GCC 的 __builtin_clz
了解
參考 compute_minrun
步驟如下:
top_bit
, size 轉換成二進位後的位數shift
,要向右移的大小,若 size 不足六位則為零mask
,來判斷剩餘位數是否有被設置(1
)minrun
= size 的前六位,若有被設置則再加 12.改寫 find_run
Timsort 為了使合併過程更加均衡,需要儘量控制每個 run 的長度,定義一個 minrun (最小運行長度),用以表示每個 run 的最小長度,若長度太短,就用二分插入排序,將 run 後面的元素插入到前面的 run 裡面。
若對鏈結串列使用 binary_insert
的話時間複雜度會很糟糕(TODO:原因補充)
今天一整天都卡在無法用鏈結串列實作出
binary_insert
而沒有思考為何要使用binary_insert
以及是否非使用binary_insert
不可,就埋頭亂寫一通,浪費一堆時間,下不為例。
naive:每個 run 的長度固定為 minrun
1
運用 Linux 核心的 hash table 實作 來完成 LeetCode 105 Construct Binary Tree from Preorder and Inorder Traversal
給定由二個由整數構成陣列的前序 (preorder) 和中序 (inorder) 形式,分別是對同一棵二元樹的前序及中序走訪結果,藉此重建此二元樹。
Hash table 中的元素為 hlist_head ,而 Hash table 中各個 bucket 的節點為 hlist_node
在結構 hlist_node
之中, pprev
為「指向自己的指標」的指標
程式的執行可以分成以下幾個步驟
hash = (num < 0 ? -num : num) % size
當作雜湊函數2
LeetCode 146. LRU Cache
本題新增了兩個新的結構
lRUCacheCreate
lRUCacheFree
lRUCacheGet
lRUCachePut
3
考慮 find_nth_bit
可在指定的記憶體空間找出第 N 個設定的位元 (即 1
)