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

2021-02-07 18:42:48 +08:00
 Peakday

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 秒。。

2244 次点击
所在节点    Go 编程语言
20 条回复
YouLMAO
2021-02-07 18:56:38 +08:00
典型的 trie
leetcode-cn.com/problems/implement-trie-prefix-tree/

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

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

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

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

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/752169

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX