Try   HackMD

2017q1 Homework1 回顧

phonebook

  • 英文字母出現頻率
  • 原本 Linked list 的查找時間複雜度為 O(n) ，他將資料結構調整成 BST 後，時間複雜度為 O(logn)，由圖表也可得知查找效率也大幅改善。
  • BST 應針對 cache line 的特性去調整
  • 嘗試引入 Soundex 演算法來提高可用性，允許相似音的查詢。
  • Soundex 演算法利用英文字的讀音計算近似值，值由 4 個字元構成，第 1 個字元為英文字母，後 3 個為數字。在拼音文字中有時會有會念但不能拼出正確字的情形，可透過 Soundex 達成類似模糊匹配的效果。
    • 例如 Knuth 和 Kant 二個字串的 Soundex值都是 "K530"。不過要注意的是，因為給定的 data set 非常不理想 (不是真的英文姓名)，透過 Soundex 的效果很有限，應該著手改進輸入資料。

raytracing

  • 做了 loop unrolling 後，分析組合語言輸出，對比調整前後，x86_64 的 jmp, jg, pxor 等指令減少

compute-pi

  • 數學, Concurrent vs. Parallel

clz

Last changed by 
 
Jim Huang
0
1190
Published on HackMD