contributed by < slipet >
:::danger
移除 </details>，開發紀錄的存在是讓他人更容易理解你所作所為，從而協同開發，但過多的 </details> 只是增加編輯的難度。
:::
開發環境
$ gcc --version
gcc (Ubuntu 12.3.0-1ubuntu1~22.04) 12.3.0
- 為了避免使用浮點運算單元 (FPU)，我們可以在 Monte-Carlo Tree Search 中以定點數來替代浮點數運算。以 32 位元的整數為例，其表示方式可以寫成: $$X = \sum_{i = 0}^{31} q_i \cdot 2^{i} , q_i \in {0, 1}$$ 其中，$q_i$ 為整數 $X$ 在第 $i$ 位的二進制位元。例如，十進制數 $9_{10}$ 的二進制表示為: $$9_{10} = 1001_{2} = 1 \cdot 2^3 + 0 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0$$ 同樣地，定點數也可以用二進制方式表示，若是我們將整數的二進制表示向右位移16位元我們可以將值域在 $[0, 2^{32} - 1]$ 的無號整數表示位移至無號定點數二進制表示 $[2^{-16}, 2^{16} - 2^{-16}]$ 的值域，整數表示裡 $i$ 的值域為 $[0,31]$ ，在定點數表示中，前面例子指數 $i$ 的範圍為 $[-16, 15]$。 這相當於我們將整數表示的每個位元都乘上一個位移量 $2^{-16}$，因此我們可以將前面的整數表式轉換成定點數表示: \begin{aligned} 2^{-16} \times X &= 2^{-16} \times \sum_{i = 0}^{31} q_i \cdot 2^{i} , q_i \in {0, 1} \ &= \sum_{i = 0}^{31} q_i \cdot 2^{i - 16} , q_i \in {0, 1} \ \
Slipet changed 4 months agoView mode
- contributed by < slipet > 開發環境 $ gcc --version gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0 $lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit
- contributed by < slipet > Qicksort 從題目實作中觀察到，變數i 表示遞迴深度，用陣列begin[i]和end[i]模擬堆疊，並分別指向鏈結串列的首尾判斷當前迭代的鏈結是否為空或只剩一個節點。 排序時，每次會選取鏈結串鏈的開頭作為pivot ，走訪剩餘的節點進行比較大小，較小的節點會被放入left陣列，其餘則分配至right 陣列。走訪結束後將left放入heads[i]，pivot放入heads[i + 1]，right放入heads[i + 2]。接著將i + 2繼續排序heads[i]。 當迴圈持續進行直至鏈結為空或僅剩一節點時，i 會開始減少，並將鏈結合併到 result 中，這過程類似於遞迴時遇到中止條件的返回。i的減少會持續，直到陣列中的鏈結節點數超過一個，隨後重複前述過程直到全部節點排序完成加入result中。 原始實作(baseline)的改善空間我認為是在迴圈中每次儲存 end[i] 時都要呼叫 list_tail 並且走訪過一次子串列這會需要 O(n) 的時間複雜度，若是引入 Linux 核心風格的 List API 改寫可以利用環狀的鏈結串列的特性在 O(1) 的時間存取鏈結的尾端。
- contributed by < slipet > 測驗 1 Details #include <stdint.h> static inline uint64_t pow2(uint8_t e) { return ((uint64_t)1) << e; } uint64_t next_pow2(uint64_t x) {
- contributed by < slipet > 開發環境 $ gcc --version gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0 $lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit
