我正在编写一个程序，该程序从流(在我的示例中为管道或套接字)读取数据并将该数据放入数组中。问题是我不知道我需要从流中读取多少数据，以及为什么我不知道需要为阵列分配多少内存。如果我知道什么，这个问题就没有必要了。我唯一知道的是流中出现的某些值(例如 -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 FrameworkList<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。如果使用 20k因子，则下一次重新分配将失败，因为您需要超过 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(实际测试)