
306
|
第十一章
faddishness
'melanesians'
Kharálampos
PizzaInACup™
url="http://en.wikipedia.org/wiki?curid=363886"
VIIIa),
Superbagnères.
我們會使用這個文字樣本,測試我們能夠多迅速地建立「針對每個獨特單詞存放一個
實例」的資料結構,接著,看看我們能夠多快速地查詢已知單詞(我們會使用很罕見
的
“
Zwiebel
”
—源自畫家 Alfred Zwiebel)。這讓我們詢問,「以前看過 Zwiebel 嗎?」
token 查詢是一種相當常見的問題,能夠迅速進行是很重要的。
當你在自己的問題上嘗試這些容器時,請務必瞭解,你可能會看到不同的
行為。每個容器以不同的方式建構它的內部結構;傳進不同類型的 token
很可能影響結構的建造時間,而且,不同長度的 token 也會影響查詢時
間。注意,總是以有條理的方式進行測試。
對 800 萬個 Token 試驗這些方法
圖 11-1 顯示,800 萬個 token 的文字檔(111 MB 的原始資料)以幾種我們會在本節討
論到的容器進行儲存。x 軸顯示每個容器的 RAM 使用量,y 軸記錄查詢時間,而每個點
的大小與建造該結構所花的時間相關聯(越大表示花越長時間)。
如圖所示,
set
與
DAWG
範例使用大量的 RAM。
list
範例既耗費 RAM 又緩慢。Marisa
trie 和 HAT trie 範例對這個資料集而言是最有效率的;它們使用的 RAM 只有其他方法 ...