0

我正在尝试为我正在从事的项目学习 ragel。我是新来的。

我有一个 15 个字符串的列表。问题是检查给定的字符串是否与这 15 个字符串中的任何一个匹配。

在正常情况下，用 15 个字符串构建一个哈希集就足以对字符串进行 O(1) 查找并判断它是否匹配。

就我而言，我将这样做十亿次。所以我正在尝试使用 ragel 为这 15 个字符串构建一个状态机，并检查给定的字符串是否匹配。

我觉得使用 ragel 方法更好，因为在这两种情况下，我都必须一个一个地浏览角色。即，为了计算哈希值，我们需要扫描所有字符一次，然后进行查找。使用状态机扫描所有字符一次会给出结果并避免进行查找。

这是更好的方法吗？任何人都可以告诉我如何为 15 个字符串构建状态机来进行字符串匹配吗？

4

1 回答 1

0

在某些架构上，通过适当的对齐，手动编码*(int64_t*) "8 bytes" == *(int64_t*) a_c_string比较效果最好，因为它使用单个 CPU 指令来比较 7-8 个字节。

Ragel 没有最终的哈希表查找，但它有更多的分支，所以它会更快还是更慢 - 这取决于。我邀请您尝试一个完美的哈希（类似于gperf）、一个快速的通用哈希（dense_hash_map）和 Ragel 并分享结果。

以下是 Ragel 中的查找表示例：

// ragel -G2 -o table_ragel.cc table.cc
int table (const char* cstring, int len) {
  char *p = (char*) cstring, *pe = p + len; int cs; %%{ machine table;
    main := ('foo' % {return 1;} | 'bar' % {return 2;});
    write data; write init; write exec; }%%
  return 0;
}
int main() {
  printf ("id: %i\n", table ("foo", 3));  // Prints 1.
  printf ("id: %i\n", table ("bar", 3));  // Prints 2.
  printf ("id: %i\n", table ("", 0));  // Prints 0.
  return 0;
}
于 2013-10-20T14:52:26.083 回答