logo标签列表

在C语言中，是提前分配内存还是按需分配内存更好？

c
4

我有一个简单（可能）的问题要问你。在C语言中创建自己的动态数组实现时，当数组接近其当前最大容量时，是提前分配内存（假设为10个元素），还是每次元素数量发生更改时重新分配内存更好？

我的意思是：对于性能、优雅或任何你想到的东西。

7个回答
5

通常的选择是将当前大小乘以一个大于1的固定数字（一般为1.5或2），这样可以得到摊销O(n)的总分配和复制成本。

请注意，并没有保证您可以原地增加数组的大小，因此您可能需要将所有现有元素复制到新位置（realloc（）会自动为您执行此操作，但您仍然需要付出代价）。

4

为了提高性能，尽可能少地使用 realloc 是更好的选择。所以你可以这样做：

array = realloc(array, old_size * 2);

4
不要忘记改变 old_size 的值！数组 = realloc(数组, old_size = (old_size * 2)); - user47589
2
如果您知道数组的平均大小和增长率，也可以对其进行优化。 - Dirk Vollmar
3
不要忘记 realloc 可能会失败！你需要检查这一点。 - rlbond
在进行乘法运算之前，不要忘记检查溢出情况：if (old_size > SIZE_MAX / 2) { handle_error(); } - caf
微不足道的错误，但是...如果你从oldsize = 0（没有数据）开始，那么你真的应该做((oldsize+1)2)或max(1, oldsize2)，否则你将永远卡在大小为零的状态。 - Adisak
2
通常最好预先分配一个"起始"固定大小，当你用尽空间时，根据增长因素进行重新分配。根据你处理的数据的典型用法或创建数据的API，可以确定起始大小和增长因子。作为初始化/创建调用的一部分，调用者可以指定起始大小和增长因子。
起始大小应该是基于典型用法的数字。典型用法是帮助你选择大小的重要因素，这样你就不会浪费空间选择一个"太大"的起始大小，并且不会使用一个起始大小太小以至于需要许多重新分配才能达到目标典型大小。
当然，典型大小是一个神奇的数字。确定典型大小的方法是使用各种数据集运行一些测试，并收集起始大小、重新分配次数和数据最小/最大内存使用量的统计数据。你可以平均结果得到可用的典型起始大小。
至于增长因子，x1.5或x2是常见的增长因子。这是你可以像起始大小一样使用测试统计数据来掌握的。
另一件需要考虑的事情是你需要小心管理对动态可调整大小的数据的引用，因为realloc()在需要时会重新定位内存中的数据。这意味着如果你存储了动态可调整大小数组的第一个元素的地址，那么在调用realloc之后该地址可能无效。可以通过一个API包装器来管理你的自定义数据类型，该包装器分发索引而不是内存地址，并且有一种方式来解析索引以获取元素的当前地址。
1
你可以像这样定义一个结构体：
/** Dynamic array */
typedef struct __darray {
        int* array;            /** Array */
        int size;               /** Array size */
        int cap;                /** Capacity */
} darray;

Size <= capacity .

当您动态添加新元素时，请测试您的大小是否 > 容量。 如果为真，则执行内存重新分配。 公式（取自 JDK 的 ArrayList 实现）如下：

(jobs here...)
[your_darray]->capacity+=[your_darray]->capacity*3/2+1;
[your_darray]->array=(int*)realloc([your_darray]->array,capacity*sizeof(int));
(jobs here...)

如果你从动态数组中删除了足够数量的元素，请别忘了再次收缩“int*”。
1

在堆上分配内存总是很昂贵的。逐个元素地执行这个操作是不可取的。

2
此外，大量的小内存分配很可能会导致堆内存碎片化。 - Ken Keenan
0
如果这个动态数组实现打算在许多上下文中使用，那么最好将预测性的额外分配控制权交给用户，而不是将其嵌入库中。
0
这似乎不是动态数组实现的最佳选择。 - John Knoeller
我同意，但发现在学习 Solaris 内部结构的过程中很有趣。 - PP.
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接