Try   HackMD

2017q3 Homework1 (phonebook)

contributed by <Yuessiah>

本文件多處地方採用超連結來補完報告,建議點開來看

開發環境

                                     
         eeeeeeeeeeeeeeeee           
      eeeeeeeeeeeeeeeeeeeeeee        
    eeeee  eeeeeeeeeeee   eeeee      OS: elementary os elementary OS 0.3.2 freya
  eeee   eeeee       eee     eeee    Kernel: x86_64 Linux 4.4.0-93-generic
 eeee   eeee          eee     eeee   Shell: bash 4.3.11
eee    eee            eee       eee  Virtualization:        VT-x
eee   eee            eee        eee  CPU: Intel Core i7-7700 CPU @ 4.2GHz
ee    eee           eeee       eeee  CPU(s):                8
ee    eee         eeeee      eeeeee  
ee    eee       eeeee      eeeee ee  RAM: 1691MiB / 15934MiB
eee   eeee   eeeeee      eeeee  eee  L1d cache:             32K
eee    eeeeeeeeee     eeeeee    eee  L1i cache:             32K
 eeeeeeeeeeeeeeeeeeeeeeee    eeeee   L2 cache:              256K
  eeeeeeee eeeeeeeeeeee      eeee    L3 cache:              8192K
    eeeee                 eeeee      
      eeeeeee         eeeeeee        BogoMIPS:              7200.65
         eeeeeeeeeeeeeeeee          

優化策略

本節只會提及部份效能改進策略, 詳細直接看 github 或提供的參考資料

code 部份能用內建函式取代就用

例如:

/* before */
while (fgets(line, sizeof(line), fp)) {
    while (line[i] != '\0')
        i++;
    line[i - 1] = '\0';
    i = 0;
    e = append(line, e);
}

/* after */
while (fgets(line, sizeof(line), fp)) {
    line[strlen(line)-1] = '\0';
    e = append(line, e);
}

使用體積較小的 struct[1]

將原本詳細的資料結構改用體積較小的結構,當有需要的時候才將詳細資料引進記憶體中。
這樣能使 L1 cache 儲存更多筆資料

djb2[2]

將原本 findName() 只能用循序查詢的結構改成隨機存取的結構,能讓查詢時間降為常數時間
另外也利用 hash table[3] 節省預設空間的使用

hash table size 如何訂?
課程助教

目前是直接沿用 programming small 那份 hackmd 上的,有空會再說明多大比較適合。感謝叮嚀
Yuessiah

效能差異

本實驗使用 words.txt 字典
輸入五次,分別為 {"zyxel", "zyrian", "zymophoric", "zymophyte", "zymoplastic"}

Performance counter stats for './phonebook_orig' (100 runs):

         6,347,936      cache-misses              #   88.793 % of all cache refs      ( +-  0.27% )
         7,149,104      cache-references                                              ( +-  0.11% )
       287,173,261      instructions              #    1.38  insns per cycle          ( +-  0.03% )
       207,684,016      cycles                                                        ( +-  0.25% )

       0.051437951 seconds time elapsed                                          ( +-  0.65% )

---
Performance counter stats for './phonebook_opt' (100 runs):

         6,222,490      cache-misses              #   75.992 % of all cache refs      ( +-  0.74% )
         8,188,303      cache-references                                              ( +-  0.73% )
       430,978,995      instructions              #    1.21  insns per cycle          ( +-  0.03% )
       357,578,775      cycles                                                        ( +-  0.21% )

       0.087407767 seconds time elapsed                                          ( +-  0.23% )

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

犧牲 append() 效能增進 findName() 的效能是很經濟的改進,因為 append() 的需求一定比 findName() 還來得低。若不是 那這個人名就沒有登錄的必要了XD

實作遇到的問題

本節提及的問題都已理解並解決。

  • 原本 hash function 我是回傳 int 型態,導致一直碰上 segmentation fault
  • opt.txt 要手動清除,不然舊版本的資料會跟新版本的混在一起

議題

探討本例選用的 dataset

有代表性嗎?跟真實英文姓氏差異大嗎?

資料難道「數大就是美」嗎?

不,資料如果沒有鑑別性或是真實性的話,有礙於汲取這些資料的程式做出正確的判定或是整理出有用的"資訊"。
應該說「質大就是美」,資料的品質才是最重要的。

企業真正要尋找的是非傳統的、而且未曾被挖掘過的資料,並且從這些資料中去提煉出價值,這才是對大數據應有的正確認知,而非只是執著於資料大小,只要能從看似毫無意義的數據礦坑中挖掘出金礦,有誰會在意那座礦坑原本是大得像座山還是小得像狗屋呢?[4]

如果我們要建立符合真實電話簿情境的輸入,該怎麼作?

  • 寫一些規則使得輸入保證正確,例如 電話號碼不可能出現中文字。
  • 應用模糊理論[5]使真實情況輸入常發生的一些拼寫錯誤有個更寬鬆的判定。

  1. Hackmd/ Programming Small ↩︎

  2. cse.yorku.ca/ Hash Functions ↩︎

  3. Hackmd/ Hash Function ↩︎

  4. 數位時代/ 一次搞懂大數據 ↩︎

  5. 數學傳播/ 模糊理論簡介 ↩︎