一个 URL，一组 Domain List，有没有比遍历一次更方便的方案

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

V2EX 提问指南

这是一个创建于 3242 天前的主题，其中的信息可能已经有所发展或是发生改变。

求： URL 的主域名是否在 Domain List 里面
"https://www.v2ex.com/new/qna"
["github.com", "v2ex.com", "google.com"……]

第 1 条附言 · 2016-01-01 03:02:52 +08:00

晕死，原来 js ES6 已经有 set 集合，扔下 10 年知识没更新啊
s = new Set(数据列);
然后 s.has(单元)就能判断
还能用 map ， Firefox 从 v15 已经支持……唉，去脑补一下

16 条回复 • 2016-01-01 02:48:31 +08:00

pathletboy

2015-12-30 12:15:10 +08:00

正则取出 url 的根域，然后通过 dict/map 查询键是否存在。

jmc891205

2015-12-30 12:18:07 +08:00

二分查找？不过前提是 Domain List 是有序的

GtDzx

2015-12-30 12:21:01 +08:00

Hash...

kaneg

2015-12-30 12:52:10 +08:00

set 就是干这种活的

clino

2015-12-30 13:01:20 +08:00 via Android

将 domain list 变成正则然后匹配也是一种方法一步搞定

imn1

2015-12-30 13:23:05 +08:00

@kaneg
其实是想问 javascript ，写 UC 脚本碰到

@clino
合成一个长正则？ github.com|v2ex.com|google.com ？这是个想法

northisland

2015-12-30 13:23:28 +08:00

@GtDzx 不能支持再多

xufang

2015-12-30 13:30:15 +08:00

https://publicsuffix.org/

Tonni

2015-12-30 13:32:46 +08:00

楼主可以参考下这段代码： https://github.com/iyee/gfwlist2pac/blob/master/gfwlist2pac/main.py#L107

yingsunwl

2015-12-30 13:36:30 +08:00

AC 状态机， Aho-Corasick string matching algorithm

SoloCompany

2015-12-30 13:42:22 +08:00

字符串查找最快的数据结构理论上应该是状态机查找树，只需遍历一次，但字典变化导致的状态机更新是很麻烦的，而且占用的空间也比较庞大
当然更多场景是使用 hash 查找，同样只需要遍历一次来计算 hash ，无冲突或者少量冲突的话和状态机的效率基本上差不多

clino

2015-12-30 15:56:56 +08:00

@imn1 我之前写的版权扫描工具就是这种方法
https://github.com/zhangchunlin/scancopyright/blob/master/apps/Scan/settings.ini#L14
这里有很多正则表达式,一起拼出一个超大的正则出来

h4x3rotab

2015-12-30 20:04:11 +08:00 via iPhone

正则效率低于 ac 自动机，但是可以现成用， hash 是很好的办法，效率不比 ac 自动机低。具体到 js ，推荐还是 hash 吧，正则这个路子太野了，估计效率低一点，因为正则不是用来做这做事情的。

imn1

2015-12-30 21:05:57 +08:00

@h4x3rotab
请教一下 hash 例子或文章，扔下 js 十多年，现在都变样了

h4x3rotab

2015-12-31 22:39:05 +08:00 via iPhone

@imn1 js 的 hash 就是字典了，只不过只关心 key 存不存在，不关心 value 。比如这样的：
var dic = {}
dic['aaa.com'] = true
var domain = getDomainFromUrl(url)
if (dic[domain]) return true

imn1

2016-01-01 02:48:31 +08:00

@h4x3rotab
原来就是指字典，这个知道是 hash 保存，还一直以为有个 hash 算法