最有效的方式来比较短串小字典（解析）

我试图优化我的简单的C interpretter，我只是为了好玩做，我做解析这样的 - 首先，我分析文件到双向链表中的令牌，然后我做语法和语义分析。
我想优化此原型的功能：最有效的方式来比较短串小字典（解析）

bool parsed_keyword（struct token *，char dictionary [] []）;

里面的函数我基本上调用strcmp对所有关键字和编辑标记类型。这当然会导致对正在解析（几乎）每个字符串的20个strcmp调用。

我想拉宾，卡普将是最好的，但它听起来好像它是不是最适合这个工作（匹配对小字典一个字）。做这项工作最好的算法是什么？感谢您的任何建议。

来源

2012-07-09 AoeAoe

当涉及到“n = 20”时，优化应该是您最担心的问题。几乎任何顺序多项式函数都可以满足您的需求。 – corsiKa 2012-07-09 17:22:57

根据Niklaus Wirth的说法，当您在编译器/解释器中查找本地符号时，*是*最有效的方法。他甚至做了测试以确保。（当然，他的指标可能与你的指标不同，但是他的指标是非常好的指标。） – 2012-07-09 17:25:44

散列表可能是我对这个特定问题的选择。它将提供O(1)查找您的大小的表格。尽管如此，特里也是一个不错的选择。

但是，为了实现将是把你的话在按字母顺序排列，然后用bsearch C库中最简单的。它应该几乎与散列或特里一样快，因为你只处理30个单词。它实际上可能会比散列表更快，因为您不必计算散列值。

Steve Jessop的想法是一个很好的想法，用相同大小的char数组来排列字符串。

const char keywords[][MAX_KEYWORD_LEN+1] = { 
"auto", "break", "case", /* ... */, "while" 
}; 

#define NUM_KEYWORDS sizeof(keywords)/sizeof(keywords[0]) 

int keyword_cmp (const void *a, const void *b) { 
    return strcmp(a, b); 
} 

const char *kw = bsearch(word, keywords, NUM_KEYWORDS, sizeof(keywords[0]), 
         keyword_cmp); 

int kw_index = (kw ? (const char (*)[MAX_KEYWORD_LEN+1])kw - keywords : -1);

如果你不已经拥有了它，你应该考虑收购的Compilers: Principles, Techniques, and Tools副本。由于它的封面，它通常被称为龙书。

来源

2012-07-09 17:18:22 jxh

如果将所有单词用nul个字节填充到最长的单词的长度，那么二分法搜索变得特别简单，因为您可以将字符串首尾相连 - 没有第二种间接方式。由于它们是关键字，因此列表不会经常更改。 – 2012-07-09 17:29:55

@SteveJessop：我将你的实现建议添加到答案中，问候 – jxh 2012-07-09 17:56:52

无关紧要，但是对于comp sci书（恐龙os书，更不用说所有的o'reilly动物书）的所有荒谬封面，编译器书最酷覆盖永远。 – nook 2012-07-09 17:58:19

如果你正在寻找的效率我会说，拉宾卡普是不是你最好的选择，和你最好的效率将与博耶，摩尔发现，但它更是一个公平一点难以实现。

如果你是为了好玩而做这件事，说实话，我不认为有必要优化，因为这些调用应该在相当短的时间内运行，并且你并不需要它以工业速度运行。

如果您正在寻找使用字符串匹配算法，这是一个很酷且有用的目标，我建议您查看KMP算法和Boyer-Moore算法，这两种算法在实现过程中都会教你很多。

当然还有其他更直接的方法，比如字典查找和简单的二分查找等等，但那些并不真正优化你处理字符串和字符串比较是一个非常有趣的领域，你会在某个时候不可避免地遇到。

来源

2012-07-09 17:21:54

Nah，boyer moore在这个特定情况下非常无效（与多于一个词相匹配），可能与天真匹配算法一样低效。是的，我只是为了好玩，否则我可能根本不在乎。 – AoeAoe 2012-07-09 19:27:38

，想到时做的查找是只使用键盘的排序阵列，并对其做一个二进制搜索的第一件事。

来源

2012-07-09 17:24:11

如果关键字的集合是固定的，你可以使用gperf使用理想哈希，例如。这只需要不断的工作和单个字符串比较，因此可能比其他方法更快。

来源

2012-07-09 20:36:41

假设您的关键字没有改变，这听起来像是perfect hash function的正确情况。完美的散列函数将输入映射到整数（如常规散列函数），但没有冲突。

Wikipedia有几个完美的哈希生成器的链接，包括GNU gperf。

来源

2012-07-09 21:01:03 mike

最有效的方式来比较短串小字典（解析）

回答

相关问题