0

我目前正在用 C 实现一个非常简单的JSON 解析器，我希望能够使用可变字符串（我可以在没有可变字符串的情况下做到这一点，但是无论如何我想学习最好的方法）。我目前的方法如下：

char * str = calloc(0, sizeof(char));
//The following is executed in a loop
int length = strlen(str);
str = realloc(str, sizeof(char) * (length + 2));
//I had to reallocate with +2 in order to ensure I still had a zero value at the end
str[length] = newChar;
str[length + 1] = 0;

我对这种方法很满意，但是考虑到我总是每次只附加一个字符，这让我觉得效率有点低（为了争论，我没有做任何前瞻来找到我的字符串的最终长度） . 另一种方法是使用链表：

struct linked_string
{
    char character;
    struct linked_string * next;
}

然后，一旦我完成处理，我就可以找到长度，分配char *适当长度的 a，并遍历链表以创建我的字符串。

但是，这种方法似乎内存效率低，因为我必须为每个字符和指向下一个字符的指针分配内存。因此，我的问题有两个：

  • 创建一个链表然后创建一个 C 字符串是否比每次重新分配 C 字符串更快？
  • 如果是这样，获得的速度是否值得更大的内存开销？
4

4 回答 4

4

动态数组的标准方法，不管你是存储chars 还是其他东西，都是在增长时将容量翻倍。（从技术上讲，任何多重工作，但加倍很容易，并且在速度和内存之间取得了很好的平衡。）您还应该放弃 0 终止符（如果您需要返回 0 终止的字符串，请在末尾添加一个）并跟踪分配的大小（也称为容量）和实际存储的字符数。strlen否则，您的循环由于重复使用而具有二次时间复杂度（ Shlemiel the Painter's algorithm）。

通过这些更改，时间复杂度是线性的（每次追加操作的摊销常数时间），并且由于各种丑陋的低级原因，实际性能非常好。

理论上的缺点是您使用的内存最多是严格必要的两倍，但对于相同数量的字符，链表需要至少五倍的内存（使用 64 位指针、填充和典型的 malloc 开销，更像是 24或 32 次）。在实践中这通常不是问题。

于 2013-10-12T19:17:40.193 回答
1

不，链表肯定不是“更快”（你如何以及在哪里测量这样的东西）。这是一个可怕的开销。

如果你真的发现你当前的方法是一个瓶颈，你总是可以分配或重新分配你的字符串，大小为2. 然后，您只需realloc在跨越char数组总大小的这样一个边界时执行此操作。

于 2013-10-12T19:14:48.377 回答
1

我建议将整组文本读入一个内存分配，然后通过 NUL 终止每个字符串是合理的。然后计算字符串的数量，并制作一个指向每个字符串的指针数组。这样，您就为文本区域分配了一个内存，为指针数组分配了一个。

于 2013-10-12T19:17:27.520 回答
0

大多数可变长度数组/字符串/任何东西的实现都有一个size和一个capacity。容量是分配的大小，大小是实际使用的大小。

struct mutable_string {
   char* data;
   size_t capacity;
};

分配新字符串如下所示：

#define INITIAL_CAPACITY 10

mutable_string* mutable_string_create_empty() {
   mutable_string* str = malloc(sizeof(mutable_string));
   if (!str) return NULL;

   str->data = calloc(INITIAL_CAPACITY, 1);
   if (!str->data) { free(str); return NULL; }

   str->capacity = INITIAL_CAPACITY;

   return str;
}

现在，任何时候你需要向字符串中添加一个字符，你都可以这样做：

int mutable_string_concat_char(mutable_string* str, char chr) {
   size_t len = strlen(str->data);
   if (len < str->capacity) {
      str->data[len] = chr;
      return 1; //Success
   }

   size_t new_capacity = str->capacity * 2;
   char* new_data = realloc(str->data, new_capacity);
   if (!new_data) return 0;

   str->data = new_data;
   str->data[len] = chr;
   str->data[len + 1] = '\0';
   str->capacity = new_capacity;
}

链表方法更糟糕，因为：

  1. 每次添加字符时，您仍然需要进行分配调用；
  2. 它消耗更多的内存。这种方法最多消耗sizeof(size_t) + (string_length + 1) * 2. 这种方法消耗string_length * sizeof(linked_string).
  3. 通常，链表不如数组对缓存友好。
于 2013-10-12T19:22:31.157 回答