3 回答
TA贡献1840条经验 获得超5个赞
您的结构在内存方面非常低效,让我们看看内部结构。但在此之前,快速提醒一些 go 类型所需的空间:
布尔值:1 个字节
整数:4 字节
uintptr:4 字节
[N]类型:N*sizeof(type)
[]type: 12 + len(slice)*sizeof(type)
现在,让我们看看你的结构:
type node struct {
root bool // 1 byte
b []byte // 12 + len(slice)*1
output bool // 1 byte
index int // 4 bytes
counter int // 4 bytes
child [256]*node // 256*4 = 1024 bytes
fails [256]*node // 256*4 = 1024 bytes
suffix *node // 4 bytes
fail *node // 4 bytes
}
好的,你应该猜到这里发生了什么:每个节点的重量都超过 2KB,这是巨大的!最后,我们将查看用于初始化 trie 的代码:
func (m *Matcher) buildTrie(dictionary [][]byte) {
max := 1
for _, blice := range dictionary {
max += len(blice)
}
m.trie = make([]node, max)
// ...
}
你说你的字典是 4 MB。如果总共是 4MB,那么就意味着在 for 循环结束时,max = 4MB. 它包含 4 MB 不同的单词,然后max = 4MB*avg(word_length).
我们将采用第一个场景,最好的一个。您正在初始化一个 4M 节点的切片,每个节点使用 2KB。是的,这需要一个不错的 8GB。
您应该查看如何构建您的 trie。从与 Aho-Corasick 算法相关的维基百科页面中,每个节点包含一个字符,因此从根开始最多有 256 个字符,而不是 4MB。
一些使其正确的材料:https ://web.archive.org/web/20160315124629/http://www.cs.uku.fi/~kilpelai/BSA05/lectures/slides04.pdf
TA贡献2037条经验 获得超6个赞
该node
类型的内存大小为2084
字节。我写了一个小程序来演示内存使用情况:https: //play.golang.org/p/szm7AirsDB
如您所见,三个字符串(大小为 11(+1) 个字节)dictionary := []string{"fizz", "buzz", "123"}
需要 24 MB 内存。
如果您的字典有 4 MB 的长度,您将需要大约4000 * 2084 = 8.1 GB
内存。
因此,您应该尝试减小字典的大小。
- 3 回答
- 0 关注
- 599 浏览
添加回答
举报