C: 문자열을 연결하는 가장 빠르고 좋은 방법은 무엇입니까?

C: 문자열을 연결하는 가장 빠르고 좋은 방법은 무엇입니까?

나는 현재 를 사용하여 문자열을 연결합니다.strcat()로부터의 기능string.h도서관.

생각해보았는데, 매우 비싼 기능이어야 한다는 결론에 도달했습니다. 연결이 시작되기 전에 촤 배열을 찾을 때까지 반복해야 하기 때문입니다.'\0'촤

예를 들어, 문자열을 연결하면"horses"1000회 사용strcat(), 돈을 지불해야 합니다.(1 + 2 + 3 + ... + 1000) * strlen("horses") = (1000*1001)/2 * 6 = 3003000

저는 문자열 길이의 정수를 유지하고 다음으로 보내는 비표준적인 방법에 대해 생각했습니다.strcat()문자열 끝의 포인터:

strcat(dest + dest_len, "string");

이 경우에는 제가 계산만 하겠습니다.1000 * strlen("horses") = 1000 * 6 = 6000.

6000보다 500배 작습니다.3003000, 따라서 이러한 연결을 많이 수행할 경우 성능에 매우 중요할 수 있습니다.

제 솔루션보다 더 나은 표준 방법이 있을까요?

조엘 스폴스키는 그의 Back to Basics 기사에서 다음과 같은 비효율적인 문자열 연결의 문제를 설명합니다.strcat화가 쉴레미엘의 알고리즘처럼 (기사를 읽어보면 꽤 좋습니다.)비효율적인 코드의 예로, 그는 O(n²) 시간으로 실행되는 다음과 같은 예를 제시합니다.

char bigString[1000];     /* I never know how much to allocate... */
bigString[0] = '\0';
strcat(bigString,"John, ");
strcat(bigString,"Paul, ");
strcat(bigString,"George, ");
strcat(bigString,"Joel ");

첫번째 문자열을 처음으로 넘겨보는 것은 문제가 되지 않습니다. 이미 두번째 문자열을 넘겨야 하기 때문에 하나의 런타임이 발생합니다. strcat결과의 길이에서 선형입니다.여러개strcats는 문제가 있습니다. 왜냐하면 우리는 이전에 연결된 결과를 반복해서 살펴보기 때문입니다.그는 다음과 같은 대안을 제시합니다.

이걸 어떻게 고치죠?몇몇 스마트 C 프로그래머들은 그들만의 것을 구현했습니다.mystrcat다음과 같이

char* mystrcat( char* dest, char* src )
{
     while (*dest) dest++;
     while (*dest++ = *src++);
     return --dest;
}

여기서 뭘 한 거지?아주 적은 추가 비용으로 새로운 긴 줄의 끝에 포인터를 돌려드립니다.이렇게 하면 이 함수를 호출하는 코드가 문자열을 다시 검색하지 않고 추가하기로 결정할 수 있습니다.

char bigString[1000];     /* I never know how much to allocate... */
char *p = bigString;
bigString[0] = '\0';
p = mystrcat(p,"John, ");
p = mystrcat(p,"Paul, ");
p = mystrcat(p,"George, ");
p = mystrcat(p,"Joel ");

물론 이는 n제곱이 아닌 선형 성능이기 때문에 연결할 내용이 많아도 성능 저하를 겪지 않습니다.

물론 표준 C 문자열을 사용하려면 이렇게 해야 합니다.문자열의 길이를 캐싱하고 특수 연결 함수(예: 호출)를 사용하는 것에 대해 설명하는 대안strcat)는 파스칼 문자열의 변형으로, 조엘도 언급한 바 있습니다.

파스칼의 설계자들은 이 문제를 인지하고 문자열의 첫 번째 바이트에 바이트 수를 저장함으로써 이 문제를 "수정"했습니다.이것들을 파스칼 스트링이라고 부릅니다.0을 포함할 수 있으며 null로 종료되지 않습니다.바이트는 0에서 255 사이의 숫자만 저장할 수 있기 때문에 파스칼 문자열의 길이는 255바이트로 제한되지만 Null Terminated가 아니기 때문에 ASCIZ 문자열과 동일한 양의 메모리를 차지합니다.파스칼 줄의 장점은 줄의 길이를 알아내기 위해 고리를 가질 필요가 없다는 것입니다.파스칼에서 문자열의 길이를 찾는 것은 전체 루프 대신 하나의 어셈블리 명령입니다.그것은 엄청나게 빠릅니다.

