c - 在c中构建未知长度的大字符串

Question

我毫不怀疑在某个地方有这个问题的答案，我只是找不到它。

经过长时间的休息后，我刚刚回到 c 并且非常生疏，所以请原谅愚蠢的错误。我需要生成一个大的(可能相当于 10mb)字符串。我不知道要等多久才能建成。

我尝试了以下两种方法来测试速度:

int main() {
#if 1
  size_t message_len = 1; /* + 1 for terminating NULL */
  char *buffer = (char*) malloc(message_len);
  for (int i = 0; i < 200000; i++)
  {
    int size = snprintf(NULL, 0, "%d \n", i);
    char * a = malloc(size + 1);
    sprintf(a, "%d \n", i);

    message_len += 1 + strlen(a); /* 1 + for separator ';' */
    buffer = (char*) realloc(buffer, message_len);
    strncat(buffer, a, message_len);
  }
#else
  FILE *f = fopen("test", "w"); 
  if (f == NULL) return -1; 
  for (int i = 0; i < 200000; i++)
  {
    fprintf(f, "%d \n", i);
  }
  fclose(f);
  FILE *fp = fopen("test", "r");
  fseek(fp, 0, SEEK_END);
  long fsize = ftell(f);
  fseek(fp, 0, SEEK_SET);
  char *buffer = malloc(fsize + 1);
  fread(buffer, fsize, 1, f);
  fclose(fp);
  buffer[fsize] = 0;
#endif
  char substr[56];
  memcpy(substr, buffer, 56);
  printf("%s", substr);
  return 1;
}

第一个解决方案每次连接字符串耗时 3.8s，第二个解决方案写入文件然后读取耗时 0.02s。

肯定有一种不用读取和写入文件就可以用 c 语言构建大字符串的快速方法吗？我只是在做一些非常低效的事情吗？如果不能，我可以写入某种文件对象，然后在最后读取它并且永远不保存它吗？

在 C# 中，您会使用字符串缓冲区来避免缓慢的连接，在 C 中有什么等价物？

提前致谢。

Answer 1

这些行让你的生活变得相当艰难:

for (int i = 0; i < 200000; i++)
  {
    int size = snprintf(NULL, 0, "%d \n", i);  // << executed in first loop only
    char * a = malloc(size + 1);               // allocate enough space for "0 \n" + 1
    sprintf(a, "%d \n", i);                    // may try to squeeze "199999 \n" into a

    message_len += 1 + strlen(a); /* 1 + for separator ';' */
    buffer = (char*) realloc(buffer, message_len);
    strncat(buffer, a, message_len);
  }

您在第一次迭代中计算 size 并为 a 分配空间 - 然后在每个后续迭代中继续使用它(其中 i 得到更大，原则上您将超过为 a 分配的存储空间)。如果你正确地做到了这一点(在每个循环中为 a 分配大小)，你将不得不在每个循环中也free，否则会造成巨大的内存泄漏。

在 C 中，解决方案是预先分配大量内存 - 并且仅在紧急情况下重新分配。如果您“大致”知道您的字符串有多大，请立即分配所有内存；跟踪它有多大，如果用完就添加更多。最后，您始终可以“归还未使用的内容”。对 realloc 的多次调用不断移动内存(因为您通常没有足够的可用连续内存)。正如@Matt 在他的评论中澄清的那样:每次调用 realloc 都会移动整个内存块 确实存在风险 - 随着内存块变大，它会变成二次方增加系统的负载。这是一个可能更好的解决方案(完整的，用小 N 和 BLOCK 测试只是为了说明原理；你会想要使用大 N(你的值 200000)和更大的 BLOCK - 并摆脱 printf 在那里显示事情正在工作的语句):

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

#define N 2000000 
#define BLOCK 32 
int main(void) {
size_t message_len = BLOCK; //
  char *buffer = (char*) malloc(message_len);
  int bb;
  int i, n=0;
  char* a = buffer;
  clock_t start, stop;
  for(bb = 1; bb < 128; bb *= 2) {
  int rCount = 0;
  start = clock();
  for (i = 0; i < N; i++)
  {
    a = buffer + n;
    n += sprintf(a, "%d \n", i);
    if ((message_len - n) < BLOCK*bb) {
      rCount++;
      message_len += BLOCK*bb;
      //printf("increasing buffer\n");
      //printf("increased buffer to %ld\n", (long int)message_len);
      buffer = realloc(buffer, message_len);
    }
  }
  stop = clock();
  printf("\nat the end, buffer length is %d; rCount = %d\n", strlen(buffer), rCount);
//  buffer = realloc(buffer, strlen(buffer+1));
  //printf("buffer is now: \n%s\n", buffer);
  printf("time taken with blocksize = %d: %.1f ms\n", BLOCK*bb, (stop - start) * 1000.0 / CLOCKS_PER_SEC);
  }
}

您需要为 BLOCK 使用一个相当大的值 - 这将限制对 realloc 的调用次数。我会使用 100000 之类的值；无论如何，你都摆脱了最后的空间。

编辑 我修改了我发布的代码以允许循环计时 - 将 N 增加到 200 万以获得“合理时间”。我还最小化了初始内存分配(强制对 realloc 进行大量调用并修复了一个错误(当 realloc 必须移动内存时，a不再指向 buffer 中的偏移量。现在通过跟踪 n 中的字符串长度来解决这个问题。

这非常快 - 最小块为 450 毫秒，较大块(200 万个数字)下降到 350 毫秒。这与您的文件读/写操作相当(在我测量的分辨率范围内)。但是是的 - 文件 I/O 流和相关的内存管理是高度优化的......