create an api router
一般来讲,很多API的前缀都是相同的, 如:
/api/v1/:who/moha
/api/v2/:who/+1s
包括现在看到的这篇,它的API是
/article/:id
所有的帖子都有共同的前缀 /article
,那么怎样快速的从众多API里面找到某一篇帖子呢?
trie (prefix tree)
顾名思义,就是根据前缀来快速查找文本的 一种典型的空间换时间的数据结构。实现也是非常简单。
class Trie
{
public:
struct Node
{
bool ok;
Node* children[26];
Node() : ok{false}, children{} {}
};
Trie() = default;
~Trie()
{
std::list<Node*> tmp;
for(auto c: root_.children)
{
if(c)
{
tmp.push_back(c);
}
}
while(!tmp.empty())
{
Node* c = tmp.front();
tmp.pop_front();
for(auto cc: c->children)
{
if(cc)
{
tmp.push_back(cc);
}
}
delete c;
}
}
void put(const std::string_view& s)
{
Node* p = &root_;
for(auto c: s)
{
if(!p->children[c - 'a'])
{
p->children[c - 'a'] = new Node{};
}
p = p->children[c - 'a'];
}
p->ok = true;
}
bool get(const std::string_view& s)
{
Node* p = find(s);
return p != &root_ && p->ok;
}
private:
Node root_;
Node* find(const std::string_view& s)
{
Node* p = & root_;
for(auto c: s)
{
if(p->children[c-'a'])
{
p = p->children[c-'a'];
}
}
return p;
}
};
看了上面的实现,我们很容易发现, 字母表children[26]
会占用大量的空间。那么,如何在不牺牲太多时间效率的情况下减少空间占用呢?
3way trie
我们可以在每个节点保存输入的第n个字符,然后判断n+1个字符与n个字符的大小关系。这样每个节点只需要保存3个下一级节点的指针就行了。如:
struct Node
{
bool word = false;
Node* left;
Node* mid;
Node* right;
char c;
};
这样实现起来类似binary search tree:
Node* put_impl(Node* n, std::string_view s, size_t d)
{
char c = s[d];
if(n == nullptr)
{
n = new Node{};
n->c = c;
}
if(c < n->c)
{
n->left = put_impl(n->left, s, d);
}
else if(c > n->c)
{
n->right = put_impl(n->right, s, d);
}
else if(d < s.size()-1)
{
n->mid = put_impl(n->mid, s, d+1);
}
else
{
n->word = true;
}
return n;
}
查找的时候也是同样的思路,代码就不贴了。
看了上面的实现,我们很容易发现,虽然children从26减少到了3但是这个树的深度还是太大了,这样并不会节约多少个有用的节点。那么还有其他办法吗?
space-optimized trie (radix tree)
前面提到,优化空间的方法就是减小字符表的大小,前面的3way trie效果有限是因为仅在节点中保留1一个字符,如果我们先保留全部的字符,等到有相同前缀的字符串添加时在分到新的节点,这样不就减少树的深度了吗,沿着这个思路实现我们就可以得到一个radix tree了。
举个例子:
当添加 dog
时,这棵树长这样。
[dog]
接着添加 doges
,这时和已添加的dog
有共同的前缀dog
,但第一个词刚好就是这个前缀,直接把分割后的es
放到下一级即可。
[dog]
/
[es]
接着添加doll
,这时共同前缀变成了do
,那么需要将当前的节点拆分成两部分,一部分时共同的前缀do
,另一部分是剩下的g
放在下一级,同时把当前的下一级作为下下集,将要添加字符的剩余部分放到下一级即可。
[do]
/ \
[g] [ll]
/
[es]
以此类推 … …
和前面的3way trie对比很容易发现,同样添加dog
、doges
、doll
,3way trie长这样:
[d]
|
[o]
/
[g]
/ \
[e] [l]
\ |
[s] [l]
很明显radix tree比3way trie节约了近一半的节点。
下面贴一下节点类型与添加的实现
struct Node
{
bool word;
std::string path;
std::vector<Node*> children;
std::vector<char> indices;
Node(const std::string_view& s) : word{false}, path{s.data(), s.size()}, children{}, indices{} {}
};
void put_impl(Node* n, std::string_view path)
{
if(n->path.empty() && n->indices.empty())
{
n->word = true;
n->path = path;
return;
}
size_t i = common_prefix(n->path, path);
if(i < n->path.size())
{
Node* c = new Node{n->path.substr(i)};
c->children = n->children;
c->indices = n->indices;
c->word = true;
n->children.clear();
n->children.push_back(c);
n->indices.clear();
n->indices.push_back(n->path[i]);
n->path = n->path.substr(0, i);
n->word = false;
}
if(i < path.size())
{
path = path.substr(i);
for(size_t idx = 0; idx < n->indices.size(); ++idx)
{
if(n->indices[idx] == path[0])
{
n = n->children[idx];
put_impl(n, path);
return;
}
}
Node* c = new Node{path};
c->word = true;
n->children.push_back(c);
n->indices.push_back(path[0]);
}
}
当然,任何算法和数据结构都有一定的局限性。如果空间足够的话,单纯的判断前缀是否存在,当然还是trie最强了。
实现API路由
什么,你想用正则表达式?那可以不用看了。
拿这个blog的实现来说,它只支持3种类型:全匹配,全替换,k-v替换。比如:
# 登录
/api/login
# 静态资源
/static/*file
# 某个帖子
/article/:id
全替换的规则很简单,就是把*file
后面所有的字符都替换为实际的字符,如:
/static/css/article.css
这时*file
替换为css/article.css
。
k-v替换的规则稍微复杂一些,k-v可以有多个,直到遇到/
或末尾为止,如规则/api/:user/:id
,有url为
/user/elder/+1s
那么会得到键值对
{
"user": "elder",
"id": "+1s"
}
规则
为了方便下文解释,这里给一个对照表
name | value |
---|---|
全匹配 | static |
全替换 | wild |
k-v替换 | param |
下面是规则:
static
必须完全匹配,优先级最高
param
可以与static
重合 (/foo/
与/foo/:bar
可共存)wild
不能与static
重合 (/foo/
与/foo/*bar
不可共存)param
与wild
不可共存 (/foo/:bar
与/foo/*bar
)
举例
/foo
/foo/
=> ok
/foo
/foo/
/foo/:bar
=> ok
/foo
/foo/*bar
=> ok
/foo
/foo/
/foo/*bar
=> conflict with static
/foo
/foo/*bar
/foo/
=> conflict with wild
/foo/:bar
/foo/*bar
=> conflict with param
/foo/*bar
/foo/:bar
=> conflict with wild
/foo/*bar/baz
=> invalid, wild must in the end
/foo/bar*baz
=> invalid, * must after /
/foo/*bar
/foo/bar/*baz
=> invalid, wild will match to the end
/foo
/foo/
/foo/:name
/foo/:name/:age
=> ok
/foo
/foo/
/foo/:name
/foo/:name/*age
=> ok
/foo
/foo
/foo/:name
/foo/bar
/foo/bar/
=> /foo/bar and /foo/bar conflict with param