contributed by <afcidk
>
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
Thread(s) per core: 1
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 94
Model name: Intel(R) Core(TM) i5-6400 CPU @ 2.70GHz
Stepping: 3
CPU MHz: 2700.000
CPU max MHz: 3300.0000
CPU min MHz: 800.0000
BogoMIPS: 5424.00
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 6144K
NUMA node0 CPU(s): 0-3
上課時老師有提供 Ternary Search Tree 視覺化的網站,但是當時只是看動畫的運作有點不太清楚他到底根據什麼條件儲存資料的。
後來在 Wikipedia 看到下面這段話。很簡短的一句話直接讓我對 Ternary Search Tree 怎麼儲存有了一定的想法。
All strings in the middle subtree of a node start with that prefix.
搭配這張圖
c
/ | \
a u h
| | | \
t t e u
/ / | / |
s p e i s as, at, cute, cup, he, i, us
Ternary search tree 只會有三個 child,分別把他們叫做 low child, middle child, high child
他們的特性
在第一次的作業 phonebook 中,我已經有嘗試過使用 trie 來加速 findName()
的速度,但是缺點就是會很浪費空間。
Ternary search tree 利用 Binary tree 儲存連向其他資料的『邊』,和使用陣列預先配置一堆記憶體空間的方法相比,在記憶體空間上使用效率比較高。
參考資料:
%.o: %.c
@astyle --style=kr --indent=spaces=4 --indent-switches --suffix=none $*.c
$(VECHO) " CC\t$@\n"
$(Q)$(CC) -o $@ $(CFLAGS) -c -MMD -MF .$@.d $<
bench
名稱有誤,影響到搜尋結果
可以利用 fscanf 裡類似正規表達式的特殊寫法直接找出字串裡的程式名稱和國家名稱
把原本的%s
改成 %256[^,], %256[^\n]\n
其中[^\n]
代表的是不包含 \n
字元,詳細說明可以參考 fprintf 的 man page
tst.c
裡的 tst_suggest()
在搜尋 A
的時候會產生問題
紀錄 prefix search 的字元陣列大小超過限制,導致 Segmentation fault 。還沒有找到為什麼會 tst_suggest
裡的 n
會超過 1024,下面有紀錄暫時的解決方法。
test_ref.c
在 test_ref.c
檔案裡面有三處 FIXME 提醒我們要更改程式碼。一開始看那段註解還是看不太懂要做什麼。
後來看到了 raygoah
同學的共筆,才突然發現到函式 tst_ins_del()
原先裡面的參數並不是我們希望放入的參數。
查閱 tst.h
裡面對於 tst_ins_del
的註解,從第一句話
tst_ins_del() ins/del copy or reference of 's' from ternary search tree
可以知道,這個函式可以選擇要 插入/刪除 tst 裡面的 copy 或是 reference
我現在還是不太懂 copy 和 reference 在這裡到底是什麼意思
看了 tst.c
裡面的程式碼,確定 copy 指的是整個字串,reference 會是字串的參照位址(可能在某處已經配置空間過了)
看了 tst.h 裡面的註解後覺得英文好難,應該是因為每個人的表達方式都不太一樣。看到不習慣的表達方式除了不習慣還是不習慣,不過有註解總比沒註解還要好 QQ
回到 test_ref.c
,FIXME 的註解要求我們插入每個字串的參照( reference )
看似把三處的 CPY 改成 REF 就可以了,但是這樣其實是不可行的。
為什麼呢?因為在第一次的tst_ins_del()
我們並沒有字串的參照位址。
在tst.c
的實做裡面,可以發現我們使用的 reference 取自第二個參數 char *const *s
,但是第一次呼叫 tst_ins_del()
時,我們傳入的 s 是相同的位址(char word[WRDMAX]
)
要解決這個問題,我們只要手動配置空間,並把字串放進去就可以了,函式 strdup()
可以幫我們做到這件事。
(gdb) r
Starting program: /home/afcidk/prefix-search/test_ref
ternary_tree, loaded 259112 words in 0.118815 sec
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: s
find words matching prefix (at least 1 char): A
Program received signal SIGSEGV, Segmentation fault.
0x000055555555613d in tst_suggest (p=0x5555574afd70, c=65 'A', nchr=1, a=0x7fffffffbde0,
n=0x7fffffffbd94, max=1024) at tst.c:330
330 a[(*n)++] = (char *) p->eqkid;
(gdb) p (*n)
$1 = 1605
印出 n 的時候發現 n 的數字大於我們設定的上限(1024)
在 tst_suggest
裡面判斷式 *n==max
應該要改為 *n>=max
,但是我還沒找到為什麼不能只判斷等於就好了。
其實這樣改還是不符合我們預期的結果,可以發現 prefix search A 的時候建議的字串總共有 1025 個,但是預期的是只顯示 1024 個字串而已。
在載入資料後,利用 argc (argument count) 和 argv (argument vector) 來判斷是否進入效能評比的模式。
目標: 建立 tst tree 和 prefix search 所花費的時間
我留下 cities.txt
裡面的前 15000 筆資料用來測試 prefix search
看起來 ref 版本花費的時間比 cpy 版本還要多
tst_traverse_fn
函式函式裡面有一個 if/else 判斷式,判斷現在的 node 是不是空的(字串結尾的意思),又依序從 lokid, eqkid 到 hikid 各呼叫一次。因此判斷tst_traverse_fn()
應該是用來遍歷整棵 tst tree 的函式。
fn()
根據想要做的事情可以放不同的函式,類似的函式像是 qsort 也可以自行定義排序的方式。