trie_match! {}
This macro speeds up Rust's match expression for comparing strings by using a
compact double-array data structure.
Simply wrap the existing match expression with the trie_match! {} macro as
follows:
```rust use triematch::triematch;
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); ```
In a normal match expression, the string is compared for each pattern. It is
equivalent to the following code:
rust
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
}
The above code requires that string comparisons be made from the beginning of the string each time. The time complexity of the above code is O(mn), where m is the average pattern length, and n is the number of patterns.
In contrast, this macro builds the following trie structure to retrieve the index of the matched arm:
Furthermore, this implementation uses the compact double-array data structure to achieve efficient state-to-state traversal, and the time complexity becomes O(m).
cfg attributeOnly when using Nightly Rust, this macro supports conditional compilation with
the cfg attribute. To use this feature, enable features = ["cfg_attribute"]
in your Cargo.toml.
rust
trie_match! {
match x {
#[cfg(feature = "foo")]
"a" => { .. }
#[cfg(feature = "bar")]
"b" => { .. }
_ => { .. }
}
}
The followings are different from the normal match expression:
match expression does not
match patterns after the wildcard.)Sometimes the normal match expression is faster, depending on how
optimization is performed, so it is better to choose based on your speed
experiments.
Run the following command:
cargo bench
Experimental results are as follows [μs]:
AMD Ryzen 7 5700U with Radeon Graphics
| Bench name | Normal match | phf crate | trie-match crate | |----------------------|--------------|-------------|--------------------| | 100 words random | 1.94 | 2.02 | 1.09 | | HTML elements random | 2.32 | 2.43 | 0.55 |
12th Gen Intel(R) Core(TM) i7-1270P
| Bench name | Normal match | phf crate | trie-match crate | |----------------------|--------------|-------------|--------------------| | 100 words random | 1.13 | 1.29 | 0.61 | | HTML elements random | 1.24 | 1.51 | 0.36 |
phf crate: Compile time static maps using perfect hash functions.
Licensed under either of
at your option.
See the guidelines.