1
pathletboy 2015-12-30 12:15:10 +08:00 1
正则取出 url 的根域,然后通过 dict/map 查询键是否存在。
|
2
jmc891205 2015-12-30 12:18:07 +08:00 1
二分查找?不过前提是 Domain List 是有序的
|
3
GtDzx 2015-12-30 12:21:01 +08:00 1
Hash...
|
4
kaneg 2015-12-30 12:52:10 +08:00 1
set 就是干这种活的
|
5
clino 2015-12-30 13:01:20 +08:00 via Android 1
将 domain list 变成正则然后匹配 也是一种方法 一步搞定
|
6
imn1 OP |
7
northisland 2015-12-30 13:23:28 +08:00 1
@GtDzx 不能支持再多
|
8
xufang 2015-12-30 13:30:15 +08:00 1
|
9
Tonni 2015-12-30 13:32:46 +08:00 1
|
10
yingsunwl 2015-12-30 13:36:30 +08:00 1
AC 状态机, Aho-Corasick string matching algorithm
|
11
SoloCompany 2015-12-30 13:42:22 +08:00 1
字符串查找最快的数据结构理论上应该是状态机查找树,只需遍历一次,但字典变化导致的状态机更新是很麻烦的,而且占用的空间也比较庞大
当然更多场景是使用 hash 查找,同样只需要遍历一次来计算 hash ,无冲突或者少量冲突的话和状态机的效率基本上差不多 |
12
clino 2015-12-30 15:56:56 +08:00
@imn1 我之前写的版权扫描工具就是这种方法
https://github.com/zhangchunlin/scancopyright/blob/master/apps/Scan/settings.ini#L14 这里有很多正则表达式,一起拼出一个超大的正则出来 |
13
h4x3rotab 2015-12-30 20:04:11 +08:00 via iPhone 1
正则效率低于 ac 自动机,但是可以现成用, hash 是很好的办法,效率不比 ac 自动机低。具体到 js ,推荐还是 hash 吧,正则这个路子太野了,估计效率低一点,因为正则不是用来做这做事情的。
|
15
h4x3rotab 2015-12-31 22:39:05 +08:00 via iPhone
|