检查字符串是否在静态编译时集中的最快方法是什么?

What's the fastest way to check if a string is in a static compile-time set?

提问人:Claudia 提问时间:11/10/2018 更新时间:11/10/2018 访问量:113

问:

我知道哈希代码通常是检查动态集的最快方法,但我想知道检查动态字符串是否在编译时已知的只读字符串集中的最快方法是什么。(我的意思是主要是绳子,而不是绳索或缺点绳子。{length: usize; chars: &[u8]}

目前,我通常会做这样的事情,但似乎它不是最优的:

// What I mean
let keywords = Set::new(["do", "if", "in", "for", "new", "try"]);
fun is_keyword(s: &str) { keywords.contains(s) }

// What I write
function is_keyword(s: &str) {
    match s.length() {
        2 -> s == "do" || s == "if" || s == "in",
        3 -> s == "for" || s == "new" || s == "try",
        // etc.
        _ -> false
    }
}

对于C样式字符串集,还有什么比从第二种变体中派生的东西更快的吗?还是尽可能快?

这与语言无关 - 我不在乎答案使用什么语言。我只是因为熟悉而使用 Rust。

字符串 算法 与语言无关

评论

0赞 user3386109 11/10/2018
最快的是编译时生成的 trie,它为 O(L) 时间,其中是您要查找的字符串的长度。L

答:

0赞 jahneff 11/10/2018 #1

就像你说的,似乎最快的方法是对字符串进行哈希处理。您当前的方式将花费 O(N) 时间来搜索集合中最大的字符串,或者根本不在集合中的字符串。

2赞 Matt Timmermans 11/10/2018 #2

对于静态集,可以使用完美哈希。这本质上是一个哈希表,但哈希函数保证集合中的每个字符串都哈希到表中的唯一索引。

要测试动态字符串,只需使用完美的哈希函数将其哈希到索引,然后查看该索引处的唯一字符串是否与测试字符串匹配。

谷歌搜索会发现许多不同的方法来进行完美的哈希处理。我最喜欢的一个描述如下:http://cmph.sourceforge.net/papers/chm92.pdf

它通常用于编译器中的关键字匹配,或在支持它的语言中实现字符串的开关/大小写。