我正在编写一个程序，它从流中读取数据（在我的示例中为管道或套接字）并将该数据放入数组中。问题是我不知道我需要从流中读取多少数据，以及为什么我不知道需要为我的数组分配多少内存。如果我知道什么，这个问题就没有必要了。我所知道的唯一的事情就是在流中出现一些值（例如-1），这意味着流的结束。所以从流中读取数据的函数可能如下所示：
int next_value() {
return (rand() % 100) - 1;
}
使用此数据工作的代码如下所示：
int main()
{
int len = 0;
int *arr = NULL;
int val, res = 0;
srand(time(NULL));
while ((val = next_value()) != -1) {
if ((res = set_value_in_array(val, &arr, &len))) {
perror("set_value_in_array");
exit(EXIT_FAILURE);
}
}
// uncomment next line if set_value_in_array_v2 or set_value_in_array_v3
//realloc(arr, len * sizeof(*arr));
free(arr);
return 0;
}
我有三种策略将数据放入数组，并为该数组提供内存分配例程。
最简单的是为next_value()出现的每个新值分配（重新分配）内存，如下所示：
// allocate new element in array for each call
int set_value_in_array_v1(int val, int **arr, int *len) {
int *tmp;
tmp = realloc(*arr, ((*len) + 1) * sizeof(**arr));
if (tmp) {
*arr = tmp;
} else {
return -1;
}
*((*arr) + (*len)) = val;
(*len)++;
return 0;
}
很简单，但我认为这并不理想。我不知道将从流中读取多少个值。值的数量可以在0到无穷大的范围内。另一种策略是为多个元素分配内存。这将减少对内存管理单元的调用次数。代码可能如下所示：
// allocate ELEMS_PER_ALLOC every time allocation needed
int set_value_in_array_v2(int val, int **arr, int *len) {
#define ELEMS_PER_ALLOC 4 // how many elements allocate on next allocation
int *tmp;
if ((*len) % ELEMS_PER_ALLOC == 0) {
tmp = realloc(*arr, ((*len) + ELEMS_PER_ALLOC) * sizeof(**arr));
if (tmp) {
*arr = tmp;
} else {
return -1;
}
}
*((*arr) + (*len)) = val;
(*len)++;
return 0;
}
更好，但它是最好的解决方案吗？如果我将以几何级数分配内存，如下所示：
// allocate *len * FRAC_FOR_ALLOC each time allocation needed
int set_value_in_array_v3(int val, int **arr, int *len) {
#define FRAC_FOR_ALLOC 3 // how many times increase number of allocated memory on next allocation
static int allocated = 0; // i know this is bad to use static but it's for experiments only
int *tmp;
if (allocated == (*len)) {
if (allocated == 0) {
allocated = 1;
}
allocated *= FRAC_FOR_ALLOC;
tmp = realloc(*arr, allocated * sizeof(**arr));
if (tmp) {
*arr = tmp;
} else {
return -1;
}
}
*((*arr) + (*len)) = val;
(*len)++;
return 0;
}
在.NET Framework List<T>数据结构中使用相同的方法。这种方式有一个大问题：它会在100个元素和情况之后分配大量内存，当没有办法增加当前的内存块时更容易出现。
另一方面，如果流中有很多数据，set_value_in_array_v2会经常调用内存管理器，这也不是一个好主意。
所以我的问题是在类似我的情况下，内存分配的最佳策略是什么？我在互联网上找不到任何问题的答案。每个链接只显示内存管理API使用的最佳实践。
提前致谢。
如果每次添加新元素时重新分配的重新分配数量为n。内存使用没有最坏的情况。
如果以4的倍数重新分配内存，重新分配的数量几乎是n/4。在最糟糕的情况下，你将浪费3个单位的内存。
如果每次空间用完时将内存重新分配k因子所需的重新分配数量为log n，其中对数的基数为k。在最糟糕的情况下，你将浪费(1 - 1/k)*100％的内存。对于k = 2，您将有50％的已分配内存未使用。平均而言，你将使用(1 - 1/k)*0.5*100％的内存。
在使用几何序列重新分配内存时，您将获得对数时间复杂度。但是，k的大因素也会限制您可以分配的最大内存量。
假设您可以为您的需求分配仅1GB的内存，并且您已经存储了216MB。如果使用k因子为20，则下一次重新分配将失败，因为您需要超过1GB的内存。
你的基数越大，时间复杂度越小，但它也增加了在最差（和平均）情况下未使用的内存量，并且还将最大内存限制为比你实际使用的内存更小的内存（这个当然情况因情况而异;如果你有1296MB的可分配内存且你的基数是6，那么数组大小的上限将是1296MB，因为1296是6的幂，假设你开始使用6的幂的内存。
你需要什么取决于你的情况。在大多数情况下，您可以粗略估计内存需求。您可以通过将初始内存设置为估计值来进行第一次优化。每次内存不足时，您可以将内存增加一倍。关闭流后，可以重新分配内存以匹配数据的确切大小（如果确实需要释放未使用的内存）。
这个问题是我学士论文的一部分，不幸的是它是德语。
我比较了3种分配方法：固定增加（你的情况2），固定因子（你的情况3）和动态因子。
其他答案中的分析非常好，但我想添加一个重要的实际测试结果：固定步长增加可以在运行时使用最多的内存！ （并且要慢几个数量级......）
为什么？假设您已为10个项目分配了空间。然后在添加第11项时，空间应该增加10.现在可能无法简单地增加前10个项目旁边的空间（因为否则会使用它）。因此分配了20个项目的新空间，复制了原始空间10，并释放了原始空间。你现在已经分配了30个项目，实际上只能使用20个。每次分配都会变得更糟。
我的动态因子方法意味着快速增长，只要步骤不是太大，后来使用较小的因素，以便最大限度地减少内存不足的风险。它是某种倒立的S形函数。
论文可以在这里找到：XML Toolbox for Matlab。相关章节是3.2（实施）和5.3.2（实际测试）