J & J - 정성태의 닷넷 이야기

사용자

메뉴

최근 덧글

[tree soap] 아차! f는 기억이 나는데, m은 ㅜㅜ 감사합니다!!! ^...[정성태] 'm'은 decimal 타입의 숫자에 붙는 접미사입니다. ...[정성태] https://lxr.sourceforge.io/ http...[정성태] VT sequences to "CONOUT$" vs. STD_O...[정성태] NetCoreDbg is a managed code debugg...[정성태] Evaluating tail call elimination in...[정성태] What’s new in System.Text.Json in ....[정성태] What's new in .NET 9: Cryptography ...[정성태] 아... 제시해 주신 "https://akrzemi1.wordp...[정성태] 다시 질문을 정리할 필요가 있을 것 같습니다. 제가 본문에...

글쓰기

제목

이름

암호

전자우편

HTML

홈페이지

유형

내용

<div style='display: inline'>
<h1 style='font-family: Malgun Gothic, Consolas; font-size: 20pt; color: #006699; text-align: center; font-weight: bold'>보이어-무어(Boyer-Moore) 알고리즘이 정말 빠를까?</h1>

예전에, 알고리즘 책을 보다가 저도 보이어-무어 문자열 검색 코드를 봤었습니다. 뭔가... 책에 나와 있는 문자열 검색 알고리즘을 쓰면 멋있을 것 같아서 코드를 그대로 짜 넣었고 뿌듯해 했던 기억이 납니다. 
 
문제는... 얼마나 성능향상이 있을까 기대하는 마음으로 C 언어의 단순 문자열 검색 함수(strstr)와 비교하고 나서... 충격을 먹었습니다. ^^; 
 
성능이 더 안 좋았던 것입니다. 그 책에 나와 있던 모든 '문자열 검색 알고리즘'들이 하나같이 strstr 함수와의 성능 테스트에서 무너져버렸습니다. 그 이후로 제 기억속에서 문자열 알고리즘은 곧 strstr이 되어 버렸습니다. (기억이 가물가물한데... 그 당시 "라빈-카프", "KMP" 알고리즘도 마찬가지 결과였습니다.) 
 
그러는 와중에, 최근에 트위터에서 다음의 글을 보게 되었습니다. 
 
<div style='BACKGROUND-COLOR: #ccffcc; padding: 10px 10px 5px 10px; MARGIN: 0px 10px 10px 10px; FONT-FAMILY: Malgun Gothic, Consolas, Verdana; COLOR: #005555'>
문자열 검색 개발 - 그러니까 검색엔진을 만든 직후였다. 한참동안 검색 기능을 테스트 하다가 우연히 데이타 파일을 직접 grep 해봤는데, 이럴수가. 내가 만든 엔진보다 grep이 더 빨랐다.... <a target='tab' href='http://tmblr.co/Zx6_Wy1KCFEYH'>http://tmblr.co/Zx6_Wy1KCFEYH</a> 
</div> 
 
링크의 글을 읽어 보니, 
 
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
문자열 검색 개발
; <a target='tab' href='http://likejazz.com/post/90399631505'>http://likejazz.com/post/90399631505</a>
</pre>
 
예전에 보았던 그 "보이어-무어" 검색 알고리즘 이야기가 나왔습니다. 게다가 논문에 가장 가까운 구현 코드를 구현했다고 하는데요. 음... 그래서 순간 호기심이 일었습니다. 혹시나 제가 예전에 봤던 그 책의 "보이어-무어" 검색은 잘못 작성된 예가 아니었을까??? 하는... 머리좋은 사람들이 만들었다는 알고리즘에 대한 일말의 기대가 다시 부활한 것입니다. 그래서 위의 블로거가 작성한 github 소스 코드를 입력하고 역시 이번에도 strstr과의 성능 비교를 해보았습니다. 
 
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
boyer-moore-string-search 
; <a target='tab' href='https://github.com/likejazz/boyer-moore-string-search/blob/master/boyer-moore.c'>https://github.com/likejazz/boyer-moore-string-search/blob/master/boyer-moore.c</a>
</pre>
 
test 함수는 boyer_moore 알고리즘을 사용한 것이고, test2는 C 언어의 런타임 함수인 strstr을 쓴 것입니다. 
 
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
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(&amp;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(&amp;TicksPerSec);

__int64 StartTick = GetQPCTick();

char *pos = strstr(string, pat);

__int64 EndTick = GetQPCTick();

__int64 elapsed = EndTick - StartTick;

printf("strstr (%I64d)\n", elapsed);
}
</pre>
 
