V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐关注
Meteor
JSLint - a JavaScript code quality tool
jsFiddle
D3.js
WebStorm
推荐书目
JavaScript 权威指南第 5 版
Closure: The Definitive Guide
CatCode
V2EX  ›  JavaScript

JS 里 3200 行的正则匹配,有没有什么好的办法优化一下?

  •  
  •   CatCode · 2019-12-29 18:25:20 +08:00 · 4950 次点击
    这是一个创建于 1551 天前的主题,其中的信息可能已经有所发展或是发生改变。

    其实和某种上网方式有关。

    我相信不少人都用着 SwitchyOmega 这个插件。
    受迫于 Windows 上 OneDrive 这些微软自家的东西都只能用 Windows 系统代理设置,我不得不折腾一个 PAC 文件放 Nginx 上。
    于是我把 SwitchyOmega 的某土啬列表导出成 PAC 文件。顺手用文本编辑器打开一看:

    我的乖乖,3200 行正则

    if (/AABBCC/.test(host)) return "+proxy";
    

    还有 3600 行indexOf

    if (scheme === "http" && url.indexOf("CCDDEE") >= 0) return "+proxy";
    

    每一个请求都要这样匹配这么多正则,效率很低啊。 (没有打算解决这个问题,就是给大家贴出来,图一乐)

    14 条回复    2019-12-30 09:40:17 +08:00
    Cbdy
        1
    Cbdy  
       2019-12-29 18:29:07 +08:00 via Android
    把正则维护到数据库,然后做一个管理页面
    AzadCypress
        2
    AzadCypress  
       2019-12-29 19:23:47 +08:00 via Android   ❤️ 1
    某 list 维护的是 Adblock plus 的规则列表
    adb 使用的详细算法在
    https://adblockplus.org/blog/investigating-filter-matching-algorithms
    iamwho
        3
    iamwho  
       2019-12-29 19:27:10 +08:00
    gfwlist2pac
    Buges
        4
    Buges  
       2019-12-29 19:45:21 +08:00 via Android
    为什么要搞这么复杂?简单的一个大陆白名单就可以解决大多数分流问题了。
    vigack
        5
    vigack  
       2019-12-29 19:51:55 +08:00
    现在都流行答非所问吗。

    最简单的优化应该是加缓存层吧?
    hahasong
        6
    hahasong  
       2019-12-29 20:01:27 +08:00 via iPhone
    3200 行正则有什么问题吗,快的很
    AzadCypress
        7
    AzadCypress  
       2019-12-29 20:05:50 +08:00 via Android
    @AzadCypress
    补充说明一下,大概就是对于一个正则表达式,里面会有连续的字符串,取出第一个长度为 N 的子字符串,计算 hash 放作为 key 存入 hasmap。如果没有长度为 N 子串的话放入另一个列表等待遍历。
    对于目标网址,使用 rabin-karp 算法里计算 hash 的部分可以快速计算出其所有长度为 N 的字串的 hash,使用这个 hash 去 hashmap 中查找,找到同 hash 的就进行正则匹配,匹配不上没找到就遍历此前的另一个列表,再没找到就是没有。
    love
        8
    love  
       2019-12-29 20:24:16 +08:00
    其实不要用那个公共列表就行,那是把全部被墙网站都列了,而实际上你 99%用不到。自己维护一个列表就行。
    lookas2001
        9
    lookas2001  
       2019-12-29 20:24:41 +08:00 via Android
    如果 js 引擎实现到位的话,这些正则应该是可以线性时间(或乘一个系数)内处理完的,所以应该不会特别慢
    Guaidaodl
        10
    Guaidaodl  
       2019-12-29 21:56:11 +08:00
    我觉得理论上最好的方法是把所有的正则合成一个, 然后编译出一个状态机.但是这样这个正则就没有人可以维护了....
    Guaidaodl
        11
    Guaidaodl  
       2019-12-29 21:56:46 +08:00
    所有还是缓存一下匹配的结果就好了...
    dyllen
        12
    dyllen  
       2019-12-30 08:40:00 +08:00
    老哥,不需要放 nginx 呀,用 file:///path/abc.pac 指定 pac 文件就行了呀。我在 linux 下面就是这样干的。
    CatCode
        13
    CatCode  
    OP
       2019-12-30 08:46:40 +08:00
    @dyllen 但 win10 就是不一样啊,win10 的代理设置不支持 file://访问
    zgray
        14
    zgray  
       2019-12-30 09:40:17 +08:00
    可能你需要升级下工具了,有个和 V2EX 的工具名字很像的你值得拥有。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1530 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 176ms · UTC 17:07 · PVG 01:07 · LAX 10:07 · JFK 13:07
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.