2018q1 Homework2 (prefix-search)

contributed by < BroLeaf >

tags BroLeaf

開發環境

Architecture:          x86_64
CPU 作業模式：           32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                8
On-line CPU(s) list:   0-7
每核心執行緒數：          2
每通訊端核心數：          4
Socket(s):             1
NUMA 節點：             1
供應商識別號：            GenuineIntel
CPU 家族：              6
型號：                  60
Model name:            Intel(R) Core(TM) i7-4720HQ CPU @ 2.60GHz
製程：                  3
CPU MHz：              2593.812
CPU max MHz:           3600.0000
CPU min MHz:           800.0000
BogoMIPS:              5187.62
虛擬：                  VT-x
L1d 快取：              32K
L1i 快取：              32K
L2 快取：               256K
L3 快取：               6144K
NUMA node0 CPU(s):     0-7
Flags:                 fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt aes xsave avx f16c rdrand lahf_lm abm cpuid_fault epb invpcid_single pti retpoline tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid xsaveopt dtherm ida arat pln pts

Ternary search tree

程式碼分析

修改 Makefile ，設定參數 –brench

修改 Makefile ，加上

bench: 
    ./test_cpy --bench 
    ./test_ref --bench

因為原本程式是要手動輸入指令才會跑，所以寫了測資 testdada.txt 讓程式可以自己跑完。

修改 test_ref.c

參考 rex662624 所使用的方法。
當我們做了下面的修改

- tst_ins_del(&root, &p, INS, CPY)
+ tst_ins_del(&root, &p, INS, REF)

問題有：

  1. 輸入 s 跑出來的結果都會是一樣的
  2. 輸入 q 會倒置 core dumped .
choice: s
find words matching prefix (at least 1 char): Tain
  Tain - searched prefix in 0.000008 sec

suggest[0] : Tain
suggest[1] : Tain
suggest[2] : Tain
suggest[3] : Tain
suggest[4] : Tain
suggest[5] : Tain
suggest[6] : Tain
suggest[7] : Tain
suggest[8] : Tain
suggest[9] : Tain
suggest[10] : Tain
suggest[11] : Tain
  1. 解法參考 rex662624 同學所用的方法，宣告一個大小 20000 的陣列去儲存所有要產生的 nodes












char word2\[20000\]\[WRDMAX\]; 
while ((rtn = fscanf(fp, "%s", word2\[cnt\])) != EOF) { 
    //char *p = word; |
    char *p = word2\[cnt++\]; 
    /* FIXME: insert reference to each string */ 
    if (!tst\_ins\_del(&root, &p, INS, REF)) { 
        fprintf(stderr, "error: memory exhausted, tst_insert.\\n"); 
        fclose(fp); 
        return 1; 
    } 
    idx++; 
}
  1. 解法參考 bauuuu1021 同學的方法，將case 'q': 中 tst_free_all(root) 改成 tst_free(root) 即解決。在 tst.c 中，兩個函式只差前者多了這兩行
choice: s
find words matching prefix (at least 1 char): Tai
  Tai - searched prefix in 0.000030 sec

suggest[0] : Tai’an,
suggest[1] : Taichung,
suggest[2] : Taiden,
suggest[3] : Tainan,
suggest[4] : Taipei,
suggest[5] : Taiwan
suggest[6] : Taiyuan,
suggest[7] : Taizhou,

Commands:
 a  add word to the tree
 f  find word in tree
 s  search words matching prefix
 d  delete word from the tree
 q  quit, freeing all data

choice: q
broleaf:prefix-search$

雖然現在出來的結果是對的，但是並不是全部的資料，只有 array size 大小的資料而已。

Select a repo