2018q3 Homework3 (dict)

# 2018q3 Homework3 (dict) contributed by < [`jason53415`](https://github.com/jason53415/dict) > ## 執行測試 * 測試 test_cpy 預設輸出結果： ```shell $ ./test_cpy --bench ternary_tree, loaded 259112 words in 0.112555 sec ``` * 當命令列參數只有 `--bench` 時，test_cpy 會先將字典檔中所有的字插入 ternary tree，接著去執行 `bench_test()` 然後結束程式；而 `bench_test()` 實際上就在 ternary tree 中搜尋一遍字典檔裡所有的字，並記錄下每一次所花的時間儲存在 bench_cpy.txt 中。 * 接著我們可以使用 gnuplot 中的 `stats` 來統計一下時間的分佈： ```shell $ gnuplot scripts/runtimebox.gp "scripts/runtimebox.gp", line 1: warning: Cannot find or open file "bench_ref.txt" "scripts/runtimebox.gp", line 1: warning: Can't read data file * FILE: Records: 247614 Out of range: 0 Invalid: 0 Column headers: 0 Blank: 0 Data Blocks: 1 * COLUMN: Mean: 0.2284 Std Dev: 0.2763 Sample StdDev: 0.2763 Skewness: 21.4626 Kurtosis: 743.2602 Avg Dev: 0.1157 Sum: 56548.4148 Sum Sq.: 31810.7971 Mean Err.: 0.0006 Std Dev Err.: 0.0004 Skewness Err.: 0.0049 Kurtosis Err.: 0.0098 Minimum: 0.0000 [ 5] Maximum: 10.7288 [ 52737] Quartile: 0.0000 Median: 0.2384 Quartile: 0.2384 ``` * 以上為直接用 gnuplot 直接執行 `runtimebox.gp` 的結果，但因為還沒執行 test_ref 生成 bench_ref.txt，所以會生成錯誤訊息，以下為 `runtimebox.gp` 的內容： ```bash stats "bench_ref.txt" using 2 stats "bench_cpy.txt" using 2 ``` * 接著依照上述的結果調整 x 軸的資料筆數上限，以及 y 軸的時間範圍，就可以用 `runtime3.gp` 得到以下的圖： ![](https://i.imgur.com/FfJtH7d.png) ## 測試環境 ### OS ```shell $ uname -a Linux scream-47860 4.15.0-36-generic #39-Ubuntu SMP Mon Sep 24 16:19:09 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux ``` ### Memory ```shell $ free -m total used free shared buff/cache available Mem: 7920 3912 2899 172 1108 3590 置換： 15257 0 15257 ``` ### CPU ```shell $ cat /proc/cpuinfo processor : 0 vendor_id : GenuineIntel cpu family : 6 model : 60 model name : Intel(R) Core(TM) i5-4460 CPU @ 3.20GHz stepping : 3 microcode : 0x25 cpu MHz : 2487.793 cache size : 6144 KB physical id : 0 siblings : 4 core id : 0 cpu cores : 4 apicid : 0 initial apicid : 0 fpu : yes fpu_exception : yes cpuid level : 13 wp : yes 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 tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm cpuid_fault epb invpcid_single pti ssbd ibrs ibpb stibp tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid xsaveopt dtherm ida arat pln pts flush_l1d bugs : cpu_meltdown spectre_v1 spectre_v2 spec_store_bypass l1tf bogomips : 6385.12 clflush size : 64 cache_alignment : 64 address sizes : 39 bits physical, 48 bits virtual power management: processor : 1 vendor_id : GenuineIntel cpu family : 6 model : 60 model name : Intel(R) Core(TM) i5-4460 CPU @ 3.20GHz stepping : 3 microcode : 0x25 cpu MHz : 2918.424 cache size : 6144 KB physical id : 0 siblings : 4 core id : 1 cpu cores : 4 apicid : 2 initial apicid : 2 fpu : yes fpu_exception : yes cpuid level : 13 wp : yes 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 tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm cpuid_fault epb invpcid_single pti ssbd ibrs ibpb stibp tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid xsaveopt dtherm ida arat pln pts flush_l1d bugs : cpu_meltdown spectre_v1 spectre_v2 spec_store_bypass l1tf bogomips : 6385.12 clflush size : 64 cache_alignment : 64 address sizes : 39 bits physical, 48 bits virtual power management: processor : 2 vendor_id : GenuineIntel cpu family : 6 model : 60 model name : Intel(R) Core(TM) i5-4460 CPU @ 3.20GHz stepping : 3 microcode : 0x25 cpu MHz : 3071.534 cache size : 6144 KB physical id : 0 siblings : 4 core id : 2 cpu cores : 4 apicid : 4 initial apicid : 4 fpu : yes fpu_exception : yes cpuid level : 13 wp : yes 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 tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm cpuid_fault epb invpcid_single pti ssbd ibrs ibpb stibp tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid xsaveopt dtherm ida arat pln pts flush_l1d bugs : cpu_meltdown spectre_v1 spectre_v2 spec_store_bypass l1tf bogomips : 6385.12 clflush size : 64 cache_alignment : 64 address sizes : 39 bits physical, 48 bits virtual power management: processor : 3 vendor_id : GenuineIntel cpu family : 6 model : 60 model name : Intel(R) Core(TM) i5-4460 CPU @ 3.20GHz stepping : 3 microcode : 0x25 cpu MHz : 2990.358 cache size : 6144 KB physical id : 0 siblings : 4 core id : 3 cpu cores : 4 apicid : 6 initial apicid : 6 fpu : yes fpu_exception : yes cpuid level : 13 wp : yes 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 tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm cpuid_fault epb invpcid_single pti ssbd ibrs ibpb stibp tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid xsaveopt dtherm ida arat pln pts flush_l1d bugs : cpu_meltdown spectre_v1 spectre_v2 spec_store_bypass l1tf bogomips : 6385.12 clflush size : 64 cache_alignment : 64 address sizes : 39 bits physical, 48 bits virtual power management: ```

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.