Microsoft MVP성태의 닷넷 이야기
VC++: 78. 보이어-무어(Boyer-Moore) 알고리즘이 정말 빠를까? [링크 복사], [링크+제목 복사]
조회: 22176
글쓴 사람
정성태 (techsharer at outlook.com)
홈페이지
첨부 파일

보이어-무어(Boyer-Moore) 알고리즘이 정말 빠를까?

예전에, 알고리즘 책을 보다가 저도 보이어-무어 문자열 검색 코드를 봤었습니다. 뭔가... 책에 나와 있는 문자열 검색 알고리즘을 쓰면 멋있을 것 같아서 코드를 그대로 짜 넣었고 뿌듯해 했던 기억이 납니다.

문제는... 얼마나 성능향상이 있을까 기대하는 마음으로 C 언어의 단순 문자열 검색 함수(strstr)와 비교하고 나서... 충격을 먹었습니다. ^^;

성능이 더 안 좋았던 것입니다. 그 책에 나와 있던 모든 '문자열 검색 알고리즘'들이 하나같이 strstr 함수와의 성능 테스트에서 무너져버렸습니다. 그 이후로 제 기억속에서 문자열 알고리즘은 곧 strstr이 되어 버렸습니다. (기억이 가물가물한데... 그 당시 "라빈-카프", "KMP" 알고리즘도 마찬가지 결과였습니다.)

그러는 와중에, 최근에 트위터에서 다음의 글을 보게 되었습니다.

문자열 검색 개발 - 그러니까 검색엔진을 만든 직후였다. 한참동안 검색 기능을 테스트 하다가 우연히 데이타 파일을 직접 grep 해봤는데, 이럴수가. 내가 만든 엔진보다 grep이 더 빨랐다.... http://tmblr.co/Zx6_Wy1KCFEYH


링크의 글을 읽어 보니,

문자열 검색 개발
; 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

(물론 이 글의 첨부 파일로 포함해 두었습니다.)





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

[연관 글]


donaricano-btn



