Ragel字符串匹配

Question

我正在努力學習ragel的一個項目，我正在努力。我是新來的。

我有一個15個字符串的列表。問題是要檢查給定的字符串是否與這15個字符串中的任何一個匹配。

在正常情況下，使用15個字符串構建散列集足以執行O（1）查找字符串並判斷它是否匹配。

在我的情況下，我會做這十億次。所以我試圖用ragel爲這15個字符串構建一個狀態機，並檢查給定的字符串是否匹配。

我覺得使用雷格爾方法更好，因爲在這兩種情況下，我將不得不一一瀏覽字符。即爲了計算散列，我們需要掃描所有字符一次，然後查找。在使用狀態機掃描所有字符時，會給出結果並避免查找。

這是一個更好的方法嗎？任何一個我可以指出如何建立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; 
}