V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
imn1
V2EX  ›  问与答

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

  •  
  •   imn1 · 2015-12-30 12:08:12 +08:00 · 2169 次点击
    这是一个创建于 3251 天前的主题,其中的信息可能已经有所发展或是发生改变。
    求: 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
        1
    pathletboy  
       2015-12-30 12:15:10 +08:00   ❤️ 1
    正则取出 url 的根域,然后通过 dict/map 查询键是否存在。
    jmc891205
        2
    jmc891205  
       2015-12-30 12:18:07 +08:00   ❤️ 1
    二分查找?不过前提是 Domain List 是有序的
    GtDzx
        3
    GtDzx  
       2015-12-30 12:21:01 +08:00   ❤️ 1
    Hash...
    kaneg
        4
    kaneg  
       2015-12-30 12:52:10 +08:00   ❤️ 1
    set 就是干这种活的
    clino
        5
    clino  
       2015-12-30 13:01:20 +08:00 via Android   ❤️ 1
    将 domain list 变成正则然后匹配 也是一种方法 一步搞定
    imn1
        6
    imn1  
    OP
       2015-12-30 13:23:05 +08:00
    @kaneg
    其实是想问 javascript ,写 UC 脚本碰到

    @clino
    合成一个长正则? github.com|v2ex.com|google.com ?这是个想法
    northisland
        7
    northisland  
       2015-12-30 13:23:28 +08:00   ❤️ 1
    @GtDzx 不能支持再多
    xufang
        8
    xufang  
       2015-12-30 13:30:15 +08:00   ❤️ 1
    Tonni
        9
    Tonni  
       2015-12-30 13:32:46 +08:00   ❤️ 1
    yingsunwl
        10
    yingsunwl  
       2015-12-30 13:36:30 +08:00   ❤️ 1
    AC 状态机, Aho-Corasick string matching algorithm
    SoloCompany
        11
    SoloCompany  
       2015-12-30 13:42:22 +08:00   ❤️ 1
    字符串查找最快的数据结构理论上应该是状态机查找树,只需遍历一次,但字典变化导致的状态机更新是很麻烦的,而且占用的空间也比较庞大
    当然更多场景是使用 hash 查找,同样只需要遍历一次来计算 hash ,无冲突或者少量冲突的话和状态机的效率基本上差不多
    clino
        12
    clino  
       2015-12-30 15:56:56 +08:00
    @imn1 我之前写的版权扫描工具就是这种方法
    https://github.com/zhangchunlin/scancopyright/blob/master/apps/Scan/settings.ini#L14
    这里有很多正则表达式,一起拼出一个超大的正则出来
    h4x3rotab
        13
    h4x3rotab  
       2015-12-30 20:04:11 +08:00 via iPhone   ❤️ 1
    正则效率低于 ac 自动机,但是可以现成用, hash 是很好的办法,效率不比 ac 自动机低。具体到 js ,推荐还是 hash 吧,正则这个路子太野了,估计效率低一点,因为正则不是用来做这做事情的。
    imn1
        14
    imn1  
    OP
       2015-12-30 21:05:57 +08:00
    @h4x3rotab
    请教一下 hash 例子或文章,扔下 js 十多年,现在都变样了
    h4x3rotab
        15
    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
        16
    imn1  
    OP
       2016-01-01 02:48:31 +08:00
    @h4x3rotab
    原来就是指字典,这个知道是 hash 保存,还一直以为有个 hash 算法
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2501 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 31ms · UTC 15:32 · PVG 23:32 · LAX 07:32 · JFK 10:32
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.