344 views
# 2017q1 Homework1 回顧 ## phonebook - [x] [claaaaassic](https://hackmd.io/s/BkwSjQjtg): 分佈 - [x] [0xff07](https://hackmd.io/s/SkpIRTvKe) * 英文字母出現頻率 - [ ] [ryanwang522](https://hackmd.io/s/Sk-qaWiYl) * 原本 Linked list 的查找時間複雜度為 O(n) ,他將資料結構調整成 BST 後,時間複雜度為 O(logn),由圖表也可得知查找效率也大幅改善。 * BST 應針對 cache line 的特性去調整 - [x] [ierosodin](https://hackmd.io/s/SJ4uqs9Yx): memory pool - [x] [heathcliffYang](https://hackmd.io/s/Hyr9PhFYx) * 嘗試引入 Soundex 演算法來提高可用性,允許相似音的查詢。 * Soundex 演算法利用英文字的讀音計算近似值,值由 4 個字元構成,第 1 個字元為英文字母,後 3 個為數字。在拼音文字中有時會有會念但不能拼出正確字的情形,可透過 Soundex 達成類似模糊匹配的效果。 * 例如 Knuth 和 Kant 二個字串的 Soundex值都是 "K530"。不過要注意的是,因為給定的 data set 非常不理想 (不是真的英文姓名),透過 Soundex 的效果很有限,應該著手改進輸入資料。 ## raytracing - [x] [twzjwang](https://hackmd.io/s/BJkx6f6Fe) - [x] [vtim9907](https://hackmd.io/s/Syu0ulAtl) * C11 / C++11 規格中,已經標註 "Remove Deprecated Use of the register Keyword": http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4340.html - [ ] [ChiHsiang](https://hackmd.io/s/S1Eqr2YKe) * 做了 loop unrolling 後,分析組合語言輸出,對比調整前後,x86_64 的 jmp, jg, pxor 等指令減少 ## compute-pi - [ ] [0xff07](https://hackmd.io/s/H1MV8APKg#) * 數學, Concurrent vs. Parallel ## clz - [ ] [baimao8437](https://hackmd.io/s/BkZOVSIcx) - [ ] [0xff07](https://hackmd.io/s/rkTYU0vKx#): 數學之美