보이어-무어(Boyer-Moore) 알고리즘이 정말 빠를까?
예전에, 알고리즘 책을 보다가 저도 보이어-무어 문자열 검색 코드를 봤었습니다. 뭔가... 책에 나와 있는 문자열 검색 알고리즘을 쓰면 멋있을 것 같아서 코드를 그대로 짜 넣었고 뿌듯해 했던 기억이 납니다.
문제는... 얼마나 성능향상이 있을까 기대하는 마음으로 C 언어의 단순 문자열 검색 함수(strstr)와 비교하고 나서... 충격을 먹었습니다. ^^;
성능이 더 안 좋았던 것입니다. 그 책에 나와 있던 모든 '문자열 검색 알고리즘'들이 하나같이 strstr 함수와의 성능 테스트에서 무너져버렸습니다. 그 이후로 제 기억속에서 문자열 알고리즘은 곧 strstr이 되어 버렸습니다. (기억이 가물가물한데... 그 당시 "라빈-카프", "KMP" 알고리즘도 마찬가지 결과였습니다.)
그러는 와중에, 최근에 트위터에서 다음의 글을 보게 되었습니다.
링크의 글을 읽어 보니,
문자열 검색 개발
; http://likejazz.com/post/90399631505
예전에 보았던 그 "보이어-무어" 검색 알고리즘 이야기가 나왔습니다. 게다가 논문에 가장 가까운 구현 코드를 구현했다고 하는데요. 음... 그래서 순간 호기심이 일었습니다. 혹시나 제가 예전에 봤던 그 책의 "보이어-무어" 검색은 잘못 작성된 예가 아니었을까??? 하는... 머리좋은 사람들이 만들었다는 알고리즘에 대한 일말의 기대가 다시 부활한 것입니다. 그래서 위의 블로거가 작성한 github 소스 코드를 입력하고 역시 이번에도 strstr과의 성능 비교를 해보았습니다.
boyer-moore-string-search
; https://github.com/likejazz/boyer-moore-string-search/blob/master/boyer-moore.c
test 함수는 boyer_moore 알고리즘을 사용한 것이고, test2는 C 언어의 런타임 함수인 strstr을 쓴 것입니다.
void test(uint8_t *string, uint8_t *pat)
{
int len_org = strlen((const char *)string);
int len_searchWord = strlen((const char *)pat);
__int64 TicksPerSec;
GetQPF(&TicksPerSec);
__int64 StartTick = GetQPCTick();
uint32_t pos = boyer_moore(string, len_org, pat, len_searchWord);
__int64 EndTick = GetQPCTick();
__int64 elapsed = EndTick - StartTick;
printf("boyer_moore (%I64d)\n", elapsed);
}
void test2(char *string, char *pat)
{
__int64 TicksPerSec;
GetQPF(&TicksPerSec);
__int64 StartTick = GetQPCTick();
char *pos = strstr(string, pat);
__int64 EndTick = GetQPCTick();
__int64 elapsed = EndTick - StartTick;
printf("strstr (%I64d)\n", elapsed);
}
성능 측정은 가장 정확도가 높다는 윈도우의 QueryPerformanceCount / QueryPerformanceFrequency 셋을 사용했습니다.
QueryPerformanceCount / QueryPerformanceFrequency
; http://sweeper.egloos.com/viewer/2820035
bool GetQPF(__int64* QPFTicksPerSec)
{
LARGE_INTEGER li;
if (QueryPerformanceFrequency(&li) == false)
{
return false;
}
*QPFTicksPerSec = static_cast<__int64>(li.QuadPart);
return true;
}
__int64 GetQPCTick(void)
{
LARGE_INTEGER li;
QueryPerformanceCounter(&li);
return static_cast<__int64>(li.QuadPart);
}
그리고 52KB의 문자열을 준비하고 발견되지 않는 문자열로 10번씩 테스트 해보았습니다.
for (int i = 0; i < 10; i ++)
{
test((uint8_t *)full.c_str(), (uint8_t *)"adbda");
}
printf("\n");
for (int i = 0; i < 10; i++)
{
test2((char *)full.c_str(), "adbda");
}
결과는 strstr의 압승입니다.
// x86/Release 빌드
// (낮을 수록 빠릅니다.)
// boyer_moore 검색 시간
boyer_moore (1253)
boyer_moore (827)
boyer_moore (821)
boyer_moore (1000)
boyer_moore (819)
boyer_moore (931)
boyer_moore (820)
boyer_moore (820)
boyer_moore (827)
boyer_moore (887)
// strstr 검색 시간
strstr (86)
strstr (81)
strstr (82)
strstr (80)
strstr (80)
strstr (81)
strstr (81)
strstr (80)
strstr (80)
strstr (95)
혹시나 싶어, 1/3 지점 앞 부분에 나오는 약간 긴 텍스트로 검색해 보았습니다.
for (int i = 0; i < 10; i++)
{
test((uint8_t *)full.c_str(), (uint8_t *)"85e39934c9c3c6ab5cd2f0e607adff92T");
}
printf("\n");
for (int i = 0; i < 10; i++)
{
test2((char *)full.c_str(), "85e39934c9c3c6ab5cd2f0e607adff92T");
}
// boyer_moore 검색 시간
boyer_moore (36)
boyer_moore (31)
boyer_moore (62)
boyer_moore (81)
boyer_moore (33)
boyer_moore (31)
boyer_moore (30)
boyer_moore (29)
boyer_moore (29)
boyer_moore (29)
// strstr 검색 시간
strstr (10)
strstr (10)
strstr (10)
strstr (9)
strstr (12)
strstr (11)
strstr (10)
strstr (10)
strstr (10)
strstr (11)
이전보다 많은 차이는 아니지만 역시 strstr의 승입니다. 정말 혹시나 싶어 이번에는 뒤에서 1/3 지점에 나오는 짧은 텍스트로 검색을 해보았습니다.
for (int i = 0; i < 10; i++)
{
test((uint8_t *)full.c_str(), (uint8_t *)"dff92Q");
}
printf("\n");
for (int i = 0; i < 10; i++)
{
test2((char *)full.c_str(), "dff92T");
}
boyer_moore (518)
boyer_moore (464)
boyer_moore (557)
boyer_moore (510)
boyer_moore (675)
boyer_moore (734)
boyer_moore (520)
boyer_moore (496)
boyer_moore (501)
boyer_moore (483)
strstr (13)
strstr (11)
strstr (14)
strstr (12)
strstr (13)
strstr (13)
strstr (13)
strstr (12)
strstr (13)
strstr (13)
역시나 strstr의 압승입니다. 현란한 boyer_moore 알고리즘을 어떻게 strstr이 이겼는지 궁금하시나요? 다음은 Visual C++의 런타임 소스로 공개되어 있는 strstr의 코드입니다.
// C:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\crt\src\strstr.c
#include <cruntime.h>
#include <string.h>
char * __cdecl strstr (const char * str1, const char * str2)
{
char *cp = (char *) str1;
char *s1, *s2;
if ( !*str2 )
return((char *)str1);
while (*cp)
{
s1 = cp;
s2 = (char *) str2;
while ( *s1 && *s2 && !(*s1-*s2) )
s1++, s2++;
if (!*s2)
return(cp);
cp++;
}
return(NULL);
}
도대체 어떤 특수한 경우를 만들어 줘야 Boyer-Moore 알고리즘이 strstr을 이길 수 있을까요?
좀 더 자세한 Boyer-Moore 알고리즘 소개글 하나.
Boyer-Moore 스트링 매칭 알고리즘
; http://web.skhu.ac.kr/~mckim1/Lecture/DS/dna/class12/class12_05.html
참고로 검색해 보니 Boyer-Moore가 KMP보다 성능이 더 좋다고 하는 글도 보이는군요.
KMP, Boyer-Moore 성능 비교
; http://blog.naver.com/gskjhyoo/100198701888
(물론
이 글의 첨부 파일로 포함해 두었습니다.)
기타...
Using Trie Class for Efficient Text Pattern Searching in C#
; https://code-maze.com/csharp-using-trie-class-for-efficient-text-pattern-searching/
[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]