#match #double-array #text #macro #data-structures #no-alloc

无std trie-match

快速匹配宏

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

MIT/Apache

26KB
460

trie_match! {}

Crates.io Documentation Rust Build Status Slack

此宏通过使用紧凑的双数组数据结构来比较字符串,从而加速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结构以检索匹配分支的索引

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 库:使用完美哈希函数的编译时静态映射。

许可证

根据您选择许可以下之一:

任选其一。

贡献

请参阅指南

依赖项

~290–740KB
~18K SLoC