성능 측정은 가장 정확도가 높다는 윈도우의 QueryPerformanceCount / QueryPerformanceFrequency 셋을 사용했습니다. 
 
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
QueryPerformanceCount / QueryPerformanceFrequency
; <a target='tab' href='http://sweeper.egloos.com/viewer/2820035'>http://sweeper.egloos.com/viewer/2820035</a>
</pre>
 
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
bool GetQPF(__int64* QPFTicksPerSec)
{
 LARGE_INTEGER li;

if (QueryPerformanceFrequency(&amp;li) == false)
    {
        return false;
    }

*QPFTicksPerSec = static_cast&lt;__int64&gt;(li.QuadPart);

return true;
}

__int64 GetQPCTick(void)
{
    LARGE_INTEGER li;

QueryPerformanceCounter(&amp;li);

return static_cast&lt;__int64&gt;(li.QuadPart);
}
</pre>
 
그리고 52KB의 문자열을 준비하고 발견되지 않는 문자열로 10번씩 테스트 해보았습니다. 
 
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
for (int i = 0; i &lt; 10; i ++)
{
 test((uint8_t *)full.c_str(), (uint8_t *)"adbda");
}

printf("\n");

for (int i = 0; i &lt; 10; i++)
{
 test2((char *)full.c_str(), "adbda");
}
</pre>
 
결과는 strstr의 압승입니다. 
 
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
// 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)
</pre>
 
혹시나 싶어, 1/3 지점 앞 부분에 나오는 약간 긴 텍스트로 검색해 보았습니다. 
 
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
for (int i = 0; i &lt; 10; i++)
{
 test((uint8_t *)full.c_str(), (uint8_t *)"85e39934c9c3c6ab5cd2f0e607adff92T");
}
printf("\n");
for (int i = 0; i &lt; 10; i++)
{
 test2((char *)full.c_str(), "85e39934c9c3c6ab5cd2f0e607adff92T");
}
</pre>
 
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
// 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)
</pre>
 
이전보다 많은 차이는 아니지만 역시 strstr의 승입니다. 정말 혹시나 싶어 이번에는 뒤에서 1/3 지점에 나오는 짧은 텍스트로 검색을 해보았습니다. 
 
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
for (int i = 0; i &lt; 10; i++)
{
 test((uint8_t *)full.c_str(), (uint8_t *)"dff92Q");
}
printf("\n");
for (int i = 0; i &lt; 10; i++)
{
 test2((char *)full.c_str(), "dff92T");
}
</pre>
 
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
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)
</pre>
 
역시나 strstr의 압승입니다. 현란한 boyer_moore 알고리즘을 어떻게 strstr이 이겼는지 궁금하시나요? 다음은 Visual C++의 런타임 소스로 공개되어 있는 strstr의 코드입니다. 
 
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
// C:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\crt\src\strstr.c

#include &lt;cruntime.h&gt;
#include &lt;string.h&gt;

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 &amp;&amp; *s2 &amp;&amp; !(*s1-*s2) )
                s1++, s2++;

if (!*s2)
                return(cp);

cp++;
    }

return(NULL);
}
</pre>
 
도대체 어떤 특수한 경우를 만들어 줘야 Boyer-Moore 알고리즘이 strstr을 이길 수 있을까요? 
 
좀 더 자세한 Boyer-Moore 알고리즘 소개글 하나. 
 
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
Boyer-Moore 스트링 매칭 알고리즘 
; <a target='tab' href='http://web.skhu.ac.kr/~mckim1/Lecture/DS/dna/class12/class12_05.html'>http://web.skhu.ac.kr/~mckim1/Lecture/DS/dna/class12/class12_05.html</a>
</pre>
 
참고로 검색해 보니 Boyer-Moore가 KMP보다 성능이 더 좋다고 하는 글도 보이는군요. 
 
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
KMP, Boyer-Moore 성능 비교
; <a target='tab' href='http://blog.naver.com/gskjhyoo/100198701888'>http://blog.naver.com/gskjhyoo/100198701888</a>
</pre>
 
(물론 <a target='tab' href='http://www.sysnet.pe.kr/bbs/DownloadAttachment.aspx?fid=857&amp;boardid=331301885'>이 글의 첨부 파일로 포함</a>해 두었습니다.) 
 
 
<hr style='width: 50%' /> 
 
기타... 
 
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
Using Trie Class for Efficient Text Pattern Searching in C#
; <a target='tab' href='https://code-maze.com/csharp-using-trie-class-for-efficient-text-pattern-searching/'>https://code-maze.com/csharp-using-trie-class-for-efficient-text-pattern-searching/</a>
</pre>

<hr />[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]
</div>

첨부파일

스팸 방지용 인증 번호

1393 (왼쪽의 숫자를 입력해야 합니다.)