初级会员
  • 第 46972 位会员
  • tianqy
  • 云霄
  • 2020-01-02 14:29:26
  • Offline
  • 20 16

最近发布的文章

最近发布的项目

    暂无

最近的评论

  • 评论了主题 AC自动机实现
    在实际应用中,发现AC自动机实现有问题,在设置failNode时,是需要BFS遍历每层节点,为其子节点设置failNode的,但是,在实现中把这块忘了,只设置了前两层节点的failNode;对于failNode设置这块进行了更新,除了增加节点记录,还优化了记录方式,之前是使用list,现在换成slice,因为要一边遍历节点,一边要记录子节点,还要删除已遍历过的节点,使用slice主要是想整体删除;另外,在匹配方面也做了修改,加快查找速度,核心改动可以查看"// DONE"注释部分,为了方便查看,直接贴代码了: ```go const childNodeCount = 16 // AC自动机节点结构定义 type AcAutoNode struct { endCount int // 结束模式串个数 prefixCount int // 前缀模式串个数 failNode *AcAutoNode // fail指针节点 childNode [childNodeCount]*AcAutoNode // 子节点 } // AC自动机初始化 var GAcAuto *AcAutoNode func init() { GAcAuto = new(AcAutoNode) } func BuildTree(s []string) { // 遍历模式串列表 for uli := 0; uli < len(s); uli++ { node := GAcAuto // 遍历模式串字符 for _, runeCh := range s[uli] { // 分高低位判断 runeStr := string(runeCh) for ulj := 0; ulj < len(runeStr); ulj++ { indexHigh := runeStr[ulj] / childNodeCount if node.childNode[indexHigh] == nil { node.childNode[indexHigh] = &AcAutoNode{} } node = node.childNode[indexHigh] indexLow := runeStr[ulj] % childNodeCount if node.childNode[indexLow] == nil { node.childNode[indexLow] = &AcAutoNode{} } node = node.childNode[indexLow] } node.prefixCount++ } node.endCount++ } } func SetNodeFailPoint() { GAcAuto.failNode = nil nodeList := make([]*AcAutoNode, 0, 10000) nodeList = append(nodeList, GAcAuto) // 逐层遍历trie树节点,为节点设置fail指针 for { nodeListSize := len(nodeList) if nodeListSize <= 0 { break } for uli := 0; uli < nodeListSize; uli++ { node := nodeList[uli] if node == GAcAuto { // 根节点的子节点的fail指针都指向根节点 for ulj := 0; ulj < childNodeCount; ulj++ { if node.childNode[ulj] != nil { node.childNode[ulj].failNode = GAcAuto nodeList = append(nodeList, node.childNode[ulj]) // DONE } } } else { // 遍历父节点,依据父节点的failNode,为其每个子节点设置failNode for ulj := 0; ulj < childNodeCount; ulj++ { if node.childNode[ulj] != nil { nodeList = append(nodeList, node.childNode[ulj]) // DONE // fail指针设置原则是: // 1)查看father->failNode下有没有和自己一样的子节点,有则fail指针取该子节点 // 2)否则,沿father->failNode->failNode继续查询下,如果一直没有,fail指针就取根节点 nextNode := node.failNode for { if nextNode == nil { node.childNode[ulj].failNode = GAcAuto break } else { if nextNode.childNode[ulj] != nil { node.childNode[ulj].failNode = nextNode.childNode[ulj] break } else { nextNode = nextNode.failNode } } } } } } } nodeList = nodeList[nodeListSize:] } } func AcAutoMatch(input string) bool { node := GAcAuto for _, runeCh := range input { count := 0 runeStr := string(runeCh) for uli := 0; uli < len(runeStr); uli++ { for ulj := 0; ulj < 2; ulj++ { index := runeStr[uli] / childNodeCount if ulj != 0 { index = runeStr[uli] % childNodeCount } Match: if node != nil && node.childNode[index] != nil { // 找到即退出,没有结束继续查找 count++ if node.childNode[index].endCount > 0 && count == 2*len(runeStr) { return true } else { node = node.childNode[index] } } else { if node == nil { // 当前字符一直查不到,则换下个字符,故重置node,取值根节点 node = GAcAuto goto runeChOver // DONE,快速退出当前字符、换下个字符 } else { // 当前节点没有目标字符,则去下个节点看下,即查看fail指针 node = node.failNode goto Match } } } } runeChOver: } return false } var minGan = make([]string, 0, 10000) func main() { // 建树 BuildTree([]string{"ba", "real", "中国"}) // 设置fail指针 SetNodeFailPoint() // 查找 fmt.Println(AcAutoMatch("ea")) fmt.Println(AcAutoMatch("real")) fmt.Println(AcAutoMatch("eal中国")) fmt.Println(AcAutoMatch("reaL")) } ```
  • 国庆期间又看了协议文档、视频资料;之前理解有些模糊的地方,已经梳理清楚了,网站支持编辑就好了,发布两天后都无法编辑了
  • 多谢支持,我这边也是跟着项目来的,后面会先整理一篇倒排的文章;由于etcd在项目中应用的还不是太多,现在只能抽时间学习,推荐《etcd技术内幕》可以看下
  • 补充: 在使用ETCD进行服务注册、发现时,分服务端和客户端实现,服务端主要是进行注册处理,分为两个for循环,第一个for循环用于注册检测、检测IP是否注册了;第二for循环用于注册续约、用于注册IP的租约续约;客户端主要是做命名解析,借助GRPC的resolver,通过将etcd中存储的服务端IP列表传给resolver实现客户端对服务端访问,负载平衡策略也是在GRPC中指定、一般设置为轮询。
  • 嗯嗯,另外,发现写wiki时,语法规则还挺麻烦,虽然有个markdown的语法链接,但点击后都指向成人、赌博的网页,和之前不一样