dictionary - 检查给定单词是否存在于固定单词列表中的最快方法

Question

这可能不是 Rust 特有的，尽管它是我目前关注的语言。

我正在编写一个函数来将语言(MySQL)解析为标记并以格式化方式输出它们，其中一部分包括查找当前工作标记以查看它是名称、函数还是列/表名。

目前，我正在使用类似的匹配语句

pub fn is_word(word: &str) -> bool {
    match word {
        "accessible"
        | "account"
        | "action"
        | "active"
        | "add"
        // ...
        | "year"
        | "year_month"
        | "zerofill" => true,
        _ => false,
    }
}

actual list很长很长。

这是解决这个问题的最佳方法吗？我尝试过使用 HashMap 以及 .contains_key()，但速度明显较慢

---

我的HashMap implementation看起来像这样:

use std::collections::HashMap;

lazy_static! {
    static ref words: HashMap<&'static str, u8> = hashmap!{
        "accessible" => 0,
        "account" => 0,
        "action" => 0,
        "active" => 0,
        "add" => 0,
        // ...
        "year" => 0,
        "year_month" => 0,
        "zerofill" => 0,
    };
}

pub fn is_word(word: &str) -> bool {
    words.contains_key(word)
}

Answer 1

由于您的列表在编译时是固定的，因此使用 perfect hash ，例如 phf crate 提供的:

build.rs

extern crate phf_codegen;

use std::env;
use std::fs::File;
use std::io::{BufWriter, Write};
use std::path::Path;

fn main() {
    let path = Path::new(&env::var("OUT_DIR").unwrap()).join("codegen.rs");
    let mut file = BufWriter::new(File::create(&path).unwrap());

    write!(&mut file, "static KEYWORDS: phf::Set<&'static str> = ").unwrap();
    phf_codegen::Set::new()
        .entry("accessible")
        .entry("account")
        .entry("action")
        .entry("active")
        .entry("add")
        // ...
        .entry("year")
        .entry("year_month")
        .entry("zerofill")
        .build(&mut file)
        .unwrap();
    write!(&mut file, ";\n").unwrap();
}

src/main.rs

extern crate phf;

include!(concat!(env!("OUT_DIR"), "/codegen.rs"));

pub fn is_word(word: &str) -> bool {
    KEYWORDS.contains(word)
}

根据您提供的基准测试代码，这至少是一样快的。