contributed by < marsh-fish
>
marvin0102
q_ascend 和 q_descend 的實作中,我原本的作法是透過 list_for_each_entry_safe
逐一排查,當檢查到不符合 ascned 或 descend 的節點時,將期刪除後還須回過頭檢查之前的佇列,review 時,發現 marsh-fish 同學的作法更有效率。
需要解釋 marsh-fish 的方案為何更有效率,這樣才有同儕程式碼審查的效果。
jservImage Not Showing Possible ReasonsLearn More →
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
mesohandsome
可以貼出修改或新增的程式碼,或是貼出 commit 紀錄,以便日後修改或參考時較為便利。
q_ascend
和 q_descend
中,重複了很多一樣的程式碼,能提高程式碼的可重用程度。
我讓兩個函式同樣都是從尾端往前端走訪,以類似 q_sort
用一個 boolean 變數讓比較時可以更改方式,從而讓他們呼叫同一個函式,透過變數去控制行為。
說好的進度呢?
使用在 list.h 定義的 INIT_LIST_HEAD
來實作
由於需要釋放所有的節點,所以用 list_for_each_entry_safe
以便能更刪除節點,最後也別忘記將空的串列空間釋放出來。
與 Ackerman666 及 dockyu 討論的結果,使用 strdup
便會自動複製字串並配置記憶體空間,另可參照 strcpy vs strdup(內也有提到 memcpy
較 strcpy
有效率,所以在 q_remove_head
和 q_remove_tail
的實作有使用到)。
注意超連結的標示方式,該提及摘要標題。
用快慢指標(Fast & Slow pointers)找到中間節點,這邊選擇讓兩個指標(烏龜和兔子)在初始就移動到第一個節點,這樣的好處是當迴圈結束時慢指標所指向的節點剛好會是中間節點。
這裡的概念和快慢指標類似,但與 q_delete_mid
不同的是初始並未移動到第一個節點,因為這裡先移動不會有額外的好處,所以我選擇先不移動。
這個函式我認為還有很大的改進空間,我使用 list_for_each_entry_safe
來作為方便刪除節點的迴圈,但我是選擇判斷當前節點與下一個節點,所以當到達最後一個節點時便會出錯,此時我的想法有兩個,一個是我從第二個節點開始搜尋,但我想保留 list_for_each_entry_safe
的使用,我不知道要如何在使用 list_for_each_entry_safe
的前提下從第二個節點開始搜尋,所以我選擇在最後節點時便跳出迴圈。
嘗試使用指標的指標來實作,每次將倒數第二個節點移動到最後一個
用分治法(Divide-and-conquer algorithm)來實作,以遞迴來實作較為容易,再次使用快慢指標將前半串列和後半串列分別遞迴,多建立一個 merge_two_sorted
函式以利於再次利用,由於 strcmp
會回傳正數或複數,便可以用以下的方式直接判斷要做遞增排序或遞減排序。
如果不採取遞迴,你要怎麼開發排序程式?
若不採取遞迴,可以先將原始串列分群(每個群將會是排列好的串列),較簡單的分群方式即相鄰的節點分成一群,如果串列個數是奇數,最後一個節點自己一群即可,接著將相鄰的群依序合併,重複此流程便可得到排列好的串列,由與每次合併群的節點數目會是 2 的冪,所以不需要遞迴,用一個變數紀錄每次欲合併的群之大小就能知道每次迭代要合併的範圍,如此分析,可用兩個迴圈來實現。
q_descend
每當下一個節點比當前節點小就將其刪除便會是答案移除所有右側比自身小的節點之串列了,q_ascend
反過來搜尋即是答案移除所有左側比自身小的節點之串列。
答案?使用明確的詞彙。
已修正
使用在 queue.h 定義的 queue_contex_t
來實作,並再次利用前面定義的 merge_two_sorted
函式,由於我是將後面的串列(第二個之後)合併進第一個串列,所以在 list_for_each_entry_safe
迴圈的第一步跳過。
新增 do_shuffle
至 qtest.c
,別忘了加入對應的 ADD_COMMAND
。
實作演算法為 Fisher–Yates shuffle ,從最後一個節點開始,用 rand()
隨機選擇前面的節點進行交換,新增一個 swap
函式以交換選擇到的節點, swap
的功能為交換兩個節點的 value
值實作演算法為 Fisher–Yates shuffle ,從最後一個節點開始,用 rand()
隨機選擇前面的節點進行交換,新增一個 swap
函式以交換選擇到的節點, swap
的功能為交換兩個節點的 value
值。
思考如何針對鏈結串列特性,減少記憶體存取的次數。
可以考慮刪除節點並加入插入節點的方式實作交換,例如:想要交換 a,b 兩個節點,其中 a 在 b 的前方,先將 a 移除並插入在 b 之後面,再將 b 移除並插入於 a 原先的位置,如此不會對串列存取之內容讀寫,能夠減少記憶體存取的次數。
新增腳本程式至 scripts
目錄,新增 make shuffle_test
命令到 Makefile
,由於實際上只是執行一個 python 程式,所以多加 make 命令不是必要的步驟。
以下是分析的結果
sort
list_sort from Linux
閱讀linux/list.h並將與 hlist
相關的程式碼抽出,同時閱讀jserv/ttt專案,將未使用到的函式移除,使其精簡。