C에서 검색 알고리즘 최적화

StackOverflow https://stackoverflow.com/questions/15838

문제

이 순차 검색 알고리즘의 성능은 다음과 같습니다.프로그래밍 실습) C의 기본 유틸리티를 사용하여 개선할 수 있습니다.i 변수를 레지스터 변수로 설정하면 어떻게 될까요?

int lookup(char *word, char*array[])
{
    int i

    for (i = 0; array[i] != NULL; i++)
        if (strcmp(word, array[i]) == 0)
            return i;

    return -1;
}
도움이 되었습니까?

해결책

예, 하지만 아주 약간만요.더 나은 알고리즘을 사용하면 훨씬 더 큰 성능 향상을 얻을 수 있습니다(예: 목록 정렬 유지 및 이진 검색 수행).

일반적으로 특정 알고리즘을 최적화하면 지금까지만 얻을 수 있습니다.더 나은 알고리즘을 선택하면(완전히 최적화되지 않은 경우에도) 성능이 상당히 향상될 수 있습니다.

다른 팁

제 생각엔 별 차이가 없을 것 같아요.컴파일러는 이미 해당 방향으로 최적화합니다.

게다가 변수 i는 큰 영향을 미치지 않으며 단어는 함수 전체에서 일정하게 유지되며 나머지는 너무 커서 어떤 레지스터에도 맞지 않습니다.캐시의 크기와 전체 어레이가 캐시에 들어갈 수 있는지 여부가 중요합니다.

문자열 비교는 계산상 비용이 많이 듭니다.

검색하기 전에 배열에 대해 일종의 해싱을 사용할 수 있습니까?

센티날 방식으로는 잘 알려진 기술이 있다.센티널 방식을 사용하기 위해서는 "array[]"의 길이를 알아야 한다.sentinal을 사용하면 "array[i] != NULL" 비교를 제거할 수 있습니다.

int lookup(char *word, char*array[], int array_len)
{
    int i = 0;
    array[array_len] = word;
    for (;; ++i)
        if (strcmp(word, array[i]) == 0) 
            break;
    array[array_len] = NULL;
    return (i != array_len) ? i : -1;
}

TPOP을 읽고 있다면 다음으로 다양한 데이터 구조와 알고리즘을 사용하여 이 검색을 몇 배 더 빠르게 만드는 방법을 알게 될 것입니다.

하지만 다음과 같은 것을 교체하면 작업을 좀 더 빠르게 만들 수 있습니다.

for (i = 0; i < n; ++i)
    foo(a[i]);

~와 함께

char **p = a;
for (i = 0; i < n; ++i)
    foo(*p);
    ++p;

배열 끝에 알려진 값이 있는 경우(예:NULL) 루프 카운터를 제거할 수 있습니다.

for (p = a; *p != NULL; ++p)
    foo(*p)

행운을 빌어요, 정말 좋은 책이에요!

해당 코드를 최적화하려면 동등성만 확인하고 전체 단어를 평가할 필요가 없으므로 strcmp 루틴을 다시 작성하는 것이 가장 좋습니다.

그 외에는 별로 할 수 없습니다.더 큰 텍스트 내에서 텍스트를 찾고 있는 것처럼 보이면 정렬할 수 없습니다.텍스트가 정렬되지 않을 가능성이 높으므로 이진 검색도 작동하지 않습니다.

내 2p(C-유사 코드):

wrd_end = wrd_ptr + wrd_len;
arr_end = arr_ptr - wrd_len;
while (arr_ptr < arr_end)
{
    wrd_beg = wrd_ptr; arr_beg = arr_ptr;
    while (wrd_ptr == arr_ptr)
    {
        wrd_ptr++; arr_ptr++;
        if (wrd_ptr == wrd_en)
            return wrd_beg;
    }
    wrd_ptr++;
}

마크 해리슨:for 루프는 절대로 종료되지 않습니다!(++p는 들여쓰기되어 있지만 실제로는 for :- 내에 있지 않습니다.)

또한 포인터와 인덱싱 간의 전환은 일반적으로 성능에 영향을 미치지 않으며 레지스터 키워드를 추가하지도 않습니다(mat가 이미 언급한 것처럼). 컴파일러는 적절한 곳에 이러한 변환을 적용할 만큼 똑똑합니다. , 수동으로 의사 마이크로 최적화하는 것보다 더 나은 작업을 수행합니다.

문자열을 일치시키는 더 빠른 방법은 파스칼 스타일로 저장하는 것입니다.문자열당 255자 이상이 필요하지 않은 경우 대략 다음과 같이 저장하고 첫 번째 바이트에 개수를 표시합니다.

char s[] = "\x05Hello";

그러면 다음을 수행할 수 있습니다.

for(i=0; i<len; ++i) {
    s_len = strings[i][0];
    if(
        s_len == match_len
        && strings[i][s_len] == match[s_len-1]
        && 0 == memcmp(strings[i]+1, match, s_len-1)
    ) {
        return 1;
    }
}

그리고 정말 빠른 속도를 얻으려면 문자열 시작 + 64, + 128 및 다음 문자열의 시작에 대한 메모리 프리패치 힌트를 추가하세요.하지만 그건 정말 미친 짓이다.:-)

또 다른 빠른 방법은 컴파일러가 SSE2에 최적화된 memcmp를 사용하도록 하는 것입니다.고정 길이 char 배열을 사용하고 문자열이 64바이트 정렬에서 시작되도록 정렬합니다.그런 다음 const char *match 대신 const char match[64]를 함수에 전달하거나 strncpy match를 64,128,256 바이트 배열에 전달하면 좋은 memcmp 함수를 얻을 수 있다고 믿습니다.

이에 대해 좀 더 생각해 보면 이러한 SSE2 일치 기능은 Intel 및 AMD의 가속기 라이브러리와 같은 패키지의 일부일 수 있습니다.한번 봐봐.

현실적으로 I를 레지스터 변수로 설정해도 컴파일러가 이미 수행하지 않은 작업은 수행되지 않습니다.

참조 배열을 미리 처리하는 데 시간을 할애하고 싶다면 Google에서 "세계에서 가장 빠른 스크래블 프로그램"을 검색하여 구현해야 합니다.스포일러:문자 조회에 최적화된 DAG입니다.

/* there is no more quick  */
int lookup(char *word, char*array[])
{
    int i;
    for(i=0; *(array++) != NULL;i++)
        if (strcmp(word, *array) == 0)
            return i;
    return -1;
}
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top