Самый эффективный способ объединения строк в c

Question

Рассмотрим эту простую программу, которая объединяет все указанные параметры и печатает их в стандартном выводе.Я использовал 2 для циклов, чтобы добавить строки, один для вычисления длины этой строки и один для объединения строк.Есть ли способ сделать это только с одной петлей?Разве не было бы более эффективно перераспределять память для каждой строки для конкатенации?Как бы Java StringBuilder был реализован в C?Будет ли это повторяться дважды, как я?

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

int main(int argc, char** argv)
{
    size_t len = 0;

    // start for loop at i = 1 to skip the program name specified in argv
    for(int i = 1; i < argc; i++)
        len += strlen(argv[i]) + 1; // +1 for the space 

    char* toAppend = (char*)malloc(len * sizeof(char) + 1);
    toAppend[0] = '\0'; // first string is empty and null terminated 

    for(int i = 1; i < argc; i++)
    {
        strcat(toAppend, argv[i]);
        strcat(toAppend, " ");
    }

    printf(toAppend);
    free(toAppend);
}

Answer 1

Наиболее эффективный способ, вероятно, состоит в том, чтобы не использовать никакие функции str и копировать символы "вручную":

char* toAppend = malloc(len + 1);

size_t j = 0;
for(size_t i = 1; i < argc; i++)
{
  for(size_t k = 0; argv[i][k]; k++)
    toAppend[j++] = argv[i][k];
  toAppend[j++] = ' ';
}
toAppend[j - 1] = '\0'; // Remove the last space and NULL-terminate the string

Answer 2

эффективный способ объединения строк в c

Эффективный способ - это вычисление длин строк и их запоминание.

size_t sum = 1; // for \0
if (argc > 2) sum += argc - 2.  // spaces
size_t length[argc];  // This is a VLA, available C99 and optionally in C11
for(int i = 1; i < argc; i++)
  length[i] = strlen(argv[i]);
  sum += length[i];
}

Затем выделите и проверьте ошибки.

char *dest = malloc(sum);
if (dest == NULL) Handle_OutOfMemory();

Скопируйте каждую строку по очереди

char *p = dest;
for(int i = 1; i < argc; i++)
  // Use either memcpy() or strcpy().
  // memcpy() tends to be faster for long strings than strcpy().
  memcpy(p, argv[i], length[i]);  
  p += length[i]; // advance insertion point
  if (i > 1) {
    *p++ = ' '; // space separators
  }
}
*p = '\0';

Теперь используйте dest[].

printf("<%s>\n", dest);

Свободные ресурсыкогда закончите.

free(dest);

---

Не было бы более эффективно перераспределять память для каждой строки для конкатенации, не так ли?

Обычно повторяющиеся перераспределенияЛучше избегать, но для небольших коротких струн это действительно мало что меняет.Сосредоточьтесь на большой O .Мой ответ O(n).Перемещение в цикле имеет тенденцию быть O(n*n).

Если производительность была критической, попробуйте различные подходы и профиль для предполагаемой системы.Дело в том, что скорость на одной машине может отличаться на другой.Обычно лучше всего сначала написать разумный и понятный подход.

Answer 3

Ваш метод распределения эффективен, он измеряет общую длину и выделяется только один раз.Но цикл конкатенации многократно измеряет длину выходного буфера от начала до конкатенации к нему, что приводит к квадратичному времени выполнения.

Чтобы исправить это, следите за своей позицией на ходу:

size_t pos = 0;
for(int i = 1; i < argc; i++) {
    size_t len = strlen(argv[i]);
    memcpy(toAppend+pos, argv[i], len);
    pos += len;
    toAppend[pos] = ' ';
    pos++;
}
toAppend[pos] = 0;

Это наиболее эффективный способ объединения в памяти, но наиболее эффективным является , а не объединение .Вместо этого:

for(int i = 1; i < argc; i++)
    printf("%s ", argv[i]);

Вся причина, по которой stdio буферизуется, заключается в том, что вам не нужно создавать буферы произвольной длины в памяти для эффективного вывода;вместо этого он автоматически буферизует до фиксированного размера и сбрасывается при заполнении буфера.

Обратите внимание, что использование printf неверно и опасно, если ваш ввод содержит символ % в любом месте;это должно быть printf("%s", toAppend);.

Если вы пишете в системы POSIX (или POSIX-ish), а не просто в C, другой вариант будет fmemopen, что позволит вам написать цикл простокак:

for(int i = 1; i < argc; i++)
    fprintf(my_memfile, "%s ", argv[i]);