作者danny0838 (道可道非常道)
看板Prob_Solve
標題Fw: [問題] 給字串找出第一個符合的glob
時間Sat Sep 23 08:07:57 2017
※ [本文轉錄自 Programming 看板 #1PnIAqkY ]
作者: danny0838 (道可道非常道) 看板: Programming
標題: [問題] 給字串找出第一個符合的glob
時間: Fri Sep 22 22:48:18 2017
如題，假設資料庫有這樣的鍵-值對：
{
"www.google.com": function A(){},
"*.example.com.*": function B(){},
"*.example.*": function C(){},
"www.*.com.*": function D(){},
"*.mycompany.*.com.*": function E(){},
...
}
語言是用 javascript。
現在希望對於任意給定的字串，
找出第一個符合的鍵執行對應的function。
例如給 "foo.example.com.tw" 要執行 function B
如果鍵是純字串，做起來很簡單，一個 Map 就解決，
但問題是現在的鍵可能是 glob pattern...
我知道可以用暴力法，
意即依序把每個鍵拿去和給定字串比對，
不過資料庫大起來效能會較差，
想知道是否有時間複雜度較低的演算法可用？
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.164.19.182
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Programming/M.1506091700.A.BA2.html
※ 編輯: danny0838 (1.164.19.182), 09/22/2017 22:51:54
1F：推 s25g5d4: 轉成 regular expression 114.45.121.76 09/22 23:03
2F：→ danny0838: 請問使用RegExp如何降低時間複雜度？ 1.164.19.182 09/23 00:03
3F：推 CoNsTaR: B 和 C 不會打架嗎？ 24.114.73.54 09/23 00:13
設計上是有按順序，如果 B 符合了就不執行 C。
※ 編輯: danny0838 (1.164.19.182), 09/23/2017 01:03:59
4F：推 CoNsTaR: map 是用樹做的，你現在的問題是 99.242.178.39 09/23 06:21
5F：→ CoNsTaR: 你的鍵其實代表了另一組鍵，而且這組鍵 99.242.178.39 09/23 06:21
6F：→ CoNsTaR: (以下稱小鍵) 99.242.178.39 09/23 06:21
7F：→ CoNsTaR: 散落在樹的不同地方，所以你的鍵和小鍵 99.242.178.39 09/23 06:21
8F：→ CoNsTaR: 對樹來講其實是互不相干的 99.242.178.39 09/23 06:21
9F：→ CoNsTaR: 如果你能找到一種排序方式，讓一個鍵所 99.242.178.39 09/23 06:21
10F：→ CoNsTaR: 代表的所有小鍵大小連續，那你就能用這 99.242.178.39 09/23 06:21
11F：→ CoNsTaR: 種排序方式來建立樹，那時間複雜度就不 99.242.178.39 09/23 06:21
12F：→ CoNsTaR: 會和map差太多，不過缺點是我覺得某些情 99.242.178.39 09/23 06:21
13F：→ CoNsTaR: 況可能會找不到解 99.242.178.39 09/23 06:21
14F：→ CoNsTaR: 還有，其實你的問題可以去 prob solve 99.242.178.39 09/23 06:21
15F：→ CoNsTaR: 版問 99.242.178.39 09/23 06:21
※ 發信站: 批踢踢實業坊(ptt.cc)
※ 轉錄者: danny0838 (36.227.221.89), 09/23/2017 08:07:57
17F：推 suhorng: 雖然也可以把很多個 pattern 一起弄成一個 DFA 不過不知 09/24 00:38
18F：→ suhorng: 道這 DFA 會多大...@@ 09/24 00:38
19F：→ suhorng: 啊, 沒看到一樓貼的 paper 09/24 00:39
20F：推 yvb: "*" 是否包含 "." ? 若不包含, 那就用 "." 拆分成多個欄位吧. 09/28 19:37
21F：→ yvb: 我的意思是,原PO例子foo.example.com.tw應該符合BD但不符合C 09/30 13:08
22F：→ yvb: 的話,那拆開就只要對應原字串和*的聯集,最後合起來取交集; 09/30 13:11
23F：→ yvb: 另外,要加上欄數的比對,以免犯foo.example.com對到B的錯誤. 09/30 13:13
24F：→ yvb: 當然, 若 glob pattern 不是只有單純 * 的話, 那就不適用了. 09/30 13:20