[완료] 문자열 검색 속도에 관하여

whxoans의 이미지

엄청나게 긴 TEXT 파일(40Mb 이상)을 메모리에 올려놓고
한줄 단위로 파싱을 하여 그 줄에 특정 단어가 있는지 검색을 하고
특정 단어가 포함되어 있으면 vector에 push_back()을 하는 로직입니다.

문제는 문자열 검색 속도가 느려 사용할 수 없을 정도라는 것입니다.

말씀드린 부분입니다.

		for ( ep = file_buffer; error > arry_length; ep = strchr(ep, '\n') + 1) {
			string line = truncateAtNewLine((string)ep);			
			if ( line.find("RESULT_CODE=2", 0) != string::npos ) {
				r_list->push_back(line + '\0');
				arry_length++;
				cout << "#" ;
			}
 
		}

file_buffer는 fread()를 통해 한번에 읽어 드린 내용이고
error의 갯수는 알고 이미 알고 있기 때문에 error 만큼의 문자열을 찾아야 합니다.
truncateAtNewLine은 string객체는 받아 처음 계행 문자까지 잘라 주는 함수입니다.

std::string truncateAtNewLine(std::string input){
   std::string::size_type size_newLen=input.size();
   if ((size_newLen=input.find("\n"))!=std::string::npos) {
       if (input.rfind('\r', size_newLen)!=std::string::npos){
           size_newLen = input.rfind('\r', size_newLen);
       }
       input.resize(size_newLen-1);
   }
   return input;
}

최소 5만줄 이상을 처리해야 하는데 str::find()는 아무래도 조금 느린감이 있고
vector를 쓰지 않고 char **로 메모리 할당을 직접하며 문자열을 넣는 방법도 취해 보았지만 이 역시 큰 차이가 없습니다.

조사한 바로는 std::find()는 문자열이 길어질 수록 속도가 급감하는 경향이 있다고 하네요.
해서 Boyer-Moore 검색 알고리즘을 적용해서 해결했는다는 말도 있는데

이런 경험이 있으시다면 조언 부탁드립니다!!:D

pokev25의 이미지

RegEx 인가..그거로 하시면 좀 나을듯 합니다만..

정규식을 사용하셔야지..

저런 방법은..쫌...

winner의 이미지

정규식 engine은 기본 문자열 처리 함수보다 느립니다. 복잡한 logic 이 요구되지 않고, 속도가 필요하다면 기본 문자열 함수를 쓰는게 낫죠.

klyx의 이미지

패턴이 아니라 특정 문자열을 찾는데도 정규식을이용하나요?

klyx의 이미지

40MB에서한줄씩 체크한다는건 그 한줄씩이 각각 서로 다른 데이터이고, 한번 쭉 파싱하고 끝나는게 아니라 요청이 있을때마다 파싱해야하는 것이라면 데이터베이스를 이용하는 것도 고려해볼만 할듯합니다.
전에 10MB이상의 사전데이터를 단순한 txt파일로 다루다가 너무 느려서 DB로 짜봤더니 당연하지만 엄청나게 빨라졌습니다.
제가 그때쓴건 SQLite였습니다. RMDBS인 MySQL보다는 느리다고 합니다만, 충분히 빠르며 가볍기도 하고 파일디비라 서버-클라이언트도 필요없고, 간단하게 프로그램내에 임베딩이 가능합니다.

그냥한번 쭉 읽고 마는거라면...DB구축하는데 걸리는 시간을 생각하면 어느쪽이 나을지는 잘 모르겠네요. 알고리즘에 대해서는 잘 모르지만 아무리 검색 알고리즘을 개선한다고해도, 파일포맷 자체가 검색에 적합하지 않으면 결국 큰 파일에 시간이 오래걸리는건 마찬가지 아닐까요?

whxoans의 이미지

사실 다시 사용하기 때문에 메모리나 vector등에 저장을 하는거죠.
해서 저도 DB를 사용해볼 생각을 했었습니다.

MySQL을 서버에 설치하고 client를 불러다 쓸 생각을 했었는데
SQLite라는 것이 현상황에 어울릴 듯 싶습니다.

좋은 정보 감사합니다.:)

klyx의 이미지

참고로 (SQLite매뉴얼 읽어보시면 아시겠지만)메모리상에 DB를 올릴수도있습니다.
만약 입력파일이 매번 바뀌는 것이라면 꼭 파일로 저장하지 않아도, SQLite로 메모리상에 저장하고 검색할수 있습니다.

winner의 이미지

제가 보기에 가장 비효율적인 부분은
string line = truncateAtNewLine((string)ep); 입니다.

계속해서 변경되는 시작부분부터 끝까지 string으로 생성하는데 이거 엄청나게 시간을 소모할 겁니다.
strchr을 쓸 줄 아시는 거 보니까 C 함수도 익숙하신 모양인데

string trucateAtNewLine(const char *line) 형태로 고쳐보시죠.
아마 rfind를 쓰고 싶으신 모양인데 그 정도는 직접 작성하시는게 어렵지 않을 겁니다.

하여간 code를 보면 대략 최소 10배는 성능을 개선할 수 있어 보입니다.

whxoans의 이미지

주로 C를 써서 C++로 할려고 해도 조금 어렵네요^^;
제가 각 function들의 time complexity에 대해서는 모르고 있는 상태이고
말씀하신거와 같이 해당부분에서 가장 delay가 길게 발생합니다.

해서

int arry_length = 0;
char **arry = (char **)malloc(50000);
for( ..생략.. )
char *np = ep;
ep = strchr(ep, '\n');
memcpy(buffer, ep, np - ep);
if ( strstr(buffer, "RESULT_CODE=2") != NULL ) {
    arry[arry_length] = (char *)malloc(strlen(buffer)+1);
    strcpy(arry[arry_length], buffer)
    arry_lenght++;
}
}

