contribured <hugikun999
>, <claaaaassic
>, <Weinux
>
GitHub: phonebook
Task: 比照 B01: phonebook,支援 fuzzy search,允許搜尋 lastName 時,不用精準打出正確的寫法。指出原有 dataset 的問題 (需要有工程分析,拿出統計學) 並改進。
Which is fastest: read, fread, ifstream or mmap?
mmap
is heavily than read
.read
,files may have been flushed out memory.mmap
can't work efficiently than other funcion.mmap
directly access memory.read
fetches the data from disk to page cache and then copy them to position you specify.Conclude: mmap 僅在 random access memory 的時候會比較有效率,如果為 sequential access 則使用 fread 會比較有效率。
這裡有提供一個可以測試 mmap
和 fread
的程式,我把 word.txt 當成輸入檔並用 $perf sate
重覆測試 100 次,可以發現 mmap
的 cache-missed 低了很大一個幅度,但是總體執行卻沒有比較快。
(1)fread
(2)mmap
mmap 版從整體的消耗時間看起來沒有減少反而增加,其原因在於先將 word.txt
做 align,比起原版額外增加了許多的 instructions,故導致最後的整體時間並沒有比較快,但是可以發現 cache-misses 已經減少了一成左右。
這裡可以利用
$perf record ./phonebook_orig
$perf annotate --no-source
查看轉成組語後每個所花費的時間。
從 gprof 可以看到時間明顯都花在 file_align()
上。
要使用
gprof
時記得要加-pg
從 append 的角度去比較就可以發現事先 mmap,可以省下四成的時間。
memory pool 的概念是透過預先 malloc 一段記憶體空間,等到需要記憶體的時候再去從剛剛已經先配置好的空間拿取。在一個大量使用 malloc 的程式中,透過 memory pool 可以省去多次呼叫 malloc 所造成的 overhead,perf 所測出來的 instructions 減少二成五了。
該圖為 mmap + memory pool 的時間
Bookkeeping algorithm keeping a list of the unused blocks.
每個 block 必須大於4 bytes,因為必須存下一個 unused 的 block number.
這個變數不會另外使用記憶體,而是將變數存在未使用的 block 內。
相比 fixed size memory pool 需要較複雜且耗時檢查的機制。
使用 create/destroy 而非 constructor/destructor,便於動態新增。
可以額外設計檢查機制是否真的需要初始化下一個尚未被使用的 block。
e.g: caching, paging, registers, memory alignment, threading
Find in the text or dictionary of size n all the words that match the given word (or start with the given word), taking into account k possible differences (errors).
其演算法可以分為
透過對一個字串(source)做刪除、替換、增加字元以形成另一個字串(target),中間所做的運算次數,即為編輯距離(distance)。比較編輯距離的大小,可以找出兩個字串之間的相似程度。
參考維基百科的演算法實作,遞迴版的運算量很大,搜尋較短的字串時可以找的出結果,但遇到比較長的字串會花費許多時間在計算編輯距離。
例如將kitten
轉成sitting
:
step 1: kitten → sitten (substitution of "s" for "k")
step 2: sitten → sittin (substitution of "i" for "e")
step 3: sittin → sitting (insertion of "g" at the end)
以英文的發音作為比較的基礎,將每個字母依照其發音的特性給予一個數字,比較字串按照 SOUNDEX 法則所得出的結果進行比較。此種方法在同一個數字會對應許多字串,造成 fuzzy search 的結果過多,需要透過其他方法使其更精準搜尋出目標字串。
由於計算編輯距離的運算量實在是太大,所以合併了上述的兩種方法,先透過運算量小的 SOUNDEX 過慮部份的字串再透過 Levenshtein Distance 計算所需的編輯距離。目前只能用在短字串的搜尋,對於長字串雖然已經大幅減少搜尋的時間,但是卻無法找出正確的字串。SOUNDEX 的限制給的太小把正確的字串給濾掉了,如果把限制放寬又會造成運算太過龐大。
還沒想到好的方法解決這個問題
為了分析 dataset 是否有代表性,拿美國人口調查局中 1990 年做的人口普查來作為對照組
合適的 dataset
下面是 words.txt 有出現在人口調查中的字
人口調查 | words.txt | |
---|---|---|
總人數 | 6290251 | 349900 |
姓氏種類 | 88799 | 27820 |
女性名字種類 | 4275 | 3083 |
男姓名字種類 | 1219 | 1071 |
有效比例 | 98.38% | 9.14% |
雖然說 words.txt 裡面涵蓋到人口調查中真實名字的比例蠻高的,但只有佔所有資料 9.14% ,有其他三十幾萬的資料都是無意義的字,在真實電話簿中不會有這樣的情形出現,整份資料當成電話簿中的姓名我想是不適合的。
然後順手用同樣的程式碼做了 ./dictionary/all-names.txt 的分析,這份資料裡面有 24% 左右是真實姓名,雖然比上一份資料的真實姓名多,而且有重複的姓氏或名字,但是數量太少,如果要當作有按照真實比例的 dataset 還是不太夠
人口調查 | all-names.txt | |
---|---|---|
總人數 | 6290251 | 16751 |
非真實姓名 | 0 | 12705 |
姓氏總數 | 6290251 | 6851 |
女性名字 | 3184399 | 5514 |
男姓名字 | 3003954 | 2048 |
女姓名字所佔總數比例 | 50.62% | 32.92% |
男姓名字所佔總數比例 | 47.76% | 12.23% |
Entropy (information theory) : entropy (more specifically, Shannon entropy) is the expected value (average) of the information contained in each message. 'Messages' can be modeled by any flow of information.
在資訊理論裡面,熵是對不確定性的測量。但是在資訊世界,熵越高,則能傳輸越多的資訊,熵越低,則意味著傳輸的資訊越少。
熵是對某個系統之不確定性或混亂程度的度量方法,也可以想成,如果 dataset 的熵值越大,資較就越混亂,不確定性越高,越無法預測
不過我沒有找到適合用在分析或改善 dataset 的應用,熵可以用來分析一個字當中有包含多少的資訊,或是分析壓縮過後的資料是否有提高壓縮率,雖然說可以知道姓氏與名字出現的次數所呈現的亂度,也可以計算出真實統計出來的亂度,若是亂度接近只能說某些字出現的頻率與真實相似,但是這並不能知道同樣頻率的字與真實是否為同一個,所以不採用此方法分析
舉個例子,假設真實世界姓名的分佈是
但是我分析的資料是
兩筆資料的 entropy 都是大約 4.94,頻率一樣的字卻不相同,我認為是不適合這個問題
改善的部份,我在美國人口調查局中拿他們 1990 的姓名資料,這次人口普查蒐集 7,200,000 人的資料,一共分成姓氏、男性名子與女性名字三份統計,並且依據出現的頻率下去做排序
首先考慮到我們的 dataset 就是電話簿本身的資料,在 349900 人中出現比例最低也有大約 4 個人,而電話簿同樣名字無法識別誰是誰,所以以下的測試資料會全都使用名字 + 姓氏來當作一筆資料
名子與姓氏的資料都有出現的比例,改善後的 dataset 依照名字比例數量配上也依照比例的姓氏,大概是像這樣子
最後是改善過的資料與人口調查的比較,改善過後的 dataset 包含真實姓氏與真實名字,男女性名字比例與真實接近
人口調查 | full-names.txt | |
---|---|---|
總人數 | 6290251 | 5567224 |
姓氏 | 6290251 | 5567224 |
女性名字 | 3184399 | 2861372 |
男姓名字 | 3003954 | 2727188 |
女姓名字所佔比例 | 50.62% | 51.40% |
男姓名字所佔比例 | 47.76% | 48.99% |
原本測量出的時間會有些誤差,在 main.c 中加入信賴區間的計算,使得 append 及 findname 量測出的時間較準確,這邊使用 95 %信賴區間表示真實資料有95%的可能性會落在這個區間。
Hash function ( 雜湊函式 )
hash table
一般而言如果兩個雜湊值是 不相同 的(根據同一函式),那麼這兩個雜湊值的原始輸入也是 不相同 的
但如果兩個雜湊值是 相同 的(根據同一函式),那麼這兩個雜湊值的原始輸入 不一定 是相同的, 而這時就發生了衝突 (collision), 遇到衝突時就資料就接在同一個索引後面即可.
一個好的雜湊函式應該具有 均勻 的真正隨機輸出。且隨機雜湊函式不太會出現非常高的衝突率。但是,少量的可以估計的衝突在實際狀況下是不可避免的.
因此以下根據常見的 hash function 做比較, 來分析它的隨機輸出與衝突率, 並且比較在 phonebook 內的 cache miss , append() findName() 時間的差異.
參考 各种字符串Hash函数比较中 8 種 hash function ( SDBM,RS,JS,PJW,ELF,BKDR,DJB2,AP ) 的實作
試著使用在 w5 作業中 matrix_oo 物件導向的做法, 把 hash function 封裝起來
phonebook_hash.h
接著只要在指向不同實作就可切換不同 hash function
如此一來在 main.c 裡就比較方便切換也不用寫太多的判斷, 不過應該還可以透過老師說過的 ELF linker set 的方法在寫得更漂亮.
main.c
word.txt
分布情形| |SDBM | RS |JS|PJW|ELF|BKDR|DJB2|AB|
|:––:|:––-:|:–––:|:––:|:––-:|:–––:|:––:|:––-:|:––-:|:––-:|
|Mean |116.63|116.63|116.63|116.63|116.6|116.63| 116.63| 116.63|
|Standard deviation|10.686|10.683|10.785|56.979|56.979|10.592|10.753|10.666|
|Variations|0.09162|0.09160|0.09247|0.4885|0.4885|0.0908|0.0921|0.0914|
word.txt
的所有資料為 349900 筆, 因此理論上平均分配到每個 hash[tag] 內的資料應該為 116.6333 筆資料, 在觀察邊準差與變異數分布 發現 BKDR 分布的情形最為平均 (邊準差 與變異數 皆為最小)
| |SDBM | RS |JS|PJW|ELF|BKDR|DJB2|AB|
|:––:|:––-:|:–––:|:––:|:––-:|:–––:|:––:|:––-:|:––-:|:––-:|
|Standard deviation|3.4135|3.3923|3.4240|10.2899|10.2899|3.4080|3.4108|3.3959|
|Variations|0.2926|0.2908|0.2935|0.8822|0.8822|0.2921|0.2924|0.2911|
PJW 與 ELF 的資料分布都完全相同 看起來要回頭看一下實作是不是有問題
| |SDBM | RS |JS|PJW|ELF|BKDR|DJB2|AB|
|:––:|:––-:|:–––:|:––:|:––-:|:–––:|:––:|:––-:|:––-:|:––-:|
|Standard deviation|1.0791|1.0802|1.0796|1.4691|1.4691|1.0788|1.0795|1.0816|
|Variations|0.9252|0.9262|0.9257|1.2596|1.2596|0.9250|0.9256|0.9274|
由於在原始版本程式中, 電話簿中的資料是被按照排序過的 ( 由 A 到 Z). 因此實作參考了 Sorted Linked List to Balanced BST ,將原本由 append() 建立已排序好的 linked list 轉成 Binary search tree 的結構, 建立 binary searh tree 需要給 head 與 list 總數為輸入,最後回傳 root 節點 (如下列表示的 4 or 3)
這邊參考 vtim9907 的實做,為了符合 cache line 的特性,決定把 node 的結構更該成 64 bytes 的大小,原來 node 的結構就只包含兩個分別指到左、右子樹的指標,和一個指到一個 phonebook entry 的指標:大小為 8 * 3 = 24 bytes
為了增加 node 的大小, 將原本的 word.txt
中的資料將它分組, 如下面的例子即是將資料 6 個一組. node 中 增加了一個陣列 裡頭包含了 6 個指向 phonebook entry 的指標 :大小為 8 * 6 + 8 * 2 = 64 bytes
heathcliffYang 共筆
hash function 觀念和實務
git branch and remote repo
Perf – Linux下的系统性能调优工具,第 1 部分
Fast Efficient Fixed-Size Memory Pool
Using Fuzzy Matching to Search by Sound with Python
NIKITA'S BLOG: Fuzzy string search
Charles 共筆
SOUNDEX
Levenshtein distance wiki
Entropy (information theory) wikipedia
vtim9907 共筆