C：提前分配内存还是每次分配内存？

我有一个简单的问题给你。当在C中创建自己的动态数组实现时，在数组接近达到当前最大能力时，最好先分配内存（假设为10个元素），或者在每次元素数改变时重新分配内存？C：提前分配内存还是每次分配内存？

我的意思是：对于表现，优雅或任何想到你的想法。

来源

2009-12-24 shazarre

通常的选择是将多个电流的大小是固定数量大于一（1.5ish是常见的，因为是2），它可以让你摊销为O（n）总分配和复制成本。

请注意，您无法保证可以增加阵列的大小，因此您可能必须将所有现有元素复制到新位置（realloc()会自动为您执行此操作，但您仍需支付费用成本）。

来源

2009-12-24 23:55:22 dmckee

这是很多更好的性能realloc尽可能少的时间。所以，你可以这样做：

array = realloc(array, old_size * 2);

来源

2009-12-24 23:53:55

不要忘记更改old_size的值！ array = realloc（array，old_size =（old_size * 2））; – Amy 2009-12-24 23:56:16

如果知道数组的平均大小和增长率，也可以对其进行优化。 – 2009-12-24 23:57:33

不要忘记'realloc'可能会失败！你需要检查。 – rlbond 2009-12-25 00:23:30

在堆上分配内存始终代价高昂。逐元素地进行并不是可以建议的。

来源

2009-12-24 23:57:00 Jagannath

此外，很多小的分配可能会碎片堆 – 2009-12-25 00:18:53

您可以定义一个结构是这样的：

/** Dynamic array */ 
typedef struct __darray { 
     int* array;   /** Array */ 
     int size;    /** Array size */ 
     int cap;    /** Capacity */ 
} darray;

尺寸< =能力。

如果您的尺寸>容量，当您动态添加新元素测试时。如果为true，则执行内存重新分配。公式（从JDK ArrayList中implementantion拍摄）是：

(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 *”。

来源

2009-12-25 00:08:43

如果这种动态数组实现方法适用于许多上下文，那么最好将预测的额外分配控制给用户，而不是将其嵌入到库中。

来源

2009-12-25 00:45:43

更新的内存分配策略是Solaris和Linux采用的Slab Allocator。 Memcached也使用this FAQ entry记录的板分配器。

来源

2009-12-25 01:00:49

这似乎是一个动态数组实施，但不好的选择。 – 2009-12-25 01:10:37

我同意，但发现学习Solaris内部知识时非常有趣。 – 2009-12-25 10:46:55

通常更好的方式是以“开始”固定大小进行预先分配，并在空间不足时根据增长因子重新分配空间。

根据您的需要，可以根据您处理的数据的典型用法或为数据创建的API确定起始大小和增长因子，以便调用者可以指定起始大小和增长因子为初始化/创建调用的一部分。

起始大小应该是基于典型用法的数字。典型用法是帮助您挑选大小的重要因素，以便您：A）不要通过选择“太大”的起始大小来浪费空间，并且B）不要使用小于许多重新分配的起始大小在达到目标典型大小之前是必要的。

典型的尺寸当然是一个神奇的数字。确定典型大小的方法是使用各种数据集运行一些测试，并收集数据的开始大小，重新分配次数和最小/最大内存使用情况的统计信息。您可以对结果进行平均以获得可用的典型起始大小。

至于生长因子，x1.5或x2生长因子是常见的。这是您可以使用测试统计与开始大小一样衡量的内容。

要考虑的另一件事是，您需要小心管理对动态调整大小的数据的引用，因为realloc（）会在需要时重新定位内存中的数据。这意味着如果您存储了动态调整大小的数组的第一个元素的地址，那么在调用realloc之后该地址可能无效。这可以通过围绕您的自定义数据类型的API包装器进行管理，该包装器提供索引而不是内存地址，并且可以在需要时将索引解析为元素的当前地址。

来源

2009-12-25 02:23:20

C：提前分配内存还是每次分配内存？

回答

相关问题