[최초 등록일: ]
[최종 수정일: 7/3/2014

Creative Commons License
이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.
by SeongTae Jeong, mailto:techsharer at outlook.com

비밀번호

댓글 쓴 사람
 



2014-09-29 02시39분
[꿈꾸는개발자] 안드로이드 어플리케이션 개발자입니다. 어플리케이션 내에서 검색기능 구현을 위하여, 알고리즘 공부 단계에 있습니다. 혹시 자바에서도 분석 해 보신적이 있으시나요?
[손님]
2014-09-29 10시18분
이 글의 결과에도 나오지만, 검색 문자열이 긴 경우에 (건너뛰기를 멀리할 수 있으니) boyer-moore 알고리즘은 효율적입니다. (하지만, 현실에서 사람들이 던지는 검색어가 긴 경우는 사실 많지 않지요.)

알고리즘이란 것이 프로그램 언어에 종속적인 경우는 거의 없지요. 자바에서도 유사한 결과가 나옵니다. 그래도 기왕에 말을 꺼내셨으니 ^^ "꿈꾸는개발자"님께서 한번 테스트 해보시고 결과를 공유해 주시면 어떨까요?
정성태
2015-01-14 12시22분
[체스맨] 고려가 필요한 부분이 두 가지 정도 있는데요.

첫째로 vc의 실제 strstr 함수는 저 코드가 아닙니다. asm 코드로 따로 들어있어요. 저 코드 긁어다 빌드해서 돌려보시면 BF에 memcmp 쓴 거 보다도 느리게 나올 겁니다.
CPU cache 이용을 극대화할 수 있도록 asm 코드가 작성된 걸로 압니다. 알고리즘이 빠르냐 느리냐만을 놓고 보면 정당한 비교가 될 수 없어요.

그리고, BM 구현된 거 얼핏 보아도, malloc 이 매번 호출되는데, 이건 성능에 지대한 영향을 미칠 수가 있으니, 미리 할당된 버퍼를 사용하도록 수정할 필요가 있구요.
최적화도 더 필요한 코드 같네요.
[손님]
2015-01-14 04시21분
좋은 의견 감사합니다. ^^ 덕분에 asm 코드로 따로 있는 것도 확인했습니다. 빠른 이유가 있었군요. ^^ 말씀하신 대로 C 코드만으로 테스트 했을 때는 BM 구현이 대체로 빨랐습니다.
정성태
2015-03-04 05시39분
[이상] 추측이지만 보이어 무어 알고리즘에 시스템 콜이 포함된 것 같군요.
[손님]
2015-03-04 10시09분
@이상 님, 위의 체스맨님 의견과 같이 어쨌든 공정한 테스트는 아니었던 것 같습니다. ^^ 참고로, 아래의 글도 약간 관련이 있는 글입니다.

무시할 수 없는 Visual C++ 런타임 함수 성능
; http://www.sysnet.pe.kr/2/0/1843
정성태

[1]  2  3  4  5  6  7  8  9  10  11  12  13  14  15  ...
NoWriterDateCnt.TitleFile(s)
12839정성태9/15/2021194.NET Framework: 1118. C# 10 - (17) 제네릭 타입의 특성 적용파일 다운로드1
12838정성태9/13/2021181.NET Framework: 1117. C# - Task에 전달한 Action, Func 유형에 따라 달라지는 async/await 비동기 처리 [2]파일 다운로드1
12837정성태9/11/2021100VC++: 151. Golang - fmt.Errorf, errors.Is, errors.As 설명
12836정성태9/10/202173Linux: 45. 리눅스 - 실행 중인 다른 프로그램의 출력을 확인하는 방법
12835정성태9/7/2021153.NET Framework: 1116. C# 10 - (16) CallerArgumentExpression 특성 추가파일 다운로드1
12834정성태9/7/202172오류 유형: 762. Visual Studio 2019 Build Tools - 'C:\Program' is not recognized as an internal or external command, operable program or batch file.
12833정성태9/6/2021102VC++: 150. Golang - TCP client/server echo 예제 코드파일 다운로드1
12832정성태9/6/202170VC++: 149. Golang - 인터페이스 포인터가 의미 있을까요?
12831정성태9/6/202189VC++: 148. Golang - 채널에 따른 다중 작업 처리파일 다운로드1
12830정성태9/6/202169오류 유형: 761. Internet Explorer에서 파일 다운로드 시 "Your current security settings do not allow this file to be downloaded." 오류
12829정성태9/5/2021181.NET Framework: 1115. C# 10 - (15) 구조체 타입에 기본 생성자 정의 가능파일 다운로드1
12828정성태9/4/2021175.NET Framework: 1114. C# 10 - (14) 단일 파일 내에 적용되는 namespace 선언파일 다운로드1
12827정성태9/4/202198스크립트: 27. 파이썬 - 웹 페이지 데이터 수집을 위한 scrapy Crawler 사용법 요약
12826정성태9/3/2021163.NET Framework: 1113. C# 10 - (13) 문자열 보간 성능 개선파일 다운로드1
12825정성태9/3/202154개발 환경 구성: 603. GoLand - WSL 환경과 연동
12824정성태9/2/2021130오류 유형: 760. 파이썬 tensorflow - Dst tensor is not initialized. 오류 메시지
12823정성태9/2/2021162스크립트: 26. 파이썬 - PyCharm을 이용한 fork 디버그 방법
12822정성태9/1/202188오류 유형: 759. 파이썬 tensorflow - ValueError: Shapes (...) and (...) are incompatible
12821정성태9/1/2021149.NET Framework: 1112. C# - .NET 6부터 공개된 ISpanFormattable 사용법
12820정성태9/1/202187VC++: 147. Golang - try/catch에 대응하는 panic/recover파일 다운로드1
12819정성태8/31/2021170.NET Framework: 1111. C# - FormattableString 타입
12818정성태8/31/2021103Windows: 198. 윈도우 - 작업 관리자에서 (tensorflow 등으로 인한) GPU 연산 부하 보는 방법
12817정성태8/31/202174스크립트: 25. 파이썬 - 윈도우 환경에서 directml을 이용한 tensorflow의 AMD GPU 사용 방법
12816정성태8/30/2021295스크립트: 24. 파이썬 - tensorflow 2.6 NVidia GPU 사용 방법 [2]
12815정성태8/30/2021192개발 환경 구성: 602. WSL 2 - docker-desktop-data, docker-desktop (%LOCALAPPDATA%\Docker\wsl\data\ext4.vhdx) 파일을 다른 디렉터리로 옮기는 방법
[1]  2  3  4  5  6  7  8  9  10  11  12  13  14  15  ...