Подтвердить что ты не робот

Конкатенация строк в C, какой метод более эффективен?

Я наткнулся на эти два метода, чтобы объединить строки:

Общая часть:

char* first= "First";
char* second = "Second";
char* both = malloc(strlen(first) + strlen(second) + 2);

Способ 1:

strcpy(both, first);
strcat(both, " ");       // or space could have been part of one of the strings
strcat(both, second);

Способ 2:

sprintf(both, "%s %s", first, second);

В обоих случаях содержание both будет "First Second".

Я хотел бы знать, какой из них более эффективен (мне нужно выполнить несколько операций конкатенации), или если вы знаете лучший способ сделать это.

4b9b3361

ОТВЕТЫ

Ответ 1

Для удобства чтения я бы пошел с

char * s = malloc(snprintf(NULL, 0, "%s %s", first, second) + 1);
sprintf(s, "%s %s", first, second);

Если ваша платформа поддерживает расширения GNU, вы также можете использовать asprintf():

char * s = NULL;
asprintf(&s, "%s %s", first, second);

Если вы застряли во время выполнения MS C, вы должны использовать _scprintf() для определения длины результирующей строки:

char * s = malloc(_scprintf("%s %s", first, second) + 1);
sprintf(s, "%s %s", first, second);

Скорее всего, самое быстрое решение:

size_t len1 = strlen(first);
size_t len2 = strlen(second);

char * s = malloc(len1 + len2 + 2);
memcpy(s, first, len1);
s[len1] = ' ';
memcpy(s + len1 + 1, second, len2 + 1); // includes terminating null

Ответ 2

Не беспокойтесь об эффективности: сделайте свой код читаемым и поддерживаемым. Я сомневаюсь, что разница между этими методами будет иметь значение в вашей программе.

Ответ 3

Здесь какое-то безумие для вас, я действительно пошел и измерил его. Кровавый ад, представьте это. Я думаю, что у меня есть некоторые значимые результаты.

Я использовал двухъядерный P4, работающий под управлением Windows, используя mingw gcc 4.4, создав "gcc foo.c -o foo.exe -std = c99 -Wall -O2".

Я протестировал метод 1 и метод 2 из исходного сообщения. Первоначально сохранялся malloc за пределами контрольного цикла. Метод 1 был в 48 раз быстрее, чем метод 2. Честно говоря, удаление -O2 из команды build сделало результат exe на 30% быстрее (пока еще не исследовали).

Затем я добавил malloc и свободный внутри цикла. Это замедлило метод 1 в 4,4 раза. Метод 2 замедлился в 1,1 раза.

Итак, malloc + strlen + free НЕ ДОЛЖНЫ доминировать над профилем, чтобы избежать того, чтобы избежать sprintf.

Здесь код, который я использовал (кроме циклов, были реализованы с помощью < вместо! =, но это нарушило HTML-рендеринг этого сообщения):

void a(char *first, char *second, char *both)
{
    for (int i = 0; i != 1000000 * 48; i++)
    {
        strcpy(both, first);
        strcat(both, " ");
        strcat(both, second);
    }
}

void b(char *first, char *second, char *both)
{
    for (int i = 0; i != 1000000 * 1; i++)
        sprintf(both, "%s %s", first, second);
}

int main(void)
{
    char* first= "First";
    char* second = "Second";
    char* both = (char*) malloc((strlen(first) + strlen(second) + 2) * sizeof(char));

    // Takes 3.7 sec with optimisations, 2.7 sec WITHOUT optimisations!
    a(first, second, both);

    // Takes 3.7 sec with or without optimisations
    //b(first, second, both);

    return 0;
}

Ответ 4

size_t lf = strlen(first);
size_t ls = strlen(second);

char *both = (char*) malloc((lf + ls + 2) * sizeof(char));

strcpy(both, first);

both[lf] = ' ';
strcpy(&both[lf+1], second);

Ответ 5

Они должны быть почти одинаковыми. Разница не будет иметь значения. Я бы пошел с sprintf, так как он требует меньше кода.

Ответ 6

Разница вряд ли имеет значение:

  • Если ваши строки маленькие, malloc заглушит конкатенации строк.
  • Если ваши строки велики, время, затрачиваемое на копирование данных, заглушает различия между strcat/sprintf.

Как отмечали другие плакаты, это преждевременная оптимизация. Сосредоточьтесь на разработке алгоритмов и возвращайтесь к этому, если профилирование показывает, что это проблема производительности.

