C编程 - realloc应该使用多频繁？

Question

我有一个关于动态内存分配的问题。

背景信息：我正在编写一个程序，读取一个单词的文本文件并计算每个单词出现的频率（每行一个单词）。

这个特定的函数会读取文件，计算行数和字符数，然后动态分配内存给字符串指针数组、存储每行字符数的数组以及字符串本身。（其他部分与我的问题没有直接相关性。）

问题：如果我空间不足时，应该多久重新分配内存一次？我为初始内存分配值设置了一个常量（“memstart”）。在下面的代码片段中，每当行数超过“memstart”时就进行重新分配。如果每次增加内存空间时，我重新分配一个更大的内存块，程序会更快吗？

像这样的事情最好的做法是什么？

代码片段：

int read_alloc(FILE* fin, FILE *tmp, char **wdp, int *sz){
    int line_cnt= 0, chr, let=1;
    do{
        chr=getc(fin);
        let++;          
        //count characters

        if(chr!=EOF){
            chr=tolower(chr);
            fputc(chr, tmp);
        }               
        //convert to lcase and write to temp file

        if ('\n' == chr || chr==EOF){
            sz[(line_cnt)]=((let)*sizeof(char));            //save size needed to store string in array
            *(wdp+(line_cnt))=malloc((let)*sizeof(char));   //allocate space for the string
            if ((line_cnt-1) >= memstart){
                realloc(wdp, (sizeof(wdp)*(memstart+line_cnt)));    //if more space needed increase size
                realloc(sz, (sizeof(sz)*(memstart+line_cnt)));
            }
            line_cnt++;         
            let=1;
        }
    } while (EOF != chr);

    return (line_cnt);
}

- LeAnn

---

通常情况下，容器会以某个固定的因子增长，比如1.5。也就是说，每次需要调整容量时，都会将容量设为当前容量的1.5倍。 - zerkms

在增加分配时，一个好的一般策略是从一个合理大小的分配开始，并根据需要进行 _加倍_。当完成增加分配后，可以使用最终调用 realloc() 将其修剪到最终大小。 - ad absurdum

你应该重新分配“log”次数。 - Ajay Brahmakshatriya

realloc（比以前更大的大小）应该至少使用与您打算跨越上一个大小的最后一个字节的次数相同的次数。如果使用次数较少，那么您会遇到麻烦。 - Kaz

Answer 1

虽然问题是关于realloc应该调用多少次的，但从OP的代码来看，我认为最好先考虑如何安全地完成它。C11标准规定（n1570草案，§7.22.3.5，“realloc函数”，我加重了部分文本）：realloc函数释放ptr指向的旧对象，并返回一个指向大小由size指定的新对象的指针。新对象的内容应与旧对象在释放之前相同，大小不超过新旧对象中较小的那个。新对象中超出旧对象大小的任何字节都具有不确定的值。如果ptr是空指针，则realloc函数对指定的大小行为类似于malloc函数（...）。如果无法为新对象分配内存，则不会释放旧对象且其值不变。realloc函数返回指向新对象的指针（可能与指向旧对象的指针具有相同的值），如果无法分配新对象，则返回空指针。现在来看一下问题中的这个片段，其中sz被声明为int * sz;。

realloc(sz, (sizeof(sz)*(memstart+line_cnt)));

返回值丢失，因此我们无法知道调用是否成功，如果成功，sz将被使无效。另外，sizeof(sz)是指针的大小，而不是所指类型(int)的大小。

更安全（和正确）的模式应该是：

size_t new_size = /* Whatever, let's say */ size + SOME_COSTANT + size / 2;
void *tmp = realloc(ptr, new_size * sizeof *ptr);
if ( tmp == NULL ) {
    /* Deal with the error, e.g. log a message with perror, return NULL
       (if this is in a function) or just give up, but remeber that
       realloc doesn't invalidate nor free 'ptr' on failure */
    exit(EXIT_FAILURE);
}
ptr = tmp; // <- on success, realloc invalidated ptr
size = new_size;   

现在，回答这个问题，只有在需要时才应该调用realloc，因为它涉及到潜在的耗费系统调用。因此，要么提前分配一个大块，要么选择像每次增加两倍（或1.5倍）这样的增长策略。

值得注意的是，如果可能的话，操作系统可以在不复制原始数组中的任何元素的情况下执行重新分配。

- Bob__

---

只有一些小问题。realloc 返回 void *，所以只需要 void *tmp = realloc(..。如果 tmp == NULL 不要释放指针，你之前的所有数据仍然由 ptr 指向，只是不要将 ptr = tmp。最后一个小问题，'*' 跟随 变量，而不是 类型。（例如，int* a, b, c; 显然不会使 b 和 c 成为指针） - David C. Rankin

1）好观点，我错过了那个。2）我释放了数据，因为它仍然被指向，因为在代码片段中我正在退出，通常我会在函数中返回（并检查以处理其他要释放的资源）NULL，但我理解你的观点。3）我知道 ;)这是我使用的一种风格（也经常看到），因为通常我尝试不在一个语句中声明多个变量，但是它可能会误导，我理解你的观点。 - Bob__

谢谢。这非常有益。 - LeAnn

Answer 2

经典答案是每次加倍，但乘以1.5的因子可能更好。重要的是，你需要每次通过某个因子乘以你的数组大小，而不是添加额外的空间。

每次重新分配都可能需要将先前的数组复制到新数组中。我们希望尽量减少这些复制。如果我们将添加n个项，并从大小为a的数组开始，每次增加r的因子进行重新分配，最终得到一个值为n的数组，则（重新）分配的序列为a，ar，ar^2，ar^3，...，n。该序列的总和为(nr-a)/(r-1)。因此，总空间的顺序为O(n)。

假设我们从a开始，每次增加r。 序列是a，a + r，a + 2r，a + 3r，...，n。该序列的总和将为0.5 *（（n ^ 2-a ^ 2）/ r + a + n）。在这种情况下，订单的总空间为O（n ^ 2）。更糟糕！

通过一个常数因子2，数组在最坏情况下将有1/2为空。那可能没关系。您可以在完成并知道最终大小时缩小分配。

正如另一个答案中指出的那样，在调用realloc（）的方式中存在几个错误，但这不是问题。

- TrentP