这是一个创建于 1420 天前的主题，其中的信息可能已经有所发展或是发生改变。
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 秒。。
 |
1
YouLMAO 2021-02-07 18:56:38 +08:00
|
 |
2
Claar 2021-02-07 21:56:26 +08:00
我认为反前缀的思路感觉也可以，就是应该比正常写法稍慢
我放到 IDE 里认真看才意识到这个写法真的是巨憨批 直接正则匹配所有的 domain，再遍历分析数量不可以吗？ 我认为你的问题是你正则了 1200 次全文，这简直顶级憨批行为 |
|
3
Claar 2021-02-07 22:01:42 +08:00
我的我没注意到子域名的问题，这种情况还是直接反前缀匹配吧
|
 |
6
heart4lor 2021-02-07 23:34:19 +08:00
|
|
10
Claar 2021-02-08 01:48:08 +08:00
@heart4lor #6 我记得 AC 自动机应该是适用于类似正则的多模式匹配吧，他比 trie 的优化和单模式匹配的 KMP 之于暴力搜索一样，通过前缀这个特征去省略掉不必要的搜索
这里应该是直接使用反的前缀比较快，毕竟这里的域名是已知的 |
 |
12
guonaihong 2021-02-08 09:48:04 +08:00
@Claar 把共同前缀字符串提取成一个 node 速度应该会快，就是管理 node 的分裂比较麻烦(一开始是一个 root 节点，有冲突就分裂新的 trie 节点)。就跟 httprouter 的实现一样。
|
|
13
Claar 2021-02-08 10:49:04 +08:00 via iPhone
@guonaihong 我的理解你这变成了不定长匹配，会更慢
|
|
14
guonaihong 2021-02-08 12:00:14 +08:00
@Claar 我用两种方式实现过 trie tree 。前者是标准的，后者是分裂式。benchmark 数据后者会快点。这样吧。感兴趣你可以提供 test data，我有时间写个代码 benchmark 看下。
|
|
15
Claar 2021-02-08 14:25:54 +08:00 via iPhone
@guonaihong 我也没有数据啊，不过我对你的实现倒是有点感兴趣，请问可否放出来看看？
|
|
16
Claar 2021-02-08 14:29:15 +08:00 via iPhone
|
|
17
guonaihong 2021-02-08 14:33:52 +08:00
@Claar ok，没问题。
|
|
18
guonaihong 2021-02-08 14:37:31 +08:00
@Claar 如果题主给数据，就 nice 了，哈哈。
|
Select Language