Тем не менее... Я подозреваю, что метод 1 будет быстрее. Есть некоторые, по общему признанию, небольшие --- накладные расходы для анализа строки формата sprintf. И strcat более вероятно "встроенный".

Ответ 7

sprintf() предназначен для обработки гораздо большего, чем просто строк, strcat() является специалистом. Но я подозреваю, что вы потеете по мелочам. Строки C принципиально неэффективны способами, которые делают различия между этими двумя предложенными методами несущественными. Прочтите "Назад к основам" Джоэл Спольский для подробностей.

Это пример, где С++ обычно лучше, чем C. Для обработки тяжелой строки с использованием std::string, вероятно, будет более эффективным и, безусловно, безопасным.

[править]

[2nd edit] Исправленный код (слишком много итераций в реализации строки C), тайминги и заключение соответственно.

Я был удивлен замечанием Эндрю Бэйнбриджа о том, что std::string был медленнее, но он не опубликовал полный код для этого тестового примера. Я изменил его (автоматизацию синхронизации) и добавил тест std::string. Тест проводился на VС++ 2008 (собственный код) со стандартными опциями "Release" (то есть оптимизированными), Athlon dual core, 2,6 ГГц. Результаты:

C string handling = 0.023000 seconds
sprintf           = 0.313000 seconds
std::string       = 0.500000 seconds

Таким образом, strcat() теперь намного быстрее (ваше перемещение может варьироваться в зависимости от компилятора и параметров), несмотря на присущую неэффективности C-строки соглашение, и поддерживает мое первоначальное предложение о том, что sprintf() несет большую часть багажа не требуется для этой цели. Тем не менее, он остается наименее удобочитаемым и безопасным, поэтому, когда производительность не является критичной, имеет мало преимуществ ИМО.

Я также протестировал реализацию std:: stringstream, которая была намного медленнее, но для сложного форматирования строк все еще имеет смысл.

Исправлен код:

#include <ctime>
#include <cstdio>
#include <cstring>
#include <string>

void a(char *first, char *second, char *both)
{
    for (int i = 0; i != 1000000; i++)
    {
        strcpy(both, first);
        strcat(both, " ");
        strcat(both, second);
    }
}

void b(char *first, char *second, char *both)
{
    for (int i = 0; i != 1000000; i++)
        sprintf(both, "%s %s", first, second);
}

void c(char *first, char *second, char *both)
{
    std::string first_s(first) ;
    std::string second_s(second) ;
    std::string both_s(second) ;

    for (int i = 0; i != 1000000; i++)
        both_s = first_s + " " + second_s ;
}

int main(void)
{
    char* first= "First";
    char* second = "Second";
    char* both = (char*) malloc((strlen(first) + strlen(second) + 2) * sizeof(char));
    clock_t start ;

    start = clock() ;
    a(first, second, both);
    printf( "C string handling = %f seconds\n", (float)(clock() - start)/CLOCKS_PER_SEC) ;

    start = clock() ;
    b(first, second, both);
    printf( "sprintf           = %f seconds\n", (float)(clock() - start)/CLOCKS_PER_SEC) ;

    start = clock() ;
    c(first, second, both);
    printf( "std::string       = %f seconds\n", (float)(clock() - start)/CLOCKS_PER_SEC) ;

    return 0;
}

Ответ 8

Я не знаю, что в случае двух есть реальная конкатенация. Печать их спина к спине не является конкатенацией.

Скажите мне, что было бы быстрее:

1) a) скопировать строку A в новый буфер b) скопировать строку B в буфер c) буфер копирования для вывода буфера

или

1) скопировать строку A в буфер вывода b) скопировать строку b в буфер вывода

Ответ 9

  • strcpy и strcat - гораздо более простые отпечатки по сравнению с sprintf, которые должны анализировать строку формата
  • strcpy и strcat невелики, поэтому они, как правило, будут встроены в компиляторы, экономя даже еще одну дополнительную служебную нагрузку. Например, в llvm strcat будет встроен с помощью strlen, чтобы найти начальную позицию копирования, а затем простую инструкцию хранения

Ответ 10

Ничего ужасно эффективно, так как оба метода должны вычислять длину строки или сканировать ее каждый раз. Вместо этого, поскольку вы все равно вычисляете strlen() s отдельных строк, поместите их в переменные, а затем просто strncpy() дважды.