위와 같은 방법도 해보았는데 큰 차이는 없더라구요.

어떤 방법이 있을까요?

winner의 이미지

그런데... memcpy와 strstr 호출 부분에 bug가 있네요.. ^_^

kinosoul의 이미지

사이즈 별로 스레드를 생성해서
검색하는건 어떨까요?
40M의경우 10M 단위로 스레드를 생성해서 파일을 읽어들이고
역시 10M단위로 문자열을 검색하는거죠?
4개의 스레드면 적어도 지금보다는 많은부분에서 성능 개선이 될꺼같습니다.
방금 제친구와 쪽지로 대화를 했는데 같은 생각이더군요 ^^;
어느정도의 사이즈가 적당한지는 제가 확인을 안해봐서 모르겠지만
스레드 사용방법이 가장 괜찮은거 같습니다.

winner의 이미지

기술언어의 정확성이 부족하다면 개선된 algorithm을 활용하는 것도 어려운 일이죠.
극한에 대한 이해없이 미적분하는 거랑 동일합니다.

만일 자작 code로 해결하실 거라면 C, C++를 code 형태를 먼저 다듬는게 먼저일 것 같아요.

winner의 이미지

Text file 내에 \r이 있는 이유가 뭔가요?
그냥 DOS/Windows format이라 \n 앞에 오는 건가요?

whxoans의 이미지

정확히 파일을 쓰는 OS는 windows 2003 server입니다.

winner의 이미지

지금 성능문제가 IO에서 발생하는게 아니니 \r\n 처리는 귀찮을 뿐입니다.

kinosoul의 이미지

kldp에 질문하는거보단 구글에서 검색하는게 더 효율적인거 같습니다.
지금 검색해보니 자료가 엄청 많네요
제가 찾아본건데 도움이 되실지 모르겠습니다 ^^;

http://bage.springnote.com/pages/1525272

bushi의 이미지

file_buffer 의 내용을 수정없이 계속 보존해서 재사용하나요 아니면 처리중에 변경이 일어나도 괜찮은가요 ?
수정이 불가하다면 어딘가에 pool 을 만들고 malloc() 없이 memcpy() 만. (어차피 포인터는 array[] 에 보관되니...)
수정이 가능하다면, 대략 이런 느낌으로...

char *end_of_buffer = file_buffer + file_size;
char *sp = file_buffer;
char *ep = NULL;
char *array[nr_of_error], **array_p = &array[0];
 
memset(array, 0, sizeof(char*) * nr_of_err);
 
while (sp < end_of_buffer) {
   ep = memchr(sp, '\n', end_of_buffer - sp);
   if (!ep)
      break;
   *ep = 0; /* 원본이 수정됨 */
   if (strstr(sp, "RESULT_CODE=2")) {
     *array_p = sp;
     array_p++;
   }
   sp = ep + 1;
}

OTL

winner의 이미지

'\n' 이 '\0'으로 바뀌는게 문제될게 없다면 이걸로 충분한 듯 합니다.
사실 DB를 사용한다고 해도 DB가 개선된 문자열 검색 algorith을 효율적으로 활용할 것 같지는 않으니까 제가 보기엔 가장 훌륭한 해결책의 prototype으로 보입니다.

whxoans의 이미지

항상 제 질문에는 bushi님의 답변이
칼같이 예리하고 깜끔하게 달아주셔서 언제나 감사드리고 있죠 :)

언제나 놀라워요 =)

whxoans의 이미지

코드를 봤을 C++ 느낌을 줘야하는 상황이라 ^^;
역시 STL이나 std멤버로는 속도 문제가 계속 있을꺼 같네요...

말씀해주신 방법은 제가 생각에 매몰되어 생각을 안해봤네요.:-)
사실 이렇게 추출하는 이유 자체가 필요한 부분만 메모리에 올릴 생각이었는데요.
이유는 나중에 몇가지 키워드로 검색 및 정렬을 해야하는데 루프의 숫자를 줄이고 싶었거든요.

답변은 감사합니다!

winner의 이미지

C++ 느낌이라는 것은 동료들이 C++를 많이 쓰기 때문인가요? 하지만 작성자가 제대로 이해하지 못하는 code가 가장 위험할 것 같아요.
bushi님의 code는 향후 C++를 이해하시면서 C++ 함수로 변경하기 어렵지 않을 것 같습니다. 아니면 동료분과 함께 수정해도 좋을 것 같고요.
필요한 부분만 memory에 올리는 것은 bushi님 code를 수정하셔서 사용하면 되겠죠.
위 code를 활용한 상황에서 성능이 계속 문제라면 strstr을 고급문자열검색 algorithm으로 바꿔보세요.

whxoans의 이미지

이 포스트는 '[완료]'로 변경했습니다~
좋은 하루 되시길!

감사합니다.

select99의 이미지

그냥 기본적인함수로 한번에 처리하는게 간단하고 빠르지 않나요? .
일단 블럭단위로 읽으시고..
fread 나 맘에 드는거 선택하시고
buf 에 읽어지면
for 문자단위 for 문을돌며 처리하세요.
대충 아래같은형태로.. 좀더 다듬고.
비교부분에 switch 문을쓴다든가해서 더빠르게 개선할수도..있겠네요.

for( ;fread(buf,...); )
for( str = buf ; str < buf + sizeof(buf); str++ )
if( *str == '\n' ) 새줄이니까..포인터기억했다가 저장할때이용...
if( memcmp( str, cmpstr, sizeof( cmpstr ))) savefunc(str,...);

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.