Golang Go语言中查找匹配文本这段代码运行起来很慢是什么原因
Golang Go语言中查找匹配文本这段代码运行起来很慢是什么原因
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 秒。。
更多关于Golang Go语言中查找匹配文本这段代码运行起来很慢是什么原因的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html
典型的 trie
leetcode-cn.com/problems/implement-trie-prefix-tree/
你先 string 反过来, 就是求前缀匹配的个数了
像是专门出的面试题
更多关于Golang Go语言中查找匹配文本这段代码运行起来很慢是什么原因的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html
我认为反前缀的思路感觉也可以,就是应该比正常写法稍慢
我放到 IDE 里认真看才意识到这个写法真的是巨憨批
直接正则匹配所有的 domain,再遍历分析数量不可以吗?
我认为你的问题是你正则了 1200 次全文,这简直顶级憨批行为
我的我没注意到子域名的问题,这种情况还是直接反前缀匹配吧
谢谢 换成你这种方法速度嗖嗖的
已经换成反前缀匹配了 A 文件 180w B 文件 1100 条 4s 完成
对 b 文件建 trie 哦,把 count 放在叶子节点
厉害,扩展面试题,今年就出这道题了 实现 grep
如果一小时写出来,包裹给 150 吧
#6 我记得 AC 自动机应该是适用于类似正则的多模式匹配吧,他比 trie 的优化和单模式匹配的 KMP 之于暴力搜索一样,通过前缀这个特征去省略掉不必要的搜索
这里应该是直接使用反的前缀比较快,毕竟这里的域名是已知的
#5 感觉 4s 还是有点慢?
把共同前缀字符串提取成一个 node 速度应该会快,就是管理 node 的分裂比较麻烦(一开始是一个 root 节点,有冲突就分裂新的 trie 节点)。就跟 httprouter 的实现一样。
我的理解你这变成了不定长匹配,会更慢
我用两种方式实现过 trie tree 。前者是标准的,后者是分裂式。benchmark 数据后者会快点。这样吧。感兴趣你可以提供 test data,我有时间写个代码 benchmark 看下。
我也没有数据啊,不过我对你的实现倒是有点感兴趣,请问可否放出来看看?
ok,没问题。
如果题主给数据,就 nice 了,哈哈。
前面表述错了,AC 自动机和 trie 都是多模式匹配,AC 自动机的优势在于 trie 失败后直接转向下一个可能的 pattern,属于不定型的模式匹配优化,但是在这个例子中一个字串必然属于一个反前缀顺序的确定模式,直接 trie 就对了
#9 包裹给 150 是什么意思啊,不过我曾经花过大概 3 小时不到根据知乎上描述的正则表达式原理实现过正则,花了一小时不到学习实现了 trie 然后花了一小时不到学习优化成了 AC 自动机,感觉 AC 自动机不难。我半年不刷题直接写应该一小时也够了
在Golang中,如果你发现查找匹配文本的代码运行得很慢,可能有几个原因:
-
算法效率:首先检查你使用的查找算法。例如,简单的线性搜索(O(n)时间复杂度)在处理大数据集时会很慢。考虑使用更高效的算法,如KMP(Knuth-Morris-Pratt,O(n+m)时间复杂度)或Boyer-Moore等。
-
正则表达式:如果你使用正则表达式进行匹配,确保正则表达式是高效的。复杂的正则表达式或不必要的回溯会导致性能下降。
-
字符串处理:频繁的字符串拼接或复制操作(尤其是大字符串)会消耗大量时间和内存。使用
strings.Builder
来构建字符串,可以提高性能。 -
并发处理:如果处理的数据量很大,考虑使用Go的并发特性(goroutines和channels)来并行处理数据。
-
I/O操作:如果查找操作涉及大量的I/O(如从文件或网络读取数据),I/O瓶颈可能是性能问题的根源。优化I/O操作,如使用缓冲读取,可以减少等待时间。
-
硬件限制:最后,不要忘记检查硬件资源。CPU、内存和网络带宽等硬件限制都可能影响性能。
优化性能通常需要从多个角度进行分析和调整。建议从算法和数据结构开始,然后逐步检查其他潜在的性能瓶颈。使用Go的性能分析工具(如pprof)可以帮助你识别代码中的热点和性能瓶颈。