sysprog2017
$ ./phonebook_orig
$ make cache-test
$ ./phonebook_orig & sudo perf top -p $!
因為在 find 的時候,只需要尋找 lastName,所以定義了一個新的結構 __LAST_NAME_ENTRY 只存 lastName,並用一個 pointer *detail 指向原本的 __PHONE_BOOK_ENTRY
這裡我選擇了 BKDR-Hash 進行優化,下面是 BKDR-Hash 的程式碼片段:
BKDR-Hash 說明
把 link list 轉換成 BST 的結構, 再利用 binary search 搜尋
pHead = pHead->pNext
)append 花費的時間比之前還長,因為還額外使用了 conver_to_bst 建樹
findName 所花的時間比之前少,且 cache miss 有些許的降低
結果:
pNext
和 pChild
建立整個 listpChild
並給它一個 array[27] 來存字母首先,觀察程式中所使用的 words.txt 可以發現,已經照字典序排序好,那如果把他打亂 (sort -R words.txt
)再測試一次的話,結果是否會有所不同?
打亂後發現,未優化前與前兩種方式所受到的影響比較小。而後面兩種有關樹的方式,均有明顯的不同。原因在於順序的不同,導致在維護樹的時候有所差異。
下一步,應該尋找一個適當的 lastname dataset 來做測試,因為 words.txt 中包含了許多沒有名字意義的單字。
老師有提到可以將 malloc 替換成 memory pool 的方式來做,先分配好一大塊記憶體,等 append 需要的時候直接取一小塊來用,這樣 append 的時間也能有所改善,畢竟頻繁的要求/釋放記憶體也會造成系統的負荷。
將 memory pool 套用至各種版本上之後可看到總時間比原本短。看來對於大量的記憶體操作時,可以優先考慮利用 memory pool 來取代傳統的 malloc,進而提升執行效率。
版本 | 套用前後時間差異 |
---|---|
優化前 | -0.01173 |
小結構 | -0.009254 |
Hash function | -0.007918 |
字典樹 | -0.063499 |
紅黑樹 | -0.014424 |
支援 fuzzy search,允許搜尋 lastName 時,不用精準打出正確的寫法
比方說電話簿有一筆資料是 McDonald,但若使用者輸入 MacDonald 或 McDonalds,也一併檢索出來。
這裏的實做方面也是利用編輯距離來進行,以編輯距離的大小來進行搜尋
將所有編輯距離小於3的資料都列出來
在這裏想說要加個記錄最小 dist 的資料,但考慮到如果在真實世界,有太多名字相同且相似的人,那樣列出來的最小 dist 的資料也會有幾十萬筆,那就有搜尋跟沒搜尋沒什麼差別。但如果再加多幾個詳細資料在 details 中,那這個 fuzzy searching 可能就有非常大的作用了。
參考資料:
Levenshtein Distance (編輯距離)