빠른 strlen?

Question

대표 문자 strlen()이 (가) \0이 될 때까지 첫 번째 문자에서부터 이동합니다. 각 문자를 통과해야합니다. 알고리즘의 의미에서 O (N).

입력이 모호하게 정의 된 경우 더 빠르게 수행 할 수 있습니까? Like : 길이가 50보다 작거나 길이가 약 200 자입니다.

내가 조회 블록을 생각했지만 모든 최적화를 얻지 못했습니다.

Answer 1

사실 strlen의 glibc's implementation는 벡터화 방법의 흥미로운 예이다.벡터 명령어를 사용하지 않지만 버퍼의 32 또는 64 비트 워드에 대한 일반 명령어 만 사용하는 방법을 찾습니다.

Answer 2

확실히. 문자열에 쓰는 동안 길이를 추적하십시오.

Answer 3

짧은 대답 : 아니오.

대답 : 베어 본 C 문자열의 문자열 길이를 확인하는 더 빠른 방법이 있다면 일반적으로 C 문자열 라이브러리로 사용되는 것이 이미 통합되지 않았을 것이라고 생각하십니까?

문자열에 대한 추가 지식 없이는 각 문자를 확인해야합니다. 추가 정보를 유지하려면 struct의 필드 (실제 문자 배열/문자열 포인터)에 길이를 저장하는 struct을 만들 수 있습니다.이 경우 길이를 만들 수 있습니다 조회 상수 시간이지만 문자열을 수정할 때마다 해당 필드를 업데이트해야합니다.

Answer 4

문자열의 최소 길이가 알려진 경우 분명히 그 위치에서 검색을 시작할 수 있습니다. 그 너머

, 당신이 할 수있는 일이 정말이 아니다; 똑똑한 것을 시도하고 \0 바이트를 찾으려고한다면 문자열의 시작과 그 지점 사이의 모든 바이트를 확인하여 이전 \0이 없는지 확인해야합니다. strlen 최적화 할 수없는 것은 아니다

. 그것은 파이프 라인 될 수 있으며 각 비교시 워드 크기 또는 벡터 청크를 처리하도록 만들 수 있습니다. 대부분의 아키텍처에서 이러한 접근 방식과 다른 접근 방식을 조합하면 순진한 바이트 비교 루프에 비해 실질적인 일정 속도가 향상됩니다. 물론 대부분의 성숙한 플랫폼에서 시스템 strlen은 이미 이러한 기술을 사용하여 구현됩니다.

Answer 5

벡터화를 사용해 볼 수 있습니다. 컴파일러에서 수행 할 수 있는지 확실하지 않지만 수동으로 수행했습니다 (내장 함수 사용). 그러나 그것은 긴 문자열에 대해서만 당신을 도울 수 있습니다.

stl 문자열을 사용하면 더 안전하며 std :: string 클래스의 길이가 포함됩니다. , 당신은 길이가 200 자입니다 알고 있다고 생각, 이제

size_t 
strlen(const char *str) 
{ 
     const char *s; 

     for (s = str; *s; ++s) 
       ; 
     return (s - str); 
} 

:

Answer 6

잭의 '\ 0'종료를 찾아

strlen 작품, 여기에 오픈 BSD에서 찍은 구현입니다 너는 말했다. 200에서 시작하여 '\ 0'에 대해 위아래로 반복한다고 가정 해보십시오. 당신은 204에서 하나를 발견했습니다, 그것은 무엇을 의미합니까? 그 문자열은 204 문자 길이입니까? 아니! 그 전에 다른 '\ 0'으로 끝날 수 있었고 당신이했던 모든 일은 한계를 벗어났습니다.

Answer 7

코어 i7 프로세서를 구입하십시오.

코어 i7에는 SSE 4.2 명령어 세트가 제공됩니다. 인텔은 strlen 및 관련 검색 작업의 속도를 높이기 위해 추가로 4 가지 벡터 지침을 추가했습니다.

http://smallcode.weblogs.us/oldblog/2007/11/