4 个版本
0.2.0 | 2023年9月25日 |
---|---|
0.1.2 | 2023年9月18日 |
0.1.1 | 2023年9月13日 |
0.1.0 | 2023年9月12日 |
在 文本处理 中排名 #975
26KB
460 行
trie_match! {}
此宏通过使用紧凑的双数组数据结构来比较字符串,从而加速Rust的match
表达式。
用法
只需将现有的match
表达式用以下宏trie_match! {}
包装即可
use trie_match::trie_match;
let x = "abd";
let result = trie_match! {
match x {
"a" => 0,
"abc" => 1,
pat @ ("abd" | "bcc") => pat.bytes()[0],
"bc" => 3,
_ => 4,
}
};
assert_eq!(result, 3);
为什么它更快?
在正常的match
表达式中,字符串会针对每个模式进行比较。这相当于以下代码
if x == "a" {
0
} else if x == "abc" {
1
} else if x == "abd" || x == "bcc" {
x.bytes()[0]
} else if x == "bc" {
3
} else {
4
}
上述代码要求每次从字符串的开始进行比较。上述代码的时间复杂度为O(mn),其中m是平均模式长度,n是模式数量。
相比之下,此宏构建以下trie结构以检索匹配分支的索引
此外,此实现使用紧凑的双数组数据结构以实现高效的状态间遍历,时间复杂度变为O(m)。
cfg
属性
仅在Nightly Rust中使用时,此宏支持带有cfg
属性的条件编译。要使用此功能,请在您的Cargo.toml
中启用features = ["cfg_attribute"]
。
示例
trie_match! {
match x {
#[cfg(feature = "foo")]
"a" => { .. }
#[cfg(feature = "bar")]
"b" => { .. }
_ => { .. }
}
}
局限性
以下与正常的match
表达式不同
- 仅支持字符串、字节字符串和u8切片作为模式。
- 通配符最后评估。(正常的
match
表达式不会匹配通配符之后的模式。) - 守卫不可用。
有时正常的match
表达式可能更快,具体取决于优化方式,因此最好根据您的速度实验进行选择。
基准测试
运行以下命令
cargo bench
实验结果如下 [μs]
-
带有Radeon图形的AMD Ryzen 7 5700U
基准名称 正常匹配 phf 库 trie-match 库 100个随机单词 1.94 2.02 1.09 HTML元素随机 2.32 2.43 0.55 -
第12代英特尔(R)酷睿(TM) i7-1270P
基准名称 正常匹配 phf 库 trie-match 库 100个随机单词 1.13 1.29 0.61 HTML元素随机 1.24 1.51 0.36
phf 库:使用完美哈希函数的编译时静态映射。
许可证
根据您选择许可以下之一:
- Apache许可证2.0版本(LICENSE-APACHE 或 https://apache.ac.cn/licenses/LICENSE-2.0)
- MIT许可证(LICENSE-MIT 或 http://opensource.org/licenses/MIT)
任选其一。
贡献
请参阅指南。
依赖项
~290–740KB
~18K SLoC