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 -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; 
} 

: 여기

는 Ragel에 룩업 테이블의 예