84669 人学习
152542 人学习
20005 人学习
5487 人学习
7821 人学习
359900 人学习
3350 人学习
180660 人学习
48569 人学习
18603 人学习
40936 人学习
1549 人学习
1183 人学习
32909 人学习
如果路由都只是 url 字符串完全匹配的,我可以用 hashmap ,理想情况 O(1) 复杂度。但是我想在 url 匹配中支持 通配符,那么最简单的实现方法,我就直接用正则了,但是匹配复杂度就变成 O(n)了,这样感觉不是很好。。。
如何解决这个问题
认证高级PHP讲师
为什么不用树来存路由的地址呢?如图,每一个方框都是一个 Map当你请求 /user/111/profile/books/222的时候先将 url 打散['/' , '111' , 'profile' , 'books' , '222']先搜索第一层有没有一个 / 节点然后搜索第二层有没有一个 111 节点 ,没有的话进入 * 节点然后所搜第三层有没有一个 profile 节点以此类推
https://github/bephp/router
这个项目没有使用正则,而是将URL按照"/"切割然后保存成为树形结构。
映射路由的时候,相当于对树进行遍历,复杂度为 O (log n)。
项目是PHP实现的,不过代码很少。应该很容易看明白的。
为什么不能维护一个路由Dict。值是key对应的func
正则在路由这块展示的灵活性是其他技术很难替代的。一样用正则,也可以把性能优化,原理很简单,合并正则,通过某种策略来依据正则匹配的结果来判断哪个
比如有
/user/{pid}/profile
/news
/product/{pid}
/product/{pid}/comment/{cid}
四个路由
用一个正则 #^(?|/user/(d+)/profile|/news|/product/(d+)()|/product/(d+)/comment/(d+)())$# 匹配#^(?|/user/(d+)/profile|/news|/product/(d+)()|/product/(d+)/comment/(d+)())$# 匹配
#^(?|/user/(d+)/profile|/news|/product/(d+)()|/product/(d+)/comment/(d+)())$#
当捕获结果分别有 1,0,2,3个组的时候,我们就知道分别匹配到了第1~4个路由。通过一些代码自动合并正则、分配捕获组数量=>路由的映射,就可以把多个正则合并到一起一次匹配
这里有个技巧是用(?|)
(?|)
为什么不用树来存路由的地址呢?
如图,每一个方框都是一个 Map
当你请求 /user/111/profile/books/222的时候先将 url 打散
['/' , '111' , 'profile' , 'books' , '222']
先搜索第一层有没有一个 / 节点
然后搜索第二层有没有一个 111 节点 ,没有的话进入 * 节点
然后所搜第三层有没有一个 profile 节点
以此类推
https://github/bephp/router
这个项目没有使用正则,而是将URL按照"/"切割然后保存成为树形结构。
映射路由的时候,相当于对树进行遍历,复杂度为 O (log n)。
项目是PHP实现的,不过代码很少。应该很容易看明白的。
为什么不能维护一个路由Dict。值是key对应的func
正则在路由这块展示的灵活性是其他技术很难替代的。一样用正则,也可以把性能优化,原理很简单,合并正则,通过某种策略来依据正则匹配的结果来判断哪个
比如有
/user/{pid}/profile
/news
/product/{pid}
/product/{pid}/comment/{cid}
四个路由
用一个正则
#^(?|/user/(d+)/profile|/news|/product/(d+)()|/product/(d+)/comment/(d+)())$#
匹配#^(?|/user/(d+)/profile|/news|/product/(d+)()|/product/(d+)/comment/(d+)())$#
匹配当捕获结果分别有 1,0,2,3个组的时候,我们就知道分别匹配到了第1~4个路由。通过一些代码自动合并正则、分配捕获组数量=>路由的映射,就可以把多个正则合并到一起一次匹配
这里有个技巧是用
当捕获结果分别有 1,0,2,3个组的时候,我们就知道分别匹配到了第1~4个路由。通过一些代码自动合并正则、分配捕获组数量=>路由的映射,就可以把多个正则合并到一起一次匹配(?|)
(?|)
来重置捕获组🎜 🎜参考 http://nikic.github.io/2014/0...🎜