Ragel string matching

Question

Я пытаюсь изучить ragel для проекта, над которым я работаю. Я новичок в этом.

У меня есть список из 15 строк. Проблема состоит в том, чтобы проверить, соответствует ли данная строка любой из этих 15 строк.

При нормальных обстоятельствах создание хэш-набора с 15 строками достаточно, чтобы выполнить O (1) поиск строки и указать, соответствует ли она или нет.

В моем случае я буду делать это миллиард раз. Поэтому я пытаюсь создать машину состояний для этих 15 строк с использованием ragel и проверить, соответствует ли данная строка.

Я чувствую, что подход с использованием ragel лучше, так как в обоих случаях мне придется проходить через символы один за другим. Чтобы вычислить хеш, нам нужно просканировать все символы один раз и затем посмотреть вверх. Где, как использование государственных машин, сканирующих все символы, дает результат и позволяет выполнять поиск.

Это лучший подход? И может ли кто-нибудь указать мне, как построить государственные машины для 15 строк, чтобы выполнить сопоставление строк?

Answer 1

На некоторых архитектурах, с надлежащим выравниванием, сравнение с ручной кодировкой *(int64_t*) "8 bytes" == *(int64_t*) a_c_string работает лучше всего, потому что для сравнения 7-8 байтов используется одна команда CPU.

У Ragel нет этого финального поиска в хэш-таблице, но у него есть больше branches, поэтому будет ли он быстрее или медленнее - это зависит. Я предлагаю вам попробовать идеальный хеш (что-то вроде gperf), быстрый хэш общего назначения (dense_hash_map) и 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; 
}