# 2020q3 Homework3 (dict)
contributed by < `ZhuMon` >

###### tags: `sysprog2020`

## :fountain: 環境

$ cat /etc/lsb-release
DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=20.04
DISTRIB_CODENAME=focal
DISTRIB_DESCRIPTION="Ubuntu 20.04.1 LTS"

$ lscpu
架構：                            x86_64
CPU 作業模式：                     32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   39 bits physical, 48 bits virtual
CPU(s):                          12
On-line CPU(s) list:             0-11
每核心執行緒數：                    2
每通訊端核心數：                    6
Socket(s):                       1
NUMA 節點：                       1
供應商識別號:                      GenuineIntel
CPU 家族：                        6
型號：                            158
Model name:                      Intel(R) Core(TM) i7-8700 CPU @ 3.20GHz
製程：                            10
CPU MHz:                         3926.410
CPU max MHz:                     4600.0000
CPU min MHz:                     800.0000
BogoMIPS:                        6399.96
虛擬：                            VT-x
L1d 快取：                        192 KiB
L1i 快取：                        192 KiB
L2 快取：                         1.5 MiB
L3 快取：                         12 MiB
NUMA node0 CPU(s):               0-11

$ uname -a
Linux zhumon-System-Product-Name 5.4.0-48-generic #52-Ubuntu SMP Thu Sep 10 10:58:49 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux

$ gcc --version
gcc (Ubuntu 9.3.0-10ubuntu2) 9.3.0

---
## 視覺化 ternary search tree + bloom filter 的效能表現並分析
> 設計實驗，允許不同的字串輸入並探討 TST 回應的統計分佈
> * 要考慮到 prefix search 的特性還有詞彙的涵蓋率
> * 使用 gnuplot 來製圖

### 假設
由於九萬多個城市的開頭字母分布一定不平均，所以使用不同開頭字母的字串輸入後，得到的統計分布應該會跟字母分布有一定的關係

### 開頭字母分布
由於開頭字母有很多種，但是有很多種開頭字母的數量很少，因此只取最多的前二十個，以下將重複的城市剔除後，顯示各種字母開頭的城市種類數量

### 使用單個字母作為輸入
使用 CPY 方式來尋找以某個字母開頭的城市

./test_common --bench CPY s S


發現跟預期不太一樣（預期時間分佈應該跟城市數量有某種關係）

----
每種查詢都執行 10 次，確認不是偶然的錯誤（查詢每個字母一輪後，執行`echo 3 | sudo tee /proc/sys/vm/drop_caches` 清理快取）

發現跟執行一次的結果相差不大

----
猜測是因為將重複的城市剔除，導致結果不合預期，因此接下來將重複的城市也算進去

發現 U 開頭的城市（或國家）最多（包含重複）但是搜尋速度卻比 S 快

TODO: 藉由 ternary search 的特性思考結果