在 rb.h 中
的 path array 可以儲存了原本 node 所指向的 left/ right child
回家請計算空間複雜度 : O(N)
在第四週測驗題中,考慮以下程式碼
揣摩紅黑樹 的高度計算方式。
上面的 template
在做什麼?它在創造一個 function template。在這個程式碼,getDepth
函式在 main
才會被呼叫(如下列程式碼),而當中所傳遞的參數類型則是在 main
裡才被決定的,因此我們利用 function template,就可以增加 getDepth
的使用彈性。
我們發現 getDepth
裡面又呼叫了 doGetGepth
函式,其中的實作如下:
請問這個函式在做什麼事情?找出紅黑樹的高。
但是我們可以實際執行看看,我們發現結果既然包含小數點…
補充 : 藉由這個測試,我們可以看出在 Linux OS 與 WSL 執行程式碼的效率差異。當資料量越大的時候,執行效率差越多。以下是輸入 資料點的對比結果。
On Linux
WSL
首先第一個 if
在做什麼事?
先判斷該樹是否有任何節點。如果沒有,則直接 return。
那第二個呢?從這我們可以知道它是透過遞迴關係做什麼?
它利用兩個遞迴分別走訪左子樹與右子樹的節點,並計算最深的高。
AVL Tree 的樹高屬於 。
想要證明它,我們需要先證明以下的引理 。
在高度為 的 AVL Tree 當中,最少擁有 個節點。
其中 為費波那契數列。
對照 The Fibonacci number of Fibonacci trees and a related family of polynomial recurrence systems
因此,當 AVL Tree 的樹高為 時,總節點數量根據數學歸納法,我們可以證明在高度為 的 AVL Tree 當中,最少擁有 個節點。
根據費波那契數列的數學特性,我們有以下結果
因此,樹的總節點
根據對數的換底公式
TODO :: 證明紅黑樹的高為 。
紅黑樹特性:
那紅黑樹左樹跟右樹可能不平衡嘛,可以差到多少
from AVL tree,左右樹平衡係數相差到 2 的時候,會旋轉以得到平衡
Bubble sort
Insertion sort
分配 bn 的記憶體空間之前### 預先計算儲存 所需的空間
以下節錄2023 年 Linux 核心設計/實作課程作業 —— fibdrv Linux 核心模組的解說
倘若一開始就知道該配置多少空間給 Fibonacci 運算,就能避免空間浪費,或在計算過程中重複呼叫 krealloc
。
首先,我們可用 Binet 公式計算任意 Fibonacci 數列中第 個數
上式的近似值:
知道近似值後,我們可使以 10 為底的對數計算其位數。具體如下:
當 為足夠大的正整數時,
將近似值取 2 為底的對數,可得到需要使用的位元數
再除以 32 可得到需要使用的 uint32
數量
Linux 核心無法使用 (正確說法是,不能直接使用) 浮點數運算,因此將算式乘以 ,亦即:
此算式的結果就是該事先配置的 uint32
數量。
參考的 C 程式:
觀察計算 fibonacci 的時間會發現會有震盪的奇況 每過一段時間執行時間就會往上跳一小段 是因為 cache miss,若要排除這種 cache 對執行時間所造成的影響可以藉由降低 realloc 次數,因為 realloc 可能導致需要將原本的資料搬到更大的記憶體空間而新的空間並不是在原本的附近,造成原本 cache 裡的資料需要被更新。
uint128_t
最多可以表示到第幾個 fibonacci 數?參考 yanjiew1
透過公式解可直接計算第 個費氏數:
當 n 足夠大時,可得到約略值:
取得以 2 為底的對數
這裡的 正好表示需要多少 bits 才能完全表達 。
因此會造成 overflow 。
若是代入 ,則
大概可以表示到
用迭代法實作 Mergesort:給定一個長度為 n
的陣列 A[n]
,並建立一個相同長度的陣列 temp[n]
。
mergeSort 函式利用兩層 for 迴圈實作。
bound
變數取 right (A[n] 陣列右邊界) 與本次遍歷的次陣列右邊界 (i+2m-1) 的最小值,來避免對超出陣列外的數值進行取值造成錯誤。quiz2 測驗2
最後一行如果不使用 modulus 可能造成 overflow
ans = (i | (ans << len)) % M;
要如何在不使用大數運算的情形下,支援 n 在 int (32 bits) 的範圍,同時避免 overflow ?
分析:
根據分析 2 可知道一開始要宣告多少空間儲存答案
參考資料:https://zhuanlan.zhihu.com/p/29768999
解釋如下 (假設已拿到 ans 數列):
其實就是一直 mod 10 然後除以 10 (文章裡為了手算方便才改為除以 5),計算時改為 2 進位方式即可
如此一來就不需使用大數運算了
想請教教授為何說 quiz2 測驗2 中的
其中
會造成 overflow ?
你把 代入 i 看看會發生什麼事?
代入 i,此時 len = 32,但它仍然不會發生 overflow 不是嗎?
因為 ans 在前一次的迭代中有 mod (1e9 + 7),因此 ans 的最大值只會是 (1e9 + 6) ,而 (1e9 + 6) 的二進位為
也就是說它最多只會佔用 30 個 bits,因此
在 時會變為
即 ans 佔用的位置為第 bit 32 ~ bit 61 ,而 i 佔用的位置是 bit 0 ~ bit 31 ,但 ans 本身有 64 bits 的空間,應該不會發生 overflow 才是。
沒錯,但是不會發生 overflow 的原因是因為我們把 %M 放在 for loop 中,也就是在中間就做 modulo 了,但我想問的其實是如果全部做完之後才做 modulo 的有沒有辦法避免 overflow 。
當 setjmp() 返回非 0 的時候(通常情況下為指定過的值,用以確認出錯的位置),
也就是當生異常的情況下(通常情況下利用了 longjmp() 這個函式),
可以提醒我們來進行一些額外的處理,
當 setjmp() 返回 0,則代表一切安好
依照核心提供的 "setjmp.h"
我近日會研讀這周的 quiz 來探討更深的情況,這邊我先提供一些很簡單的案例。
這個例子中,
我們使用 setjmp() 函式來設置一個跳轉點,
然後在 do_something() 函式中模擬一個錯誤情況,
如果發生了錯誤,
就使用 longjmp() 函式跳轉回 setjmp() 函式呼叫的位置。
qsort_r
而非 qsort
?因為他們共同使用到比較的函式,會有牽涉 reentrancy 的問題(不是 race condition)。
所以要透過事先宣告更多的變數,讓不同執行序可以使用不同變數。