在 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.8 秒，第二个写入文件然后读取需要 0.02 秒。

当然，有一种快速的方法可以在 c 中构建一个大字符串，而无需借助读写文件？我只是在做一些非常低效的事情吗？如果不能，我可以写入某种文件对象，然后在最后读取它并且永远不保存它吗？

在 C# 中，您将使用 stringbuffer 来避免慢速连接，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 流和相关的内存管理是高度优化的......