作者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/cn.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