使用realloc動態數組大小與初始大小C

我是C語言新手（來自java），想知道在我的情況下什麼是更好的方法。我正在編程一個遊戲，並且在生成動作的函數中，我想返回一些指向結構數組的指針（Move由結構體表示）。因爲我事先不知道數組的大小，我想從一個空數組開始，而不是每次我想添加一個移動（通過realloc（size + 1））來調整它的大小。但我想知道，如果設置一個初始尺寸，並且如果我需要，只是將尺寸增加一倍，是否更爲理想。性能更好的方法是什麼？使用realloc動態數組大小與初始大小C

謝謝！

來源

2013-08-23 user2030118

顯然是雙倍大小的。 –

倍增效率更高，那是什麼'矢量'我認爲 –

即使將一些腰部空間？ – user2030118

多次調用realloc將是低效的。因此添加一個內存大小是一個壞主意。將尺寸加倍，當您完成並獲得想要存儲數據的精確尺寸時，您可以將realloc縮小至該尺寸。這應該照顧浪費的內存。但realloc只有在最後時，你認爲你不需要增加了。

根據具體情況和您的實現，如果您認爲當分配的內存總量變大時加倍會有點太多，您可以添加檢查以增量增加內存。類似於

if (memory_allocated < 100) 
    //realloc to double size 
else 
    //realloc 10 more

上面的數字是任意的，您可以選擇更好的數字。但如果將內存加倍是一個巨大的問題，請使用此選項。否則加倍並重新分配到精確是一個足夠好的解決方案。

來源

2013-08-23 06:11:11

我會更進一步：不要使用'realloc（）'來縮小數組！無論如何，該內存將需要使用。 – 2013-08-23 06:14:04

@ H2CO3這將取決於實施。我不知道存儲的內容是否只是暫時的。假設他縮小了添加的數據，那麼在之前的迭代中，加倍的內存可能會成爲內存消耗。完成後縮小可以處理內存佔用。但是這顯然取決於具體的實施。 –

哼，因爲'malloc'和'realloc'使用分頁，它真的很重要嗎？ – DCMaxxx

你可以翻一番。但是如果你關心時間和浪費的空間，你需要知道移動次數的分佈。也就是說，有多少時間出現1次移動，2次移動等等。然後，一種方法可能會更清晰。例如，當移動次數爲< = 100時加倍，但爲大於100時加上20.

最初，將代碼寫入遊戲中，跟蹤這些統計數據並相應調整您的方法。

來源

2013-08-23 06:15:06 JackCColeman

-1

沒有比賽。每次需要分配更多內存時，請選擇任意大小並加倍。該函數調用realloc()爲您需要添加的每個結構都會導致您的程序變慢。

realloc()也是昂貴的。每次你調用它時，你都會在堆上使用一塊新的內存。 realloc()在成功分配新內存時釋放最初分配的塊;但是，這會導致堆碎片，並且即使存在大量可用內存，仍有可能無法分配連續內存。

最後，每次調用realloc()時，都會冒內存分配失敗的風險。爲什麼不盡可能少地將風險降至最低？

來源

2013-08-23 06:16:48 verbose

downvoter照顧解釋？ – verbose

除了使用realloc來提高分配性能使數組大小加倍外，我還會問你是否真的需要每個Move項的O（1）訪問時間。如果沒有，你也可以使用一個列表，而不是像：記住

typedef struct Move Move; 
struct Move { 
    /* your stuff here */ 
    Move *next; 
};

有了這個，你可以一個新的移動項目每次創建一個新的時間添加到列表頭部或尾部。但是，在這裏，您最終需要O（n）個訪問時間來隨機訪問移動項目。

來源

2013-08-23 06:20:35 anselm

但即便如此，您仍可以創建一個「緩存陣列」來存儲每個元素的地址。但是，您必須確保每次鏈接列表更改時更新此緩存。此外，結合2個概念是可行的：建立一個數組鏈表。如果數據以塊的方式添加，現在我可以添加10個條目，然後添加40條，那麼添加一個由'next'指針，'count'值或者'大小「值（如果內存塊的大小很重要）和一些元素。 – glglgl

是的，我也想過這個解決方案（鏈表）。我也考慮它 – user2030118

鏈接列表大部分時間比可調整大小的數組顯着更慢，因爲引用的位置很差。只有在需要頻繁插入中間或前端時才使用鏈接列表。 –

假設你有一個n個元素的數組，現在它已滿。每次您撥打realloc()時，每個元素都將被移至新的空間。

的realloc（大小+ 1）：

的移動總和1+2+...+n = O(n^2)

（即使它開始作爲k+k+1...+n，它原來是爲O（n^2），其中k是原始空間，你的malloc）

的realloc（尺寸* 2），即使原來的空間只有一個：

的移動之和爲n*(1/2+1/4+...+1/(2^logn))，（2^LOGN = N）和金額的上限爲2n，那就是說，O(n)。

很明顯，當總元素的數量很少時，它們幾乎是相同的。但是如果n很大，那麼雙重效率更高。順便說一句，當數組滿了時，數組的大小加倍，是很多動態數組的一個流行工具。

來源

2013-08-23 06:34:38 vvy

使用realloc動態數組大小與初始大小C

回答

相關問題