# 2025/04/23 一對一討論問答簡記 參與者: 1. bevmmf 2. jserv ## 會議記錄 :::success [第六週測驗三](https://hackmd.io/@sysprog/linux2025-quiz6)提到的 bloom filter，其特性是沒有 false positive、抑或沒有 false negative? 為何 O(1) 的檢查很關鍵? ::: 我覺得問題是在問 一定是前人遇到什麼問題，非得要 O(1) 才能成立，所以重點是前人遇到的那個問題是甚麼。 後來發現我又搞錯了，老師說的 O(1) 是時間複雜度 (Time Complexity)，但空間複雜度也是用 big O 去表示。而我原本直覺的認為bloom filter的出現是為了因應大數據時代的檢索要求，然而事實是 `bloom filter` 早在 1970 年就被發表出來了。該paper為 : > Bloom, B. H. (1970). Space/Time Trade-offs in Hash Coding with Allowable Errors. Communications of the ACM, 13(7), 422-426. 有趣的是，該 paper 本來要解決問題的場景是在50萬字之字典的行尾斷字問題 (hyphenation)。 bloom filter 的目的是要快速區分 90% 簡單斷字規則與 10% 特殊斷字規則而被發明出來。最終目的是實作斷字演算法 (hyphenation algorithm) 。而此斷字演算法到現在仍有不少場合會使用到。舉例像是一本電子書的撰寫，斷字演算法就能讓他不會每行長度不均行成不美觀、不勻稱的問題。由論文中的例子與電子書案例，甚至是從 paper 名 "allowable errors" 能得知 bloom filter 的使用場景為 : 1. 允許錯誤，產生錯誤的cost不大 2. 需要快速檢索一筆 data 有無在一 data set 中 3. 記憶體空間有強烈限制 而討論到檢索就不免提到 hash table。以下討論兩者關係與比較 | | Bloom Filter | Hash Table | |-------------|-------------------------------|----------------------| | 功能 | 僅支持存在性查詢<br>無法存取具體資料<br>標準實作不支持刪除 | 支持鍵值對存取資料<br>支持插入、刪除、更新<br> | | 時間複雜度 | 查詢和插入：O(k)（k 為hash function 數） | 平均：O(1)<br>最壞：O(n)（大量hash collision） | | 空間複雜度 | O(m) (m 為 bit array 大小)<br>每元素約需幾<font color = "red">bit<font > | O(n)，n 為元素數量<br>每元素需數十<font color = "red"> bytes </font> 的string(key) | | 誤報與精確性 | 存在 false positive <br>(隨元素數量n增加而上升) | 查詢結果精確，無誤報 :::success 若 BF 檢測出「不存在」 => 待測資料必定「不存在」於資料集 (O) 若 BF 檢測出「存在」 => 待測資料必定「存在」於資料集 (X) ::: 以上是實作bloom filter會遇到的議題 : false positive。 首先要先釐清統計學的 false positive 與 false negative。先假設今天一個 function 輸出 high 代表輸入資料存在，而輸出low代表不存在。 false positive : 輸出 high 理論上是資料存在，但實際上不存在，也就是假陽性。 false negative : 直翻為假陰性，也就是輸出 low ，但實際上它存在，也就是存在但被誤判成不存在。 而老師上面兩個 statements 代表的是 : 1. false negative 不存在 2. false positive 不存在 而 bloom filter 的 issue 是 false positive 。理由是當足夠多的 data 存進 BF 裡時，有可能 mapping 到的多個 bit 覆蓋幾乎整個 bit array ，進而讓下次使用 BF 判定新 data 存在時，大機率因為 mapping 到的皆與先前其他 data 重疊(交集 or 碰撞)而產生 false positive (判定存在但實際不存在)。而相反來說有沒有 false negative ?答案是沒有，因為 BF 只能增加不能刪除資料，所以不會有已經被翻成 1 又被翻回 0 的狀況。 :::success TODO: 為何需要多個 hash function? ::: hash table 是利用 key(`apple`) 經過 hash function 映射到 index 而去該 hash table index 找 key-value-pair ，最後取得 value 。 一個 hash function 有什麼限制? 由以下建模結果可知當只有 1 個 hash function 時， false positive rate 是高的，只有適當提高 k(numbers of hash function) 才能降低 false positive rate :::success TODO: 說明false positive rate近似值背後的數學原理 ::: ### 建模 false positive rate model參數有 `m` : bit array的長度(即table size) `n` : 要存的元素數(幾個string) `k` : hash function數 示意圖為以下 : ```graphviz digraph BloomFilter { rankdir=LR; node [shape=box, style=filled, fillcolor=lightblue]; edge [color=navy]; // Input elements subgraph cluster_input { label="Input Elements (n)"; color=lightgrey; style=filled; element1 [label="Element 1"]; element2 [label="Element 2"]; element3 [label="Element ..."]; elementn [label="Element n"]; {rank=same;element2 -> element1 -> elementn -> element3 [style=invis, constraint=true];} } // Hash functions subgraph cluster_hash { label="Hash Functions (k)"; color=lightgrey; style=filled; hash1 [label="Hash 1", shape=oval, fillcolor=green]; hash2 [label="Hash 2", shape=oval, fillcolor=green]; hash3 [label="Hash ...", shape=oval, fillcolor=green]; hashk [label="Hash k", shape=oval, fillcolor=green]; {rank=same; hash1 -> hash2 -> hash3 -> hashk [style=invis]} } // Bit array subgraph cluster_bitarray { label="Bit Array (m bits)"; color=lightgrey; style=filled; bitarray [label="0 0 1 0 1 ... 0", shape=rectangle, width=4, fillcolor=lightyellow]; } // Edges from elements to hash functions element1 -> hash1; element1 -> hash2; element1 -> hash3; element1 -> hashk; element2 -> hash1; element2 -> hash2; element2 -> hash3; element2 -> hashk; element3 -> hash1; element3 -> hash2; element3 -> hash3; element3 -> hashk; elementn -> hash1; elementn -> hash2; elementn -> hash3; elementn -> hashk; // Edges from hash functions to bit array hash1 -> bitarray [label="Set bit"]; hash2 -> bitarray [label="Set bit"]; hash3 -> bitarray [label="Set bit"]; hashk -> bitarray [label="Set bit"]; // Parameters table with adjusted padding and width params [shape=none, label=< <table border="0" cellborder="1" cellspacing="0" cellpadding="8"> <tr><td><b>Parameters</b></td></tr> <tr><td width="200">m: Bit array length</td></tr> <tr><td width="200">n: Number of elements</td></tr> <tr><td width="200">k: Number of hash functions</td></tr> </table> >]; } ``` 先考慮 單次加入元素 : 先假設hash function設計足夠好，mapping夠平均，則每個hash function使bit array中某個bit被翻成1的機率是$\frac{1}{m}$，最後可得 - 某個bit被沒被翻的機率是$$(1-\frac{1}{m})^k$$ - 某個bit被翻成1的機率是$$1-(1-\frac{1}{m})^k$$ 再考慮 加入n個元素後 : - 某個bit沒被翻的機率是$$(1-\frac{1}{m})^{kn}$$ - 某個bit被翻成1的機率是$$1-(1-\frac{1}{m})^{kn}$$ 最後 false positive 發生的機率就是加入的一新 $y$ ，查詢 $y$ 時產生誤報， k 個 hash function 映射到 bit array 的機率。加入一假設為關於 k 個 hash function 映射後的 bit array 為獨立不重疊 ， 結果即為某 k 個 bit 已被翻成 1 的機率 : $$P_{fp} \approx [1-(1-\frac{1}{m})^{kn}]^k$$ 再來是我們嘗試做數學近似 ### 數學近似 首先我整理了一些常用數學近似內容 1. 泰勒展開（Taylor Series Expansion） - 原理：將函數表示為某點處的無窮級數，利用導數進行展開。 - 常用形式： $(1 + x)^n \approx 1 + nx$（當 ( x ) 很小時） $e^x \approx 1 + x + \frac{x^2}{2!}$（取前幾項） $\sin x \approx x - \frac{x^3}{3!}$ $\cos x \approx 1 - \frac{x^2}{2!}$ - 用途：用於近似計算函數值(三角函數、exponential)或多項式。 2. 線性近似（Linear Approximation） - 原理：在某點附近用函數的切線近似其值。 - 公式：$$ f(x) \approx f(a) + f'(a)(x - a) $$ - 例子：$$ \sqrt{1.1} \approx \sqrt{1} + \frac{1}{2\sqrt{1}}(1.1 - 1) = 1 + 0.05 = 1.05 $$ - 用途：快速估算函數值。 3. 對數近似（Logarithmic Approximation） - 原理：利用對數函數的性質進行簡化。 - 常用形式（當 ( x ) 很小時）： $$ \ln(1 + x) \approx x $$ $$ \log_b (1 + x) \approx \frac{x}{\ln b} $$ - 用途：在統計和概率論中簡化計算。 4. 指數近似（Exponential Approximation） - 原理：利用指數函數的性質進行近似。 - 常用形式（當 ( x ) 很小時）： $$ e^x \approx 1 + x $$ $$ a^x \approx 1 + x \ln a $$ - 用途：在金融或物理學中模擬增長與衰減。 5. 極限定理（Limit Theorems） - 原理：利用極限性質近似函數或數列行為。 - 常用形式： $$ \lim_{n \to \infty} \left(1 + \frac{x}{n}\right)^n = e^x $$ $$ \lim_{x \to 0} \frac{\sin x}{x} = 1 $$ - 用途：分析級數收斂性或積分行為。 6. 斯特林近似（Stirling's Approximation） - 原理：對階乘 ( n! ) 進行近似。 - 公式：$$ n! \approx \sqrt{2\pi n} \left(\frac{n}{e}\right)^n $$ - 用途：在組合數學或統計力學中計算大階乘。 7. 積分近似 - 原理：使用數值方法近似定積分。 - 方法：梯形法、辛普森法、蒙特卡羅方法等。 - 用途：計算複雜函數的積分值。 #### 泰勒展開近似 因為 $P_{fp}$ 展開為多項式，我們用多項式近似分析。由泰勒展開推導 ###### 在 \( x = 0 \) 附近展開 對 $( g(x) = (1 - x)^a )$（這裡 $( a = k \cdot n )$）做泰勒展開，展開點選 \( x = 0 \)： ###### 計算導數 - $( g(x) = (1 - x)^a )$， - $( g'(x) = -a (1 - x)^{a-1} )$， - $( g''(x) = a(a - 1) (1 - x)^{a-2} )$， - $( g'''(x) = -a(a - 1)(a - 2) (1 - x)^{a-3} )$， - ……。 ###### 在 \( x = 0 \) 代入 - $( g(0) = (1 - 0)^a = 1 )$， - $( g'(0) = -a (1 - 0)^{a-1} = -a )$， - $( g''(0) = a(a - 1) (1 - 0)^{a-2} = a(a - 1) )$， - $( g'''(0) = -a(a - 1)(a - 2) )$。 ###### 泰勒級數 $$ g(x) = 1 + (-a)x + \frac{a(a - 1)}{2!} x^2 + \frac{-a(a - 1)(a - 2)}{3!} x^3 + \cdots $$ ###### 當 \( x \) 很小時 如果只取前兩項（因為 $( x = \frac{1}{m} )$ 很小，高階項更小）： $$ (1 - x)^a \approx 1 - a x $$ 因此若 m 為極大值，則$\frac{1}{m}$為極小。我們能使用泰勒展開式將 $(1-\frac{1}{m})^{kn}$ 近似為 $$1-\frac{kn}{m}$$ 此時$P_{fp}$可寫成 $$(\frac{kn}{m})^k$$ 但由於此近似原則是 $m$ 遠大於 $kn$ 近似成兩項才會準確，因此精度不夠 #### 極限近似 此近似只跟 $m$ 有關 由 $$ \lim_{n \to \infty} \left(1 + \frac{x}{n}\right)^n = e^x $$ 可知在插入 $n$ 個鍵後，某個特定位元被設為 1 的機率是 $P_1$ = $(1-\frac{1}{m})^{kn}$ 可近似為 $$ P_1 = \lim_{m \to \infty} \left(1 - \frac{1}{m}\right)^{m(\frac{kn}{m})} \approx e^{-1(\frac{kn}{m})} $$ 最後我們做一近似假設，對所有關又因所以 $P_{fp}=[1-(1-\frac{1}{m})^{kn}]^k$ 可近似為 $$P_{fp}\approx[1-e^{-\frac{kn}{m}}]^k$$ #### 分析參數 - 調`m` ![image](https://hackmd.io/_uploads/B1PDKu2kxl.png) m增加 => $-\frac{kn}{m}$變大 => $P_{fp}$變小 因此`m` 越大越好 - 調`n` ![image](https://hackmd.io/_uploads/SJQYYOhyll.png) n增加 => $-\frac{kn}{m}$變小 => $P_{fp}$變大 因此`n` 越小越好 - 調`k` ![image](https://hackmd.io/_uploads/rJjMwt_1lg.png) `k` 增加 => $e^{-\frac{kn}{m}}$變小 => $[1-e^{-\frac{kn}{m}}]$變大，但開次方數也變大 因此 k 有一個最佳值（$P_{fp}$ 最小點），過大或過小都不好 :::success CS:APP 第二章 TODO: 給定一個 double 型態的數值 x，在不使用 FPU 指令的前提，限定用 bitwise 操作 (亦即整數運算)，使 x 倍增 (x * 2) ⇒ e.g., x = 2.0 | 4 ⇒ e.g., x = - 2.0 | -4 ⇒ e.g., x = 2.5 | 5 double x; x << 1; // 為何無法通過編譯？ (參照 C 語言規格書) 輸出 : ```shell error: invalid operands to binary << (have 'double' and 'int') 7 | printf("%f", x << 1); | ^~ ``` ::: 根據 [International Organization for Standardization. (1999). Programming languages — C (ISO/IEC 9899:1999). ISO/IEC.](https://www.dii.uchile.cl/~daespino/files/Iso_C_1999_definition.pdf) 規格書 6.5.7 Bitwise shift operators（頁面 84） > "Each of the operands shall have integer type."(International Organization for Standardization, 1999, p. 84) 且 6.5 Expressions（頁面 67）： > Some operators (the unary operator `˜`, and the binary operators `<<`, `>>`, `&`, `ˆ`, and `|`,collectively described as bitwise operators) are required to have operands that have integer type. These operators return values that depend on the internal representations of integers, and have implementation-defined and undefined aspects for signed types. 兩者皆充分展現 bit operators 之 operands 對象必須為 integer。 #### 寫程式達成double type倍增且不用 `*` 因為 data type 不為 integer 因此不能直接用 bit operation。我知道若要倍增只要在 exponential 段+1即可達成。此時若我能將 double 暫時轉為 int 即可操作達到此目的，於是我思考如何轉換。第一個直覺想到的是強制轉換(cast,explicit conversion)，但根據 `C99` 規格書 > `ISO/IEC 9899:1999` 6.3.1.4 Real floating and integer（page 43）： When a finite value of real floating type is converted to an integer type other than _Bool, the fractional part is discarded (i.e., the value is truncated toward zero). If the value of the integral part cannot be represented by the integer type, the behavior is undefined. (International Organization for Standardization, 1999, p. 43) 可知由 float 強轉成 int ， float 的 fraction(小數) 部分會被捨棄掉，因此這條路行不通。後來找到 `string.h` 庫的 `memcpy` 可以複製一 data type 的整段位元到另一 data type 上。此在`ISO/IEC 9899:1999`的 7.21 String handling <string.h>（page 324） > 7.21.2.1 The memcpy function Synopsis ```c #include <string.h> void *memcpy(void *restrict dest, const void *restrict src, size_t n); ``` > Description The memcpy function copies n characters from the object pointed to by src to the object pointed to by dest. If copying takes place between objects that overlap, the behavior is undefined. Returns The memcpy function returns the value of dest. (International Organization for Standardization, 1999, p. 324) 以下是程式碼 ```c #include <stdio.h> #include <string.h> #include <stdint.h> #define mask_exp_off (0xFFFFFFFFFFFFFFFF-0x7FF0000000000000) int main(){ double x = 6; uint64_t temp; memcpy(&temp,&x,sizeof(double)); uint64_t temp_nonf = temp >> 51; temp_nonf += 1; temp_nonf <<= 51; temp = temp_nonf | (temp & mask_exp_off); double res; memcpy(&res,&temp,sizeof(uint64_t)); printf("multiplication by 6 of x : %lf",res); return 0; } ``` 現在開始思考此程式之邊界條件。首先，指數11位若是全滿時，+1就會有問題。問題是轉換後的unsigned int變數會進位而破壞原本double的exponential內容。 - 問題 : 我使用 [double converter](https://www.binaryconvert.com/convert_double.html?hexadecimal=7FF8000000240181) 使指數11位時，不管 mantissa 是什麼輸出十進位數值都是 `Nah` 。 而產生此問題的原因是 `IEEE754` 規範 double 時將 exp 11位 全為 0 或 1 時定義為特殊情況 1. 當 exp 11位 為 `00000000000` 時為 非規範數（subnormal）或零（若尾數也為 0） 要理解非規範數，應該要同時討論正常數 - 正常數 (normal number,也稱為 normalized number) : - exponential 部分 : `儲存值`( unsigned int `E` )為 `1~2046`。實際指數值( `e` ，可為正數、0、負數) 為 `-1022~1023`。 而儲存值( `E` )與實際值( `e` )關係為 : ``` E = e + 1023 ``` - mantissa 部分 : 隱含領先整數 1 (例如， mantissa : `100...` 表示值為 `1.100...`) 最小的正常數為 `E` = 1， mantissa = 1，值為1.0 * 2^(-1022) ≈ 2.2250738585072014e-308 >`ISO/IEC 9899:1999` 5.2.4.2.2節: The values given in the following list shall be defined as constant expressions with implementation-defined values that are of the types float, double, or long double, respectively, and that are suitable for use in #if preprocessing directives: - `DBL_MIN` : the minimum normalized positive floating-point number for type double. - Implementation-defined value: For a typical IEC 60559 (IEEE 754) implementation with radix(base) 2, DBL_MIN is approximately 2.2250738585072014E-308 - 非規範數（subnormal number，也稱為 denormalized number） - exponential 部分 : `儲存值`( unsigned int `E` )為 `0`。實際指數值( `e` ) 為 `-1022`。 - mantissa 部分 : 無隱含整數1，領先整數為0 最小正非規範數（雙精度）：0.0000000000000000000000000000000000000000000000000001 * 2^(-1022) ≈ 4.9406564584124654e-324 > `ISO/IEC 9899:2011`5.2.4.2.2 : `DBL_TRUE_MIN` : the minimum positive floating-point number for type double, including subnormal numbers. `Implementation-defined value` : For a typical IEC 60559 (IEEE 754) implementation with radix 2, DBL_TRUE_MIN is approximately 4.9406564584124654E-324. 2. `11111111111` : 表示特殊值`無窮大（±Infinity）`或 `NaN` 當瞭解以上 double IEEE 規範後，就能清楚的了解總共有哪些邊界條件 : 1. 原本 double 的 exp part 就是滿的(0x7FF) 2. 原本 double 的 exp part 就是空的(0b00000000000) 3. +1 後的 exp part 會滿(0x7FF) 因此能改寫程式為 ```c #include <stdio.h> #include <string.h> #include <stdint.h> #define mask_exp_off ~0x7FF0000000000000 int main() { /* check infinity case double x; uint64_t infinity_bits = 0x7FF0000000000000ULL; memcpy(&x, &infinity_bits, sizeof(double)); */ double x = 12.0; // Input value uint64_t temp; // Convert double to bit representation memcpy(&temp, &x, sizeof(double)); printf("temp (hex): 0x%016llX\n", temp); // Extract and check exponent uint64_t temp_exp = (temp >> 52) & 0x7FF; if (temp_exp == 0x7FF) fprintf(stderr, "exponential part is full\n"); else if (temp_exp == 0) fprintf(stderr, "exponential part is empty\n"); else if (temp_exp == 0x7FE) fprintf(stderr, "exponential part is about to full\n"); else { // Increment exponent and reconstruct bits temp_exp += 1; temp = (temp_exp << 52) | (temp & MASK_EXP_OFF); } // Convert bits back to double double res; memcpy(&res, &temp, sizeof(uint64_t)); printf("x = 6 multiplied by 2 : %lf\n", res); return 0; } ``` 本來寫法只能限制 x 為正數才能運作，而更改過後，也支援負數運作。並且能夠對任何情況邊界情況進行判斷與報錯。 待辦事項 - [x] [中央極限定理（Central Limit Theorem, CLT）](https://zh.wikipedia.org/zh-tw/%E4%B8%AD%E5%BF%83%E6%9E%81%E9%99%90%E5%AE%9A%E7%90%86) 此定理為統計學與誤差分析的理論基礎。描述為當一 distribution (平均為 $\mu$ ，方差 variance 為 $\sigma^2$)，而抽取 n(足夠大，通常 > 30) 筆 identical distribution 數據時，分布最後會呈現常態分佈( normal distribution )(均值 $\mu$，標準差 $\frac{\sigma}{\sqrt{\mu}}$)。而這定理表示樣本平均數能有效代表母體均值( $\mu$ )，即使母體分佈非正態（如偏態、均勻分佈）。實際的意義即是 CLT 讓有限測量數據的平均數可靠，幫助判斷 low latency、throughput 或 determinism，使量化關鍵規格。 - [x] [泰勒展開式 ( Taylor expansion )](https://zh.wikipedia.org/zh-tw/%E6%B3%B0%E5%8B%92%E7%BA%A7%E6%95%B0) 以上。Taylor Series 的目標是找到一個多項式級數，逼近函數 $f(x)$ 在 $𝑥 = 𝑎$ 附近的值，並確保誤差最小 ### reference - [系統軟體開發思維](https://hackmd.io/@sysprog/concepts) - [2025q1 第 6 週測驗題](https://hackmd.io/@sysprog/linux2025-quiz6)