or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Do you want to remove this version name and description?
Syncing
xxxxxxxxxx
第 1, 2 週課堂問答簡記
fennecJ
我們做 quick sort 分而治之,要做 partition,第一週測驗題 partition 的策略是什麼?
一般來說 pivot 可以隨機選也可以從頭拿,本測驗提的作法為從頭拿。
挑第一個 element 作為 pivot,將剩下的 element 分為比 pivot 大和 pivot 小兩個 partition
為何在選出 pivot 後要做 list_del?
因為要把它作為斷點從 list 移出來。後面在執行 list_for_each_entry_safe 時才不會存取到 pivot 這個 element。
Quicksort 先排序小的或先排序大的會有差嗎? (考慮到 single thread 與 multiple thread)
你為什麼會覺得它會有差呢?在 single thread 的情形下 list_less 和 list_greater 都需要被排序完,無論先排序 less 還是先排序 greater 都不會影響程式結果。
list_splice
是做什麼用的?將2個 list 接在一起
splice 這個字是什麼意思,有其他同義字可以替代嗎?
意思是拼接,可以 merge 代替?
merge 是較不精確的說法
concat?
對,就是這個字,同學們要對同義字有所了解,因為有時候 API 名字會換但用途是不變的。
為何 FFF 要用 list_splice_tail ?
因為我們做的排序是由小排到大,因此 greater 必須被放在後面,所以只能用 list_splice_tail 把 greater 接在後面。
這和前面遞迴用 Quicksort 是不同的,前面是分兩堆去做,但如果是同一個人做(單執行續),執行順序不影響結果,但這裡是 less 、 greater 方向不同的問題。
那 CCC 是什麼?
list_for_each_entry_safe
這個 for_each_safe 和 for_each 有一個很大的差別在於它做了一個副本! 這個 safe 版本適用在哪裡呢? 當我從開頭走到結尾時可能會把開頭去掉,為了避免 head 被拿掉發生問題,所以它做了一個副本。
如果 partition 的時候我想在 linked list 中間對半切的話可以怎麼做?
可以用 Floyd's tortoise and hare algorithm,這個 alg 的概念是,設兩個 ptr turtle 和 hare,turtle 每走一步;hare 就走兩步,直到 hare 把整個 list 走完,因為 list 是 circular list,所以 hare 走完整個 list 後會回到 head 或是 head->next,依 list 的 node 數為奇數或偶數個而定。程式碼示意如下:
floyd's tortoise and hare algorithm 最早是用來判斷一個 linked list 中是否存在 cycle 用的。演算法的步驟以及證明可以參考 nelsonlai1 同學寫的文章
(私心推薦 JomaTech 的介紹 影片 ,從 07:10 開始有以數學證明該演算法)
如果本題是 doubly linked list 且我們知道 tail,則我們也可以一個從 head 往後走,一個從 tail 往前走,最後他們相遇的地方也會在 list 中間。
NULL 的發音為何?
怒偶?
正確發音應為 [nʌl](音近no) 請不要發「怒偶」,他沒有怒。
可以聽聽看 外國人都怎麼念NULL
不連續的記憶對對計算機架構的什麼東西不友善?
cache
所以 cache 會希望它 access 是連續的,那連續的除了空間連續外還有什麼?
時間連續,即 temporal locality
也就是一個是 temporal locality 一個是 spatial locality。
Locality of reference
你#覺得 L1 cache 和 L2 cache 速度差幾倍
實際上是約 10 倍,你剛剛說的 100 倍是用到 RAM 的時候,而 1000 倍則是網路資料傳輸等級的速度,約為 L1 cache 1000~10000
想請問若 DDD 從 list_move_tail 改為 list_move 對程式執行會有什麼影響?
題目要求的是 Stable quick sort ,可以想想一個 sort alg 什麼情況下會被稱為 stable ? 還有為什麼 quick sort 通常不 stable ?
stable sort alg 指若有多個 elements 有相同的 key value,則 sort 前後其相對關係不變。
e.g
有一 list 5, 3, 3*, 4
其中有兩個 elements 有相同的 key value 3 ,這裡用 3 以及 3* 作為區別。他們兩個的相對關係為 3 在 3* 前面
則經過穩定排序後的結果必為:
3, 3*, 4, 5
若使用不穩定的 sort alg 排序,則結果可能為:
3*, 3, 4, 5
可以看到兩個 3 的相對關係發生改變了。
由於程式是取從開頭 pivot 後往後比較,所以用 list_move_tail 可以確保後面的 ele 被放在後面。
以剛剛提到的 list 5, 3, 3*, 4 為例,則若使用 list_move 的話程式執行會變為:
可以看到 3* 和 3 的相對位置改變了。
quicksor在怎樣的狀況下效能會有很大的疑慮
quicksort在worstcase的時候為什麼是O(n^2)
quicksort的bestsort是O(nlogn),worstcase是(n^2),當quicksort遇到已經排序好的狀況,那他就會變成worstcase,如果偵測到worst的時候現在的程式就會切換成heapsort或是insertion sort,因為這兩個排序遇到快排序完的時候都不會有很差的情況,insertion sort平常看起來不實用,但在快排序好的資料裡表現還不錯,現在的排序法都會截長補短,讓程式能夠體現出比較好的效能
yeiogy123
MergeTwoLists 議題
上述是我們利用新節點來合併兩list作法,
這個程式碼中有什麼可以察覺的隱藏問題呢?
可以看到一開始使用了新的結構指標,有使用到malloc的函式,
那他會有什麼隱含的問題?
沒有使用到free()函式
對,沒有使用到free的話,會形成我們所謂的memory leak,
但這裡我們可以使用free去釋放先前指標所存的記憶體空間嗎?
如果使用free的話,那最後副函式的回傳位址可能會有錯誤。
所以在這個地方會因為程式碼順序的問題,而無法使用free去釋放已經動態規劃的記憶體空間,而有可能造成隱含的memory leak問題。
因此我們下面會介紹另外一個
這裡使用了pointer pointer指向head,可以解決無法釋放記憶體配置空間的問題,想問倒數第二行的程式碼中的"|"用途為合?
這裡的"|"為bitwise的OR,下列為輸出真值表:
那麼在這裡bitwise-or的用途為合?
先前for-loop中,會判斷分支是否跳躍直到L1&&L2為False才會跳出。
因此這裡是將剩餘的那條list後半段加入到輸出的list中。
我們可以在把if-else簡化,使用條件三目運算子,
可以簡潔化程式碼,降低cache在block swap時的負擔。
YangYeh-PD
Linux 核心的 hash table 實作
若考慮以下 doubly linked list 的宣告
並將它應用在以下刪除節點的函式
前面的
struct list_head *l
代表 list 的開頭,而struct dll_node *n
是準備要被刪除的節點。沒錯,所以我們可以看到這段函式需要兩個參數,並且需要針對刪除開頭的特殊狀況做額外處裡。
不過倘若我們改用以下的
hlist_node
的宣告並實作刪除節點的函式
若我們先不看演算法,請問此函式現在剩哪一個參數?
其中
struct hlist_node **pprev
是什麼意思?現在參數只剩下待刪除的節點,不需要再給它 list 的開頭位置。
**prev
是一個指向 n 上一個節點的next
的間接指標。我們上一週 Linux Torvalds 在 TED 訪談中,提到使用間接指標可以使例外消失。在這個例子當中,
*next
一樣是指向下一個節點的指標。但是**prev
則是使用間接指標。好…
*pprev = next
在做什麼事情?喔!把下一個節點的指標傳給
*pprev
。如果被刪除掉的節點後面還有節點的話,才會將下個節點的
prev
指回上一個節點的next
。