이 문자열 검색 알고리즘에서 strlen(검색대상문자열)을 없애려면
글쓴이: cppig1995 / 작성시간: 목, 2008/07/17 - 8:59오전
char *strstr_jump(char *S, const char *s)
{
char Ereal[256] = {0}, *E = &Ereal[128];
int i, j, Slen = strlen(S), slen = strlen(s);
for(i = 0; i < slen; ++i) E[s[i]] = 1;
for(i = 0; i < Slen; i += slen)
if(E[S[i]])
for(j = i - slen + 1; j <= i; ++j)
if(!strncmp(&S[j], s, slen))
return &S[j];
return 0;
}5625411바이트 중에서 위치 4782202에 있는 10바이트의 문자열을 찾을 때, clock()을 이용해 측정하면 100회 반복에 1300클럭(strstr)-2100클럭(strstr_jump)으로 상당한 차이가 발생합니다. 생각해보니 5625411바이트에 대해 strlen을 돌리니 그 꼴 될 만 하다는 생각이 들었습니다. strlen(S)만 없애면 상당히 개선될 것 같아 보이기도 하더군요.
질문1: strlen(S)를 없애기에는 제 내공이 부족합니다. strlen(S)를 없애려면 어떻게 해야 할까요?
질문2: 최적화할 수 있는 다른 방법은 없을까요?
질문3: 이 문자열 검색 알고리즘을 뭐라고 해야 할까요?
Forums:
j가 음수가 될 수도 있지 않나요?
strlen을 쓰는 대신 '\0' 이 나올때까지 iteration 하면 되지 않을까요? 그리고, i가 0일때 j가 음수가 될 수도 있지 않나요? 제대로 따라가보진 않았는데, 얼핏 보니 ...
스트링 검색이면 BM, KMP, Rabin-karp 같은걸 써보시는것도...
s가 좀 길어지면 E 라는 배열을 잡은 의미가 없어질 것 같은데요. strncmp 부분을 최적화하다보면 Rabin-karp 랑 비슷해질것 같습니다.
--
http://www.deisys.net
--
http://www.deisys.net
그러게
그러게 말입니다.
사실, s 내에 나오는 바이트의 가지수가 100만 넘어도 엄청 느려질 겁니다.
--
임수서룬뫼 윤희수 {cppig1995/돼지군}
Real programmers /* don't */ comment their code.
If it was hard to write, it should be /* hard to */ read.
char *strstr_jump(char *S,
char *strstr_jump(char *S, const char *s) { char Ereal[256] = {0}, *E = &Ereal[128]; int i, j, Slen = strlen(S), slen = strlen(s); for(i = 0; i < slen; ++i) E[s[i]] = 1; for(i = 0; i < Slen; i += slen) if(E[S[i]]) for(j = i - slen + 1; j <= i; ++j) if(!strncmp(&S[j], s, slen)) return &S[j]; return 0; }허접하지만 제생각..
char *strstr_jump(char *S, const char *s)
{
char Ereal[256] = {0}, *E = &Ereal[128];
int i, j, Slen = strlen(S), slen = strlen(s);
//이곳에서 플래그만 주지말고 다음 문자값을 가지게하는거에요..
for(i = 0; i < slen; ++i) E[s[i]] = 1;
for(i = 0; i < Slen; i += slen)
if(E[S[i]]) //그리고 이곳에서 비교를 E[S[i]] && E[S[i]] == S[i+1]
//제생각에는 한문자만 일치하는걸로 아래의 반복문을 실행하는건 약간 비효율적이지않을까요?
for(j = i - slen + 1; j <= i; ++j) //방금생각난건데 위에 조건문을 바꾸지말고 이곳 반복문을 E를 가지고 하는거에요
if(!strncmp(&S[j], s, slen)) //이전 문자값을 아는건 인덱스를 아는거고 그럼 추적하다가 원점으로 돌아왔을
return &S[j]; //때 길이가 slen과 같다며 같은문자열이고 원점으로 안온다면 다른문자열이겠죠?
//이방법을 이용할경우엔 위에서 E에 다음 문자값을 가지게하면안되고 이전문자값을
return 0; //가지게해야 좀더 구현이 용이할거같네요
}
제생각 한번써봤는데 이해가 잘안되시면 어쩌죠^^;;
코드로 한번 만들어봐야겠네요~
ㅠㅠ 문단정리 어케하는지 모르겠어영 ㅠㅠ 죄송;
예외처리 생각하지
경계검사 때문에 없애기 힘들 것 같습니다.
예외처리 생각하지 않으면
int l1 = strlen(s1); int l2 = strlen(s2); while (l1 >= l2) { if (!memcmp(s1, s2, l2) return s1; l1--; s1++; } return NULL;OTL
댓글 달기