ACM 高手可以自动略过了.
大家好, 我是不知名框架`uRouter`的作者, 前 ACM 铜牌选手, 今天给大家分享一个动态路由匹配算法.
没看过gin
这部分源码, 但自己实现一个也不难. 核心是一个字典树的变种, 称之为树形Map
或许更为贴切.
package main
import "strings"
const (
defaultSeparator = "/" // 默认路径分隔符
defaultVarPrefix = ':' // 默认变量前缀
)
type (
apiHandler struct {
VPath string // API 路径
Funcs []func() // 处理函数
}
routeTree struct {
Value *apiHandler // 值
Children map[string]*routeTree // 子节点
}
)
func newRouteTree() *routeTree { return new(routeTree) }
// 判断字符串是否为变量
func isVar(s string) bool { return len(s) > 0 && s[0] == defaultVarPrefix }
// 分割字符串; 在原数组的基础上游走, 减少内存分配次数
func split(s string, sep string) []string {
var j = 0
var list = strings.Split(s, sep)
for i, v := range list {
if v != "" {
list[j] = list[i]
j++
}
}
return list[:j]
}
// Set 注册接口
func (c *routeTree) Set(vpath string, funcs []func()) {
var handler = &apiHandler{VPath: vpath, Funcs: funcs}
var list = split(handler.VPath, defaultSeparator)
if len(list) == 0 {
return
}
c.doSet(c, 0, list, handler)
}
func (c *routeTree) doSet(node *routeTree, index int, list []string, handler *apiHandler) {
var segment = list[index]
if isVar(segment) {
segment = "*"
}
var next = node.Children[segment]
if node.Children == nil {
node.Children = make(map[string]*routeTree)
}
if node.Children[segment] == nil {
next = &routeTree{}
node.Children[segment] = next
}
if index+1 == len(list) {
next.Value = handler
} else {
c.doSet(next, index+1, list, handler)
}
}
// Get 查找接口
func (c *routeTree) Get(path string) (*apiHandler, bool) {
var list = split(path, defaultSeparator)
if len(list) == 0 {
return nil, false
}
return c.doGet(c, 0, list)
}
func (c *routeTree) doGet(node *routeTree, index int, list []string) (*apiHandler, bool) {
if index == len(list) {
return node.Value, true
}
var segment = list[index]
if v, ok := node.Children[segment]; ok {
return c.doGet(v, index+1, list)
}
if v, ok := node.Children["*"]; ok {
return c.doGet(v, index+1, list)
}
return nil, false
}
本测试共注册 1024 个接口, 每个接口分为 4 段.
goos: darwin
goarch: arm64
pkg: github.com/lxzan/uRouter
BenchmarkRouteTree_Get-8 6707703 168.2 ns/op 80 B/op 1 allocs/op
PASS
ok github.com/lxzan/uRouter 1.433s
1
Nazz OP 不好意思说错了,是黑铁选手,距离黄铜还差一个气球🐸
|
2
codehz 2023-02-08 09:00:02 +08:00
gin 的实现思路大体上差不多,但是
第一不是简单的分割 /,而是会在插入 route 的时候去寻找最长前缀 第二也不是用 map 而是单纯的弄了一个 children 数组去匹配 其实挺符合现实使用场景的,因为一个目录下的分支通常没那么多( |
5
cqcsdzmt 2023-02-08 10:55:41 +08:00 1
一个不愿透露姓名的网友表示很赞
|
6
ericls 2023-02-08 10:58:38 +08:00
为啥非要给解决方案一个名字 解决方案的名字就应该叫: 「针对 XXX 问题的一种解决方案」
|
7
Nazz OP @ericls 实事求是突出主题. 总不能这样起标题吧: 震惊! 比 gin 快一倍的动态路由解析算法 (乱说的, 没测试过)
|
9
ericls 2023-02-08 11:41:23 +08:00 via iPhone 1
@Nazz 不是不是 我觉得这个标题很好 我就是说 总体上 那些 XXX tree 啊 xxx Map 啊 这种。
|
10
ClarkAbe 2023-02-08 11:54:07 +08:00 1
那你的 Benchmark 代码测试了一下我自己的新 router tux...
https://imgur.com/a/ZHM1oFI 我的路由结构是空间换时间以及利用数组不会 GC 的特性 ```golang type Tree struct { father *Tree // 父路由节点 children [255]*Tree // 子路由节点 part []uint8 // 路径参数 (例如: :name *name) method *Method // 路由方法 (methodTyp 类型) } ``` ```txt Running tool: /usr/bin/go test -benchmem -run=^$ -bench ^BenchmarkRouteTree_Get$ tux goos: linux goarch: amd64 pkg: tux cpu: AMD Ryzen 7 5800H with Radeon Graphics BenchmarkRouteTree_Get-16 122476156 9.885 ns/op 0 B/op 0 allocs/op PASS ok tux 2.232s ``` |
12
Nazz OP |
16
Nazz OP @ClarkAbe 还好吧,只在注册接口的时候创建一次 map, split 的 alloc 不可避免. 后续我测试下 sliceMap 怎么样,O(n)遍历数组
|
17
huang82 2023-02-08 12:16:30 +08:00
一个不愿透露姓名的网友表示很赞
|
18
hailaz 2023-02-08 12:51:20 +08:00
有个小小的疑惑,我想注册路径“/”,能成吗?
|
19
iOCZ 2023-02-08 13:31:57 +08:00
花了一点时间,能看懂 golang 了
|
21
ClarkAbe 2023-02-09 11:51:16 +08:00
@Nazz 用你的测试代码写了 Benchmark 并且对比测试了 https://github.com/ClarkQAQ/tux
|