V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
The Go Programming Language
http://golang.org/
Go Playground
Go Projects
Revel Web Framework
Peakday
V2EX  ›  Go 编程语言

查找匹配文本这段代码运行起来很慢是什么原因

  •  
  •   Peakday · 2021-02-07 18:42:48 +08:00 · 2327 次点击
    这是一个创建于 1389 天前的主题,其中的信息可能已经有所发展或是发生改变。

    package main

    import ( "bufio" "fmt" "io" "os" "regexp" "strings" "sync" )

    func getDomain(cfg string) []string { data := make([]string, 0)

    f, _ := os.Open(cfg)
    defer f.Close()
    
    scan := bufio.NewScanner(f)
    for scan.Scan() {
    	data = append(data, scan.Text())
    }
    return data
    

    }

    func main() { domain := getDomain(os.Args[1])

    data := make(chan string, 1024)
    message := make(map[string]int)
    wg := &sync.WaitGroup{}
    
    f, _ := os.Open(os.Args[2])
    defer f.Close()
    
    br := bufio.NewReader(f)
    
    for {
    	txt, err := br.ReadString('\n')
    	txt = strings.TrimSpace(txt)
    
    	if err == io.EOF {
    		break
    	}
    
    	wg.Add(1)
    	go func(s string, w *sync.WaitGroup) {
    		for _, i := range domain {
    			patt := "(.*)" + regexp.QuoteMeta("."+i) + "($)|" + "(^)" + i + "($)"
    			if b, _ := regexp.MatchString(patt, s); b {
    				data <- i
    				break
    			}
    		}
    		w.Done()
    	}(txt, wg)
    }
    
    wg1 := &sync.WaitGroup{}
    wg1.Add(1)
    go func(w1 *sync.WaitGroup) {
    	for {
    		d, ok := <-data
    		if !ok {
    			for k, v := range message {
    				fmt.Printf("%s:%d\n", k, v)
    			}
    			break
    		}
    		message[d]++
    	}
    	w1.Done()
    }(wg1)
    wg.Wait()
    close(data)
    wg1.Wait()
    

    }

    A 文件是要数据文件,B 文件包含查的关键字 目前 A 文件大概 180w 条数据,B 文件关键字 1200 多个

    A 文件内容: tc.qq.com 1.tc.qq.com osfsr.lenovomm.com

    B 文件内容: tc.qq.com a.com lenovomm.com

    统计 B 文件中所有域名的请求次数,如果 A 文件中的域名属于 B 文件中域名的子域名或本身,均算入请求次数中

    上面的例子最终应得到 tc.qq.com:2 次 a.com:0 次 lenovomm.com:1 次

    现在执行很慢,想请教一下怎么优化。 具体慢到 A 文件包含 1000 条数据,B 文件包含 1100 条数据,执行花费了 17 秒。。

    20 条回复    2021-02-08 15:42:29 +08:00
    YouLMAO
        1
    YouLMAO  
       2021-02-07 18:56:38 +08:00
    典型的 trie
    leetcode-cn.com/problems/implement-trie-prefix-tree/

    你先 string 反过来, 就是求前缀匹配的个数了

    像是专门出的面试题
    Claar
        2
    Claar  
       2021-02-07 21:56:26 +08:00
    我认为反前缀的思路感觉也可以,就是应该比正常写法稍慢

    我放到 IDE 里认真看才意识到这个写法真的是巨憨批
    直接正则匹配所有的 domain,再遍历分析数量不可以吗?

    我认为你的问题是你正则了 1200 次全文,这简直顶级憨批行为
    Claar
        3
    Claar  
       2021-02-07 22:01:42 +08:00
    我的我没注意到子域名的问题,这种情况还是直接反前缀匹配吧
    Peakday
        4
    Peakday  
    OP
       2021-02-07 23:14:15 +08:00
    @YouLMAO 谢谢 换成你这种方法速度嗖嗖的
    Peakday
        5
    Peakday  
    OP
       2021-02-07 23:15:30 +08:00
    @Claar 已经换成反前缀匹配了 A 文件 180w B 文件 1100 条 4s 完成
    heart4lor
        6
    heart4lor  
       2021-02-07 23:34:19 +08:00
    YouLMAO
        7
    YouLMAO  
       2021-02-08 00:16:44 +08:00 via Android
    @Peakday 对 b 文件建 trie 哦,把 count 放在叶子节点
    YouLMAO
        8
    YouLMAO  
       2021-02-08 00:17:37 +08:00 via Android
    @heart4lor 厉害,扩展面试题,今年就出这道题了 实现 grep
    YouLMAO
        9
    YouLMAO  
       2021-02-08 00:18:34 +08:00 via Android
    @heart4lor 如果一小时写出来,包裹给 150 吧
    Claar
        10
    Claar  
       2021-02-08 01:48:08 +08:00
    @heart4lor #6 我记得 AC 自动机应该是适用于类似正则的多模式匹配吧,他比 trie 的优化和单模式匹配的 KMP 之于暴力搜索一样,通过前缀这个特征去省略掉不必要的搜索
    这里应该是直接使用反的前缀比较快,毕竟这里的域名是已知的
    Claar
        11
    Claar  
       2021-02-08 01:54:17 +08:00
    @Peakday #5 感觉 4s 还是有点慢?
    guonaihong
        12
    guonaihong  
       2021-02-08 09:48:04 +08:00
    @Claar 把共同前缀字符串提取成一个 node 速度应该会快,就是管理 node 的分裂比较麻烦(一开始是一个 root 节点,有冲突就分裂新的 trie 节点)。就跟 httprouter 的实现一样。
    Claar
        13
    Claar  
       2021-02-08 10:49:04 +08:00 via iPhone
    @guonaihong 我的理解你这变成了不定长匹配,会更慢
    guonaihong
        14
    guonaihong  
       2021-02-08 12:00:14 +08:00
    @Claar 我用两种方式实现过 trie tree 。前者是标准的,后者是分裂式。benchmark 数据后者会快点。这样吧。感兴趣你可以提供 test data,我有时间写个代码 benchmark 看下。
    Claar
        15
    Claar  
       2021-02-08 14:25:54 +08:00 via iPhone
    @guonaihong 我也没有数据啊,不过我对你的实现倒是有点感兴趣,请问可否放出来看看?
    Claar
        16
    Claar  
       2021-02-08 14:29:15 +08:00 via iPhone
    @guonaihong 就用题主说到的
    a.com b.com c.com
    ba.a.com fg.b.com
    格式可好?
    guonaihong
        17
    guonaihong  
       2021-02-08 14:33:52 +08:00
    @Claar ok,没问题。
    guonaihong
        18
    guonaihong  
       2021-02-08 14:37:31 +08:00
    @Claar 如果题主给数据,就 nice 了,哈哈。
    Claar
        19
    Claar  
       2021-02-08 14:48:54 +08:00 via iPhone
    @Claar 前面表述错了,AC 自动机和 trie 都是多模式匹配,AC 自动机的优势在于 trie 失败后直接转向下一个可能的 pattern,属于不定型的模式匹配优化,但是在这个例子中一个字串必然属于一个反前缀顺序的确定模式,直接 trie 就对了
    Claar
        20
    Claar  
       2021-02-08 15:42:29 +08:00
    @YouLMAO #9 包裹给 150 是什么意思啊,不过我曾经花过大概 3 小时不到根据知乎上描述的正则表达式原理实现过正则,花了一小时不到学习实现了 trie 然后花了一小时不到学习优化成了 AC 自动机,感觉 AC 自动机不难。我半年不刷题直接写应该一小时也够了
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   6135 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 06:17 · PVG 14:17 · LAX 22:17 · JFK 01:17
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.