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：提前分配內存還是每次分配內存？

回答

相關問題