2017q1 Homework1 (phonebook)

contributed by < leocorter >

新手上路請多多指教

Reviewed by `king1224`

我在你的 github 上沒有看到你的 BST 版本的程式碼
你在 stackoverflow 上看到的程式碼是以 double 做為鍵值來比較判斷要放左子樹 or 右子樹，本次 phonebook 是以 lastname 做為鍵值，請問你是如何判斷該往左子樹 or 右子樹走
關於 main.c 中的 append() 使用，原始版本可以傳入整串資料的任意節點，畢竟原始版本的儲存方式沒有分支，但對於 BST 結構來說，每次都需要傳入 root，因此 main.c 中的使用方式需修改

Reviewed by `tina0405`

*關於BINARYTREE我本身是嘗試用字數長短判斷左右，想了解是以和者為判斷標準。

*還有你將STRUCTURE只分為左子樹和右子樹那其他的資料要如何去呼叫，之後在使用這份電話簿時，還是會運用到其他資訊。

*其他方面也可測試不同的hashfunctin嘗試。

開發環境

Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                8
Vendor ID:             GenuineIntel
Model name:            Intel(R) Core(TM) i7-3632QM CPU @ 2.20GHz
CPU MHz:               1243.343
CPU max MHz:           3200.0000
CPU min MHz:           1200.0000
BogoMIPS:              4389.95
Virtualization:        VT-x
L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              6144K

未優化版本











/* original version */
entry *findName(char lastName[], entry *pHead)
{
    while (pHead != NULL) {
        if (strcasecmp(lastName, pHead->lastName) == 0)
            return pHead;
        pHead = pHead->pNext;
    }
    return NULL;
}

很單純的找不到就換下一個

執行: $ ./phonebook_orig
- append() 及 findName() 時間如下

size of entry : 136 bytes
execution time of append() : 0.189302 sec
execution time of findName() : 0.005467 sec

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

          212,2953      cache-misses              #   95.108 % of all cache refs      ( +-  0.12% )
          223,2152      cache-references                                              ( +-  0.14% )
       2,6081,7801      instructions              #    1.43  insns per cycle          ( +-  0.02% )
       1,8211,8763      cycles                                                        ( +-  0.49% )

       0.088154008 seconds time elapsed                                          ( +-  1.88% )

進度請加快亮谷

phonebook

改進方向

binary search tree
hashing function 加入查詢
降低資料表示的成本 S

Binary search tree

想法：

如果我們只要找 lastName 這個字串那麼 entry 裡面的其他資料就是多餘的，所以我就把其他資料刪除。
原本的資料是用 linked list 一個一個串起來，現在我想要建造一個 binary tree 所以加上了左右的連結。

typedef struct __PHONE_BOOK_ENTRY {
    char lastName[MAX_LAST_NAME_SIZE];
    struct __PHONE_BOOK_ENTRY *pNext_left;
    struct __PHONE_BOOK_ENTRY *pNext_right;
} entry;

可是再我實作的過程中遇到了 segmentation fault 後來檢查是執行到 findName() 產生錯誤，之後我上網搜尋 binary tree segmentation fault 找到了 stackoverflow 發現裏面有~~雙重指標~~指標的指標

中文的「雙」表示對等的兩者，比方說「雙人」，但 node **tree 本質上是「指標的指標」，貿然稱為「雙指標」的話，你會發現對價關係錯誤了，請務必留意。 "jserv"

void addNode(double value, node **tree)
{
    // search first
    while (*tree)
    {
        if (value < (*tree)->key) 
            tree = &(*tree)->left;
        else if((*tree)->key < value) 
            tree = &(*tree)->right;
        else return;
    }

    // no match, so add
    *tree = malloc(sizeof(**tree));
    (*tree)->key = value;
    (*tree)->left = (*tree)->right = NULL; // note: set to null
}

我想請問關於指標，網路上查詢之後還是不太懂，為何這邊要這樣用？？
感謝許友綸學長的教學已了解
不要貿然讀網路上資料，為何不回頭讀 K&R C 呢？ "jserv"
謝謝老師的建議鄭安邦

實驗結果

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

           39,2941      cache-misses              #   64.873 % of all cache refs      ( +-  0.71% )
           60,5712      cache-references                                              ( +-  1.02% )
       2,4814,4349      instructions              #    1.69  insns per cycle          ( +-  0.08% )
       1,4716,5776      cycles                                                        ( +-  0.36% )

       0.075049025 seconds time elapsed                                          ( +-  2.39% )

cache miss 下降到 64.873%

討論

append() findName() 下降
- 如果 binary tree 有實作成功 append()應該會上升，且 findName() 應該會下降更多，代表只有 struct 資料的減少影響到實驗結果

還要再努力

昨天嘗試用 binary tree 完成實驗，可是結果沒有達到所要的要求，今天發現了錯誤的地方，是因為原本的邏輯不對，造成的不是 binary tree 而是變成 pNext_left 和 pNext_right 兩個選一個串下去，想要修改缺發生了 segmentation fault

請問要從何資料或書籍了解 segmentation fault 的相關知識和解決方法，我查了維基百科了解了可能發生原因，和 The C program language 卻還是無法解決