資料結構專題 - 論文查詢
Last updated on June 17, 2024
Contents
前言
筆者這學期的眾多系必修中有著一堂對資工系來說很重要卻也很難的課 —— 資料結構。撇除小考不談，上機考的難度要花大約 1/3 學期適應；期中末考更是不用說，直接被炸死。所以現在期末專題就從加分項變成救命項了 owo。
成績公布後的筆者：結果幸好期末考沒有炸得很厲害，還沒調分前就已經在 A+ 的底了 uwu。
介紹
功能
資結大魔王在學期末要用 C++ 做一個 CLI 的論文查詢器作為專題，簡而言之就是搜尋引擎。這個引擎要可以在輸入資料集後，應付使用者的多種查詢指令：包含準確（exact）、前綴（prefix）、通配符（wildcard）、以及後綴（postfix）查詢；指令之間也要可以進行聯集、交集、差集運算，以滿足使用者的使用需求。程式執行時間限時 4 秒。
輸入輸出
輸入由資料集與指令檔組成：
- 資料集：一個資料夾，其中包含多個 txt 格式的論文資訊。（約 1000 ~ 9000 筆）
- 指令檔：一個 txt 檔，其中有多行查詢指令。（約 200 筆）
輸出只有一個 txt，要包含所有指令的查詢結果。（最多可以到 20 萬筆輸出）
思路
基礎方向
資料結構
最基本的方案即是使用 字典樹－trie 這個資料結構（筆者都念 try）。trie 在經過一些修改後都可以應付多種指令；唯獨通配符查詢的時間複雜度看起來有點不妙。所以筆者去查了些資料試圖優化。
筆者在搜索通配符查詢適合的資料結構後[1]，發現 DAWG（directed acyclic word graph）不只同時支援 trie 的功能，且比 trie 佔更少記憶體空間，在進行通配查詢時可降低搜尋複雜度[2]。但問題是：從 trie 建出 DAWG 的過程昂貴、複雜、又有插入時必須要以字典序輸入的額外條件，無法搭配這次專題要實作的線上演算法。因此筆者仍然選用一開始的 trie 進行實作，決定跑出來後再看看需不需要補救。
運作邏輯
程式整體的運作順序大約被劃分成三大步驟：
- 讀檔 - 從資料集讀入單字
- 建樹 - 建出兩棵 trie，一棵應對 exact, prefix, wildcard 搜尋；一棵專門進行 postfix 查詢
- 查詢 - 將指令讀入，並對各論文內文進行查詢後輸出符合論文的標題
在前期尚未平行優化階段時，(1) 與 (2) 其實是同時進行的：每讀入一個字，就把它丟入兩棵 trie 中。但在後期的平行優化階段，這兩步會被細分並重複循環。
撰寫
在想好基本的撰寫方式後，筆者就開始了沒日沒夜的實作工作。那時候還正逢期末考前夕，筆者最後是先把基本程式都寫出來後才去讀期末，幸好還有時間 owo。
優化
寫好的程式肯定是要優化的，不然那時候筆者跑出來的速度肯定是連看都不能看：1000 筆的輸入就要跑 2 秒多。但優化靈感來自哪呢？那肯定就是跟同學一起討論了。
從同學那得到的優化靈感
- 捨去 suffix trie
其實一開始有段時間筆者是沒有注意到「postfix 就是反過來的 prefix」這點的，繞遠路用了 suffix tree 去做後綴查詢。但 suffix tree 的建置過程比 trie 還要貴很多，而且 suffix tree 也不是主要拿來做後綴查詢。這也是筆者一開始程式 1000 筆要跑 2 秒多的原因。
後來在跟一位同學討論時，他提出了可不可以用一棵 trie + prefix 查詢的原理實現 postfix 查詢的想法。筆者想了想後發現確實可以，但沒辦法只用一棵 trie，必須要用另一顆倒過來的 trie 進行查詢，否則使用原生的 trie 反而要多做相當多步驟才能完成一次查詢。
- 用 vector 作為答案集儲存容器
在單一個 trie node 的底下，會儲存著 inverted index。筆者直覺上使用了 unordered_set 作為容器。但筆者在後期跟另一位同學的討論過程發現：他雖然還沒有做任何優化，但他建樹的時間比筆者快了快 700ms。為何？
筆者注意到他是使用 vector 作為容器。且在每次插入時會檢查最後一個數以避免重複插入。因此，要以這樣的方式與 set 有同樣的功能，那就是輸入要是有序的。另一方面，vector 的 push_back 速度遠比 set 的 insert 還要來得快。因此在筆者把跟這方面相關的容器都換成 vector 之後，一棵 trie 的建樹時間減少了 700 ~ 800ms，而 20 萬筆的指令輸出速度增加了一倍。果然還是不能小看 vector owo。
筆者想到的優化方式
- parallel
平行其實是筆者最直覺的優化方式。問題是筆者根本沒學過 C++ 的平行究竟要怎麼寫，且在學完開始實作時又因為炸了一堆 segmentation fault 而讓筆者自我懷疑，究竟有沒有平行設計可以幫得上忙的地方。
幸好，後來筆者有想到：與其在 trie 做插入時開整整 26 個 thread 下去跑以 a~z 為開頭的字而把記憶體搞爛，還不如同時建兩棵 trie 來得有效率。在這之後，筆者發現讀檔其實也很慢（讀 9000 個檔要差不多 600 ms），所以筆者就把原始流程以高階的平行設計角度改為：
- 以批次為單位進行平行讀檔
- 循序式處理檔案資料以確保有序性
- 用處理完的資料平行建樹
- 重複 (1) ~ (3) 直到沒有資料要讀
- 循序式處理指令輸入
(5) 之所以沒有改成平行是因為設計上太繁雜了，要開 buffer 給兩棵 trie 作為指令輸入，返回時又因為有序性要放回對應的空位中，最後才能進行集合運算。而且指令處裡其實也才佔 100ms 左右，比起優化後只剩 500ms 的前置流程來講（原本跑 9000 筆可能要 20 多秒），在這上面優化可能也不會讓速度加快多少。
- string iterator & reverse_iterator
原本在將字串或是指令傳入 trie 中時，都要做昂貴的 string operation，像是去頭去尾或是把字串反過來後再丟進去。這類操作基本上複雜度都是正比於字串長度的。如果改為將起始與終止的迭代器傳入，那就不需要做任何的前處理。但這個優化在最後好像沒有優化太多，可能是字串平均長度都不長，但感覺還是有它價值在 owo。
思路部分到這邊就大致結束了，前前後後經歷了 6 個版本與快 100 個小時的工作時間。有興趣看實際程式碼與更詳細的實作流程的人可以前往這裡。
速度評測
平台
筆者在寫這個專題前的程式幾乎全部都是在 windows 本機上跑（除了一些 DC Bot 有跑在 ubuntu 的 VPS 上過）。但因為到時候專題的 code 是要在 linux 上跑，而剛好這學期有另外一堂課的 lab 已經有給了個 linux 的虛擬機檔，所以筆者就直接沿用那台 VM 了 uwu。
從整體跑下來的結果來看，在 linux 上跑的時需只有 windows 的大概 0.74 ~ 0.8 倍而已。下面順便放一張整個優化過程的線性預估時間圖：
x 軸單位是 100 筆資料；y 軸單位是 100 ms；左邊藍線是這次測資上限；藍線右半邊就是預估在 4 秒內可以跑完多少輸入。
實際數據
| Dataset size | Linux (ms) | Windows (ms) | Memory (MB) |
|---|---|---|---|
| 100 | 15 | 12 | 8.9 |
| 1000 | 85 | 100 | 67.2 |
| 9000 | 575 | 850 | 461.8 |
| 20000 | 1260 | 1880 | 993.0 |
| 30000 | 1850 | 2850 | 1444.4 |
| 31000 | 1900 | 2925 | 1486.5 |
| 35000 | N/A | N/A | N/A |
Linux 版本：Ubuntu 22.04.3 LTS
CPU 皆為 11th Gen Intel® Core™ i7-11800H
除了 100 大小的數據集是用小指令檔（只有 8 個 query）下去測之外，其他都是用 200 個 query 的指令檔下去測。Not Available 是因為已經跳 std::bad_alloc 錯誤了，記憶體不夠根本跑不出來。（inverted index 占空間太大）
稍微描點過後，筆者發現實際時間會比線性再好一點點。
而以下是評分時助教方跑出來的實際數據：
CPU 為 12th Gen Intel® Core™ i7-12700K
10000 筆輸入 + 更多筆 query cmd 只花了約 323 ms，運行時間班級排名為 3/109。正好前兩名都是筆者朋友，不知道他們是用了甚麼神奇方法把運行時間壓到 2 開頭的，或許是運行環境差異所以測不出來優化點 owo？
評價
難易度
- 找資料：🌕🌕🌕🌑🌑
- 實作 ：🌕🌗🌑🌑🌑
- 優化 ：🌕🌕🌕🌕🌑
因為擾人的 segmentation fault 是優化過程中的好夥伴，所以筆者優化過程中超常牙起來 owo。
應用
筆者在看到專題的那時就想到之前有接觸過一個叫 BombParty 的闔家歡遊戲，遊戲規則是要輪流想出包含特定子字串的英文單字。所以只要隨便找個很多單字的資料集再以 *XXX* 作為指令（XXX 是子字串）就可以把這個程式拿來作弊了(X)。所以筆者做專題時的心態有點像為了自己而做，醬比純粹做個專題有趣多了 uwu。
不過這個專案沒意外的話應該是會暫時被打入冷宮，到時候要用到時再來修就好了。
那麼，就先醬。