contributed by <raygoah
>
afcidk
findName()
看不太出來效能的差別,是否有嘗試過查詢不同名字或是多次查詢來進行比較?LinYunWen
HASH_TABLE_LENGTH = 1024
rwe0214
O(n)
,而不是 O(nlogn)
,如果是 O(nlogn)
時間應該不只這樣><這裡對應的程式碼修改應一併傳到 GitHub 上
commit message 的撰寫請參閱【譯】如何撰寫Git提交訊息
vvn好的,謝謝提醒 raygoah
中英文字間記得空白喔!vvn
感謝提醒raygoah
不需要使用 sudo XD vvn
之前沒有切換到 root ,現在學會了,已補上raygoah
想法:
main.c
後可以發現到,在 struct 中,實際會被使用到的其實只有 lastName
,推測將 struct 縮小,會降低 cache miss 的發生測試減少 entry size 是否有用:
lastName
以外的所有程式碼註解觀察縮小 struct 後,entry size 為 24 bytes 的情況下, cache miss 的情形:
可以發現到,縮小 struct 後, cache miss 發生的情形確實有改善。但因為前面使用的方法是將程式碼註解,此方法可能會影響到程式的功能,因此接著嘗試在不影響程式功能的前提下,減少 entry size
減少 entry size:
__PHONE_BOOK_ENTRY
的大小,entry size 從原本的 136 bytes 減少為 32 bytes。
閱讀
在實做前遇到的插曲:
可能要先 $ make clean
再 $ make
之後每次先 $ make clean
再 $ make
後,就沒再發生過了
先把這個情況紀錄下來,要是還有出現,再來看看是哪邊出問題 raygoah
實作 hash function
依照 hash 函數比較 中介紹的各種不同的 hash function ,使用在此次作業中,並比較不同的 hash function 所得到的結果差異
在這裡 seed 的值取 131,參考此篇,而實際將 seed 改成 13 或 267 跑跑看,結果幾乎沒差,於是選擇 131 作為 seed 值
接著觀察使用了 BKDR hash 後,cache miss 的情形
由上圖可以看到,cache miss 發生的比率,從之前的 47.791% 下降到 38.554%, 因此實作 BKDR hash 是有助於減少 cache miss 的發生
利用 gnuplot 繪製出圖形,觀察使用 hash 後,findName()
和 append()
所需時間有無改變,可以看到在建立了 hash table 的版本中,append()
所花的時間是有些微增加的,但在 findName()
中所花費的時間,卻是大幅的減少,在圖中甚至已經看不太到了
append()
所花的時間也是些微增加,在 findName()
中所花費的時間,也是大幅的減少
4. 實作 SDBMHash
5. 實作 ELFHash
findName()
和 append()
所需時間方面,和之前幾種 hash 相比沒什麼顯著的差異在以上幾種不同的 hash function 中,可以看到在 append()
的部份,所需花費的時間比起沒有使用 hash 的版本都有些許的增加,但在 findName()
的部份,可以很明顯的看到花費的時間大幅的減少
使用不同的 hash function,對於 cache-miss 的發生會有一點影響,在hash 函數比較 中排名較高的 hash,發生 cache-miss 的次數也有比較少的現象,但整體而言有使用 hash 比起沒有使用的版本,cache-miss rate 都是比較低的
閱讀
實作
ryanwang522
的紀錄,以及 Sorted Linked List to Balanced BST,閱讀後實作 BST雖說整體運行時間是增加的,但從繪製的比較圖中可以看到,BST 版本中 findName()
和 append()
所需時間比起使用 hash 的版本是比較低的,如下圖所示
由於 append()
的部份是直接將 dataset 中的名字串接成 link list,所以花費的時間和縮小 struct 的 optimized
版本會是相同的,但若是把建立 BST 所需的時間加入的話,所需時間應該是會上升的,如下圖所示
而重點是在於 findName()
的部份,證實了利用 BST 在搜尋方面,時間複雜度最佳為 O(logn)
最差為 O(n)
的特性,是可以有效降低 findName()
的所需時間,但因為建立 BST 為 O(nlogn)
,所以在整體運行上所需要的時間會是變多的
從 dictionary/words.txt
中可以看到有人的姓名入下所示:
很明顯的,正常來說,不會有這種由一個字母重複出現的取名方式,就算他父母很想讓他在學校永遠都當一號,而取了 aaaa
這樣的名字,但我想這也是不太可能的事情,因此我認為 dataset 中許多筆資料的和真實狀況是相差許多的,但如果這些資料是取自於網路上的 id 或是帳號暱稱,那麼就相對的就比較合理
再來是關於每筆資料都不同這點,光是一個 50 人的班級中,都很有可能出現兩個或以上名字一樣的人了,在這麼多筆資料中,每筆資料卻是不重複的,這種情況應該不太可能,當然因為 phonebook 的作業是老師經過簡化過後的情況,所以才會如此,不然一般來說必定會有重複的姓名出現,而且重複的情況應該會不少