…

오랫동안 파스칼 문자열 리터럴을 C 코드에 넣으려면 다음과 같이 써야 했습니다.

char* str = "\006Hello!";

네, 직접 손으로 바이트 수를 세어 문자열의 첫 번째 바이트로 하드코딩해야 했습니다.게으른 프로그래머들은 이것을 하고 느린 프로그램을 갖습니다.

char* str = "*Hello!";
str[0] = strlen(str) - 1;

쉽고, 빠르고, 일반적이고, 안전하기를 원한다면, 나는 다음을 사용하는 것을 제안합니다.open_memstream()기능(이것은 POSIX-2008 표준의 일부이지만 안타깝게도 C11 표준에는 들어가지 못했습니다.)다음과 같이 작동합니다.

먼저, 당신은 그것에 포인터와 사이즈의 주소를 건네줍니다.

char* result = NULL;
size_t resultSize = 0;
FILE* stream = open_memstream(&result, &resultSize);

반환 값은 사용했던 것처럼 파일 스트림입니다.fopen()파일을 여세요.이와 같이, 당신은 전체 무기고를 사용할 수 있습니다.fprintf()& 당신이 좋아하는 모든 것을 당신의 메모리 버퍼에 스트리밍하고, 당신을 위해 자동으로 할당되고 관리됩니다.가장 중요한 것은 누적된 문자열의 크기도 추적하기 때문에 크기를 계산하기 위해 다시 검색할 필요가 없다는 것입니다.

for(int i = 0; i < 1000000; i++) {
    fprintf(stream, "current number is %d, or 0x%x\n", i, i);
}

마지막으로 스트림을 닫으면 결과 포인터와 크기 변수가 작성된 문자열 데이터의 실제 양을 반영하도록 업데이트됩니다.

fclose(stream);
//Now you have a zero terminated C-string in result, and also its size in resultSize.
//You can do with it whatever you like.
//Just remember to free it afterwards:
free(result);

여러 문자열을 연결하기 위해 코드는 다음을 사용할 수 있습니다.strlen()그리고.memcpy()둘 다 종종 잘 최적화된 함수입니다.

이 접근 방식을 사용하면 저렴한 비용을 쉽게 추가할 수 있습니다.size제한.
그렇지 않으면 대상 버퍼가 오버플로될 수 있는 실제 가능성을 고려할 때 크기 제한은 필수적입니다.

문자열 길이의 합에 비례하는 실행 시간: O(len(S[0]) + len(S[1]) + len(S[2]) + ...)

char *strsncat(char *dest, size_t size, char * strs[], size_t n) {
  assert(size > 0);
  size--;
  char *p = dest;
  while (n-- > 0) {
    size_t len = strlen(*strs);
    if (len >= size) {
      len = size;
    }
    size -= len;
    memcpy(p, *strs, len);
    strs++;
    p += len;
  }
  *p = '\0';
  return dest;
}

void cat_test(void) {
  char dest[10];
  char *strs[]  = { "Red", "Green", "Blue" };
  printf("'%s'\n",strsncat(dest, sizeof dest, strs, sizeof strs/sizeof strs[0]));
  // 'RedGreenB'
}

답변이 늦었지만, 저도 방금 같은 문제를 발견했습니다.출발점을 찾기 위해, 저는 맨 페이지를 다시 읽기로 결정했습니다.strcpy,strncpy,strlen,strnlen,strcat그리고.strncat.

하마터면 놓칠 뻔 했지만, 다행히도...흥미로운 구절이 있습니다.man strcpy내 개발 시스템(데비안 스트레치)에서.인용하기 (내 포맷):

strlcpy()

일부 시스템(BSD, Solaris 등)은 다음과 같은 기능을 제공합니다.

size_t strlcpy(char *dest, const char *src, size_t size);

이 기능은 다음과 유사합니다.strncpy(), 하지만 기껏해야 복사합니다.size-1에 바이트 단위로dest, 는 항상 종료 null 바이트를 추가하고 대상을 (further) null 바이트로 패딩하지 않습니다.이 기능은 다음의 몇 가지 문제를 해결합니다.strcpy()그리고.strncpy(), 그러나 발신자는 다음과 같은 경우에도 데이터 손실의 가능성을 처리해야 합니다.size너무 작습니다.함수의 반환 값은 의 길이이며, 이를 통해 잘림을 쉽게 탐지할 수 있습니다. 반환 값이 다음보다 크거나 같으면size, 잘라내기가 발생했습니다.데이터 손실이 중요한 경우 호출자는 통화 전 인수를 확인하거나 함수 반환 값을 테스트해야 합니다.strlcpy() 에 존재하지 않으며 에 의해 표준화되지는 않지만 라이브러리를 통해 리눅스에서 사용할 수 있습니다.

예, 이 글을 읽고 계십니다.glibc 함수의 man 페이지는 작업을 더 잘 수행하는 다른 라이브러리의 표준화되지 않은 함수에 대한 힌트를 포함합니다.이것은 이 문제가 얼마나 중요한지를 증명할 수 있습니다.

그건 그렇고, 왜 그 디자이너들이str(n)cpy()함수가 복사된 바이트 수 또는 새 끝에 대한 포인터를 선택하지 않았습니다.dest답례품으로그냥 돌아오는 것dest이 함수들은 매개 변수를 변경하지 않기 때문에 우습게 보입니다. 그래서 모든 경우에 함수가 반환되었을 때 호출자에게 여전히 알려져 있으며 따라서 이 선택은 의미가 없습니다.제가 뭔가를 빠뜨렸나요?

내가 알기 전까지strlcpy(), @Joshua Taylor가 그의 답변에서 보여준 것과 같은 나만의 문자열 연결 기능을 주로 사용했습니다.그러나 이 아이디어에는 나름의 문제점이 있습니다.

문자열을 바이트 단위로 스캔/복사하는 것은 매우 비효율적일 수 있습니다.대상 CPU에 따라 32비트 또는 64비트 레지스터를 사용하고 여러 바이트를 한 번에 복사해야 합니다.물론 복사해야 할 바이트 수가 충분한지 확인해야 하고 그렇지 않은 경우에는 다음으로 작은 레지스터 크기를 사용해야 하기 때문에 기능이 더욱 복잡합니다.성능을 더욱 향상시키기 위해서는 조립 코드를 사용하여 기능을 구현해야 합니다.

AFAIK, glibc나 libbsd와 같은 라이브러리들이 그런 방식으로 구현되었습니다.따라서 libbsd 구현을 사용하는 것이 가장 좋을 수 있습니다.하지만 저는 성능 측정을 하지 않았습니다.

두 개의 문자열이 있다고 가정합니다.s1그리고.s2길이로l1그리고.l2연결은 새 문자열을 생성해야 함을 의미합니다.s3길이로l1+l2. 이 작업의 시간 복잡도는O(l1+l2). 이런 관점에서 보면,strcat()최선의 선택인 것 같습니다.

그러나 두 문자열이 연결된 상태를 표시하려면 해당 문자열의 포인터를 기록하기만 하면 됩니다.O(1) 간단한 예를 들면 다음과 같습니다.

typedef struct ConcatStr {
    char* str1;
    char* str2;
} ConcatStr;
ConcatStr myStrcat( char* str1, char* str2 )
{
    ConcatStr cstr;
    cstr.str1 = str1;
    cstr.str2 = str2;
}

여기에 제가 하는 일이 있고 strcat보다 빠르지만 다른 솔루션과 비교하면 어떨지 모르겠습니다.예를 들어 1000개의 문자열 배열을 가지고 있고 문자열을 공백 사이에 연결하고 10만 문자 버퍼를 가지고 있다고 가정해 보겠습니다.

int L=0;
char buffer[100000];
char *str[1000]; // assume this is already populated
for (int i=0; i<1000; i++) // 1000 or whatever number you actually have
{
 L+=sprintf(buffer+L,"%s ",str[i]); // this is the important part
}

sprintf는 쓴 글자 수를 반환하고 포인터 버퍼 +L을 계속 진행합니다.이것은 안전 점검이 없습니다.L이 100000을 초과하는지는 확인할 수 있지만, 그건 고객님 부담입니다.buffer+L이 문자열 끝을 벗어나면 앱이 크래시됩니다.

저는 strcat의 드롭인 대체에 더 가까운 이 변형을 사용합니다.

char* mystrcat(char** dest, const char* src) {

    int i = 0;
    char cur;
    while(1) {
        cur = src[i];
        (*dest)[i] = cur;
        if(cur == 0) break;
        i++;
    }

    *dest += i;

    return *dest;
}

여기서는 반품 값이 중요하지 않습니다. ychar str[32]에 문자에 대한 실제 포인터를 저장할 수 없으므로 다음 작업을 수행할 수 있습니다.

char str[32];
char* pStr = str; //storage for pointer
mystrcat(&pStr, "bla");
mystrcat(&pStr, "de");
mystrcat(&pStr, "bla\n");
printf(str);

아니면

myfunction(char* pStr) {

    mystrcat(&pStr, "bla");
    mystrcat(&pStr, "de");
    mystrcat(&pStr, "bla\n");
}

char str[32];
myfunction(str);
printf(str);

포인터에 대한 스토리지가 이제 내 기능을 위해 스택에 생성되기 때문입니다.

길이 제한 버전은 다음과 같습니다.

char* mystrcat(char** dest, const char* src, int max) {

    int i = 0;
    char cur;
    while(1) {
        if(i == max) {
            (*dest)[i] = 0;
            break;
        }
        cur = src[i];
        (*dest)[i] = cur;
        if(cur == 0) break;
        i++;
    }

    *dest += i;

    return *dest;
}

확인하기

https://john.nachtimwald.com/2017/02/26/efficient-c-string-builder/

눈 깜짝할 사이에 char**를 클립보드에 복사할 수 있게 도와줬습니다.

    str_builder_t *sb;
     sb = str_builder_create();

                        int colcnt=0;
                        for (int i=0;i<nrF;i++)  // nrF = number of Fileds 
                    {
                            //strcat(DATA,sqlite_array[i]);
                     str_builder_add_str(sb, sqlite_array[i], 0); 
                            if (colcnt<nrofcolumns)  // my list view 
                                {
                            str_builder_add_str(sb, "\t", 0); 
                                colcnt++;

                            }
                                if (colcnt==nrofcolumns) 
                            {

                            str_builder_add_str(sb, "\n", 0); 
                                    colcnt=0;
                            }

                    }

    HANDLE  glob =GlobalAlloc(GMEM_FIXED,str_builder_len(sb)+1);
    memcpy(glob,str_builder_peek(sb),str_builder_len(sb)+1);
    OpenClipboard(NULL);
    EmptyClipboard();
    SetClipboardData(CF_TEXT,glob);
    CloseClipboard();   

다음은 간단한 안전하고 효율적인 연결 기능입니다.

#include <stdio.h>
#include <string.h>

char *strwrite(char *dest, size_t size, size_t *ppos, const char *src) {
    size_t pos = *ppos;
    if (pos < size) {
        size_t len = strlen(src);
        if (pos + len < size)
            memcpy(dest + pos, src, len + 1);
            *ppos += len;
        } else {
            memcpy(dest + pos, src, size - pos - 1);
            dest[size - 1] = '\0';
            *ppos = size - 1;
        }
    }
    return dest;
}

int main() {
    char dest[10];
    size_t pos = 0;
    for (int i = 0; i < 3; i++) {
        strwrite(dest, sizeof dest, &pos, "Test");
    }
    printf("%s\n", dest);   // TestTestT
    return 0;
}

POSIX 시스템에서 코드는 다음과 같이 단순화할 수 있습니다.strnlen():

char *strwrite(char *dest, size_t size, size_t *ppos, const char *src) {
    size_t pos = *ppos;
    if (pos < size) {
        size_t len = strnlen(src, size - pos - 1);
        memcpy(dest + pos, src, len);
        pos += len;
        dest[pos] = '\0';
        *ppos = pos;
    }
    return dest;
}

언급URL : https://stackoverflow.com/questions/21880730/c-what-is-the-best-and-fastest-way-to-concatenate-strings