Ragel字符串匹配

Question

我正在为我正在做的一个项目尝试学习ragel。我对此还不熟悉。

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

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

在我的例子中，我将会这样做十亿次。因此，我尝试使用ragel为这15个字符串构建一个状态机，并检查给定的字符串是否匹配。

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

这是一种更好的方法吗？谁能告诉我如何为15个字符串构建状态机来进行字符串匹配？

Answer 1

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

Ragel没有最终的哈希表查找，但它有更多的branches，所以它是更快还是更慢-这要看情况。我邀请你尝试一个完美的散列(类似于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;
}