TL;DR (太長，講結論):
文章標題使用: DBCS_strcasestr
時間複雜度: O(n ^ 2)
※ 引述《shiburin (>\\\<)》之銘言：
: 肥宅我發現
: 如果把搜尋的字串加長
: 搜尋時間就會明顯變長
: 所以ptt的搜尋是用什麼演算法呢
: 該不會是linear search吧
: 跑超久的
: 有沒有卦？
ptt source code: https://github.com/ptt/pttbbs
追下去
|-> 有關文章的程式碼:
| https://github.com/ptt/pttbbs/blob/master/mbbsd/read.c
|
|-> 有關按鍵按下去的觸發 (Ctrl+X, r, y, ...etc):
|
| static int i_read_key(const onekey_t *rcmdlist, keeploc_t *locmem,
| int bid, int bottom_line, int pending_darws)
|
| https://github.com/ptt/pttbbs/blob/master/mbbsd/read.c#L874
|
|-> 有關 z (搜尋) 按下去的程式碼:
| ...
| case '/':
| case '?':
| mode = select_read(locmem, RS_KEYWORD);
| break;
|
| case 'S:
| ...
|
| https://github.com/ptt/pttbbs/blob/master/mbbsd/read.c#L979
|
|-> 先建立出下面那排問你要搜尋啥的輸入欄:
|
| static int
| ask_filter_predicate(filter_predicate_t *pred, int prev_modes, int sr_mode,
| const fileheader_t *fh, int *success)
| ...
| } else if (sr_mode & RS_KEYWORD) {
| if(!getdata(b_lines, 0,
| currmode & MODE_SELECT ? "增加條件 標題: ":"搜尋標題: ",
| keyword, TTLEN, DOECHO) || trim_blank(keyword))
| return READ_REDRAW;
|
| LOG_IF(LOG_CONF_KEYWORD, log_filef("keyword_search_log", LOG_CREAT,
| "%s:%s\n", currboard, keyword));
|
| https://github.com/ptt/pttbbs/blob/master/mbbsd/read.c#L593
|
|-> 然後再來搜尋:
|
| if (select_read_should_build(newdirect, bid, &resume_from, &count) &&
| (count = select_read_build(currdirect, newdirect, !first_select,
| force_full_build ? 0 : resume_from, count,
| match_filter_predicate, &predicate)) < 0) {
|
| https://github.com/ptt/pttbbs/blob/master/mbbsd/read.c#L855
|
|-> 如果沒有被 shortcut, 就會去執行後面的 select_read_build:
|
| static int
| select_read_build(const char *src_direct, const char *dst_direct,
| int src_direct_has_reference, time4_t resume_from, int count,
| int (*match)(const fileheader_t *fh, void *arg), void *arg)
|
| 這邊的 match 是個函式指標，用來搜尋用的。前面傳入的是 match_filter_predicate，
| 因此可以得知是使用這個函式來搜尋。
|
| https://github.com/ptt/pttbbs/blob/master/mbbsd/read.c#L691
|
|-> 執行 match (match_filter_predicate)
|
| if (!match(&fhs[i], arg))
| continue;
|
| https://github.com/ptt/pttbbs/blob/master/mbbsd/read.c#L731
|
|-> 在 pool 中比對
|
| ...
| else if (sr_mode & RS_KEYWORD)
| return DBCS_strcasestr(fh->title, keyword) != NULL;
| ...
|
| DBCS: Double-byte Character Sets 雙位元組字元集。
| 這東西應該是 ptt 內部的字串編碼方式。
| man strcasestr: strstr, strcasestr